Task swapping networks in distributed systems

Abstract

In this paper we propose task swapping networks for task reassignments by using task swappings in distributed systems. Some classes of task reassignments are achieved by using iterative local task swappings between software agents in distributed systems. We use group-theoretic methods to find a minimum-length sequence of adjacent task swappings needed from a source task assignment to a target task assignment in a task swapping network of several well-known topologies.

Keywords:

• task swapping network
• task swapping graph
• task assignment
• permutation group
• distributed system

2010 AMS Subject Classifications:

• 20B30
• 05C25
• 68T42
• 68M14

C.R. Categories:

• C.2.1
• G.2.3

Notes

1. In this paper, we use task migration and process migration interchangeably.

2. An alternative method to find a minimum-length permutation factorization of permutation using the generating set S₁={(i i+ 1): 1≤i<n} is to apply numbers game 415 of finite Coxeter group of type A_n−1 2053. An interested reader may refer to 4152053 for further details.

3. Source codes and sample data are available at http://www.airesearch.kr/downloads/tsg.zip.