# More on Pipelined Dynamic Scheduling of Big Data Streams
## 3 Preliminaries and Communication Scheduling  
### Preliminaries  
In this paragraph, we present the mathematical notations required to implement our stepwise scheduler (the interested reader can find more details and proofs in [1]). The main idea is to organize all the communications in a set of communication pairs, such that there is one-to-one communication between the system's nodes at any given time. First, let us define an equation that describes the round-robin placement of \(t\) consecutive tasks into a set of nodes. This equation describes the _initial task distribution_. \[n=\lfloor i/t\rfloor\mod N, \tag{1}\]  
where \(N\) is the number of nodes in the initial distribution, \(p\in[0,\dots,N-1]\), \(n\) is the node where a task indexed \(i\) is placed and \(t\) is the number of tasks assigned per node. The range of \(i\) is from \(0\) to \(N\times t\). For example, if there are \(t=4\) tasks per node and \(N=6\), our model assumes 24 tasks. Then, tasks \(i=0,1,2\), and 3 will be located at node \(n=0\), tasks \(i=4,5,6\), and 7 will be located at node \(n=1\), tasks \(i=8,9,10\), and 11 will be located at node \(n=2\),... and tasks \(i=20,21,22\), and 23 will be located at node \(n=5\). From Equation (1), for some integer \(L\) we get that  
\[\lfloor i/t\rfloor=LN+n. \tag{2}\]  
Now, if we set an integer \(x\), such that \(x=i\mod t\), \(0\leq x<t\), Equation (2) becomes  
\[i=(LN+n)t+x \tag{3}\]  
Equation (3) describes the initial task distribution. We use \(R(i,n,L,x)\) to symbolize this distribution. A task migration usually occurs if a node has certain indications that it will be be down after a while or when it has become overloaded. In such a case, certain task that it processes have to be migrated. Now, if we wish to describe such a different scenario, where the number of tasks changes, we need a second equation. This equation is derived in a similar way. Now, if we assume that the number of nodes changes from \(N\) to \(Q\), so \(Q\) is now the number of nodes, \(q\) is the node where a task indexed \(j\) will be placed and \(s\) is the new number of tasks. Thus, we get:  
\[j=(MQ+q)s+y \tag{4}\]  
where \(q\in[0,\dots,Q-1]\) and the integers \(M,y\) are defined similarly as \(L\) and \(x\) in Equation (4). For \(y\), we have \(0\leq y<s\). We use \(R^{\prime}(j,q,M,y)\) to symbolize a distribution that would incur in case of the system changes described before. Now, we will use Equations (3) and (4) to define sets of one-to-one communication steps among the systems nodes. The idea is to equate the two distributions \(R\) and \(R^{\prime}\) and generate a linear Diophantine equation. From modular arithmetic, we know that the linear Diophantine equations can have solutions divided into classes. The linear Diophantine equation required by our schedule is provided as follows:  
\[R=R^{\prime}\Rightarrow(LN+n)t+x=(MQ+q)s+y \tag{5}\]or  
\[nt-qs+(x-y)=MQs-LNt \tag{6}\]  
In [1], it was proven that every communicating pair \((p,q)\) belongs to a class \(k\) if it satisfies the equation:  
\[(pt-qs)\ mod\ g=k \tag{7}\]  
For the members \((p,q)\) of every class \(k\), there is a constant number of combinations of \(x\) and \(y\) values, name it \(c\), (recall that \(x\) and \(y\) are limited by \(t\) and \(s\), respectively) that produce \(k\) when we get their modulo to \(g\)[29]. Totally, there are \(g\) classes and there may be two or more classes with the same value of \(c\). These classes are referred as _homogeneous_. We now illustrate the ideas described so far in this section with an example. Assume that initially, we have \(N=6\) nodes and \(t=4\) tasks are executed per node. Then, based on system monitoring, one node is reported to be heavily overloaded and need to be relieved from certain processing load (recall that nodes may be executing a variety of tasks at any time). This means that its tasks will have to be redistributed to the remaining 5 nodes. Then, each of the remaining nodes will have to handle \(s=5\) tasks.