On the number of acceptable task assignments in distributed computing systems

A distributed computing system and cooperating tasks can be represented by a processor graph G_p=(V_p, E_p) and a task graph G_T=(V_T, E _T), respectively. An edge between a pair of nodes in G_T represents the existence of direct communications between the two corresponding tasks. The maximal number of hops between two processors in G_p to which two adjacent tasks in G_T are assigned is called dilation of that assignment. Characterization and use of the number of acceptable assignments for given G_T and G_P are treated. Assignments with the dilation less than or equal to one are considered. This dilation constraint represents a special case in which two adjacent tasks in G_T must be assigned to either a single processor or two adjacent processors in G_p. For the case where N(G_T, G_P ) denotes the numbers of acceptable assignments under this constraint, N(G_T, G_P) are derived for arbitrary G_T and G_P , and a recursive expression is formulated for N(G _T, G_P) when G_T is a tree. For some restricted cases, either closed-form or recursive-form expressions of N(G_T, G _P) are derived. The results on N(G_T, G_P) are extended to the completely general case, assignments with dilations greater than one, where two adjacent tasks in G_T can be assigned to any two processors in G_P which are not necessarily adjacent to each other