## 3 A Motivating Example  
Let us consider a cluster of \(N=6\) nodes and an application topology such as the one in Figure 1, in which the interconnection between the components is shown. In this figure, there are four bolts and one spout, each of which have \(t=4\) threads. Each thread executes one task, so we can refer to tasks and threads interchangeably hereafter. Our offline (static) strategy [1] uses a set of matrix transformation based on linear algebra theory that aims (1) to produce a series of communication steps such that each node communicates to exactly one other node at a time, and (2) to place the tasks in the most suitable (in terms of distance) nodes, so that their communication (as defined by the application topology) is implemented with the minimum communication latency. In short, our strategy initially defines the initial matrix, \(M_{init}\), as a table that stores the tasks assigned to each node by the default round-robin Storm scheduler. This table can have two forms: in the first form, the tasks are indicated as letters, and in the second, they have been replaced by numbers. \[M_{init} = \left[ \begin{array}{cccccc}N_{0}&N_{1}&N_{2}&N_{3}&N_{4}&N_{5} \\ \texttt{Q}&\texttt{R}&\texttt{S}&\texttt{T}&\texttt{A}&\texttt{B}\\ \texttt{C}&\texttt{D}&\texttt{E}&\texttt{F}&\texttt{G}&\texttt{H}\\ \texttt{I}&\texttt{J}&\texttt{K}&\texttt{L}&\texttt{M}&\texttt{N}\\ \texttt{0}&\texttt{P}&\Omega&\Omega&\Omega&\Omega\end{array} \right]\equiv \tag{1}\] \[\equiv \left[ \begin{array}{cccccc}N_{0}&N_{1}&N_{2}&N_{3}&N_{4}&N_{5} \\ 0&1&2&3&4&5\\ 6&7&8&9&10&11\\ 12&13&14&15&16&17\\ 18&19&\texttt{\textasciitifbox{200}}&\texttt{\textasciitifbox{200}}&\texttt{ \textasciitifbox{200}}\end{array} \right]\]  
Figure 1: Task interconnection for a random application. The tasks indicated by \(\Omega\) are added by our model as \"dummies\" and are used to avoid empty values in \(M_{init}\). In the numbered representation, the dummy tasks are circled. A dummy task plays no role in the actual processing. The scheduler performs a series of well-defined matrix transformations and uses a refinement phase to produce the final matrix \(M^{\prime}_{fin}\). The refinement phase is used to allocate the tasks to the proper nodes, meaning that intercommunication latencies caused by the communication between tasks are reduced. Each row of this matrix indicates a communication step between the node labeled at the top of each column and the node index found in the specific row. For the example of Figure 1 the corresponding \(M^{\prime}_{fin}\) is  
\[M^{\prime}_{fin}= \begin{array}{cccccc}N_{0}&N_{1}&N_{2}&N_{3}&N_{4}&N_{5}\\ \hline 0&1&2&5&3&4\\ 1&0&5&2&4&3\\ 3&4&0&1&2&5\\ 4&3&1&0&5&2\end{array} \]  
and the communications defined by the first row are as follows: node 0 transfers tuples to node 0 (internal communication between the tasks residing in node 0), node 1 to node 1 (internal communication between the tasks residing in node 1), node 2 to node 2 (internal communication between the tasks residing in node 2), node 3 to node 5, node 4 to node 3 and node 5 to node 4. Internal task communications are preferred whenever possible, as they add no extra communication latencies. Moreover, \(M^{\prime}_{fin}\) can be used to define the task allocations in each node. In this example, the equivalent task allocation matrix is  
\[M^{\prime}_{fin}= \begin{array}{cccccc}N_{0}&N_{1}&N_{2}&N_{3}&N_{4}&N_{5}\\ \hline Q&A&E&\Omega&I&M\\ B&R&\Omega&F&N&J\\ K&O&S&C&G&\Omega\\ P&L&D&T&\Omega&H\end{array} \]  
which indicates that, for the specified application topology, the communication latencies are reduced by placing tasks Q,B,K and P to node \(N_{0}\), tasks A,R,0 and L to node \(N_{1}\), etc. Generally, the static approach does its best to find an optimal solution for a task allocation and scheduling problem. Specifically, the following tasks are addressed:  
1. It reduces the buffering space required by each task, and the system's throughput therefore increases (most of the tuples are processed as soon as they arrive at the processing node);
2.