Migration of Tasks in Interconnection networks Based on the Star Graph

Document Type


Publication Date


Publication Title

Journal of Parallel and Distributed Computing



First page number:


Last page number:



The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The procedure for task allocation in the star graph can be done using the star code and the allocation tree constructed based on this code. In this paper, the optimal set of codes which can collectively recognize a set of distinct substars is derived. It is shown that using only (n − 1) codes, almost half of the existing substars in an n-dimensional star is recognizable for n ≤ 9. When relinquishment of tasks is considered, task migration could potentially improve the utilization of network resources by reducing/eliminating the fragmentation caused as a result of task deallocation. A deadlock-free procedure is presented to migrate a task, distributed over the nodes of one substar, to the nodes of the other substar wherein: (i) subtasks travel in parallel via disjoint paths; (ii) the adjacency among the mapped nodes is preserved. The procedure can be made distributed with a slight modification. The work can be extended to other hierarchical networks based on permutation group.


Cayley graphs; Computer algorithms; Computer network resources; Computer networks; Distributed operating systems (Computers); Routing (Computer network management)


Digital Communications and Networking | Electrical and Computer Engineering | Engineering | Signal Processing | Systems and Communications




Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library