AN ALGORITHM FOR FIFO MESSAGE DELIVERY AMONG MIGRATING TASKS

We consider distributed-memory parallel machines that support the FIFO delivery of messages among processors, and present an asynchronous di stributed algorithm that ensures the FIFO delivery of messages among t asks that migrate in such machines. For the concurrent migration of a set K of tasks, the algorithm requires O(nm(K)) interprocessor message s and O(n) time to run, where n is the number of processors in the sys tem and m(K), is the number of pairs of communicating tasks involving the migrating tasks. However, for a great number of current distribute d-memory architectures, these complexities can be reduced to O(m(K)) a nd O(1), respectively.