## 4 Mathematical Background  
In this paragraph, we present the mathematical notations required to implement the PMOD scheduler. The main idea behind what follows is not to re-allocate the tasks (this is not an efficient solution to follow as the program runs), but instead to organize all the communications in \"homogeneous\" groups in terms of communicating pairs, which will be used to achieve a schedule with reduced memory consumption and thus a higher achievable throughput and balanced load among all the nodes. First, let us define an equation that describes the round-robin placement of \(r\) consecutive tasks into a set of nodes. \[n=\lfloor i/t\rfloor\mod N, \tag{2}\]  
where \(N\) is the number of nodes in the initial distribution, \(n\) is the node where task \(i\) is placed and \(t\) is the number of tasks. From Equation (2), for some integer \(L\), we obtain  
\[\lfloor i/t\rfloor=LN+n. \tag{3}\]  
Now, if we set an integer \(x\) such that \(x=i\mod t,0\leq x<t\), Equation (3) becomes  
\[i=(LN+n)t+x \tag{4}\]  
Equation (4) describes the initial task distribution. We use \(R(i,n,L,x)\) to symbolize this distribution. In a similar manner, we can derive an equation that describes the new distribution, according to the system changes. Assume that the number of nodes changes from \(N\) to \(Q\); thus, \(Q\) is the number of nodes in the new distribution, \(q\) is the node where task \(j\) will be placed and \(s\) is the new number of tasks. Thus, we obtain  
\[j=(MQ+q)s+y \tag{5}\]  
where the integers \(M,y\) are defined in a similar manner to \(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 occur in the case of the system changes described before. However, as stated at the beginning of this section, our aim is not to perform a task redistribution but to define sets of homogeneous communications that will rapidly produce an efficient communication schedule with reduced latencies. The idea is to equate the two distributions defined in Equations (4) and (5) and generate a linear Diophantine equation as follows:  
\[R=R^{\prime}\Rightarrow(LN+n)t+x=(MQ+q)s+y \tag{6}\]  
or  
\[nt-qs+(x-y)=MQs-LNt \tag{7}\]  
Such linear Diophantine equations are solved using the extended Euclidean algorithm in logarithmic time, which is perfectly suitable for our scheduler. Now, we set \(G=gcd(Nt,Qs)\), making \(LNt-MQs\) a multiple of \(g\). This means that there is an integer \(\lambda\), such that \(LNt-MQs=\lambda g\). If we also set \(z=x-y\), then (7) is rewritten as  
\[\lambda g-z=nt-qs \tag{8}\]  
From modular arithmetic, we are aware that, for linear Diophantine equations, a pair of processors \((p,q)\) belongs to a communication class \(k\) if  
\[(pt-qs)\ mod\ g=k \tag{9}\]Proposition 1 will make use of the definition of a class and Equation (7) to show the homogeneity of the processor pairs found in each class. **Proposition 1**. : _All processor pairs that belong to a class are proven to be homogeneous in terms of the number of solutions that they produce for Equation (8)._  
Proof. : We divide both parts of Equation (8) with \(g\) to obtain  
\[ \begin{array}{l}(\lambda g-z)\mod g=(nt-qs)\mod g\Rightarrow\\ (\lambda g\mod g)-(z\mod g)=(nt-qs)\mod g\Rightarrow\\ (0-z)\mod g=(nt-qs)\mod g\Rightarrow\\ -z\mod g=(nt-qs)\mod g.\end{array} \]  
Since \(z=x-y\), it is obvious that \(-z=y-x\). Therefore, we derive the equation  
\[(y-x)\mod g=(nt-qs)\mod g\quad\text{or}\quad(y-x)\ mod g=k \tag{10}\]  
Equation (10) states that for every class \(k\) (and thus for its members--a set of communicating pairs), there is a constant number of combinations of \(x\) and \(y\) values, which we name \(c\) (recall that \(x\) and \(y\) are limited by \(t\) and \(s\) respectively), that produce \(k\) when we get their modulo to \(g\). This proves Proposition 1. The main characteristics of classes [24; 25; 26] are summarized as follows:  
1. The maximum number of classes that exist in a redistribution problem is \(g\);
2.