# Task swapping networks in distributed systems

Dohan Kim<EMAIL_ADDRESS>
###### 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

12pt

##  1 Introduction

A distributed system is defined as a collection of independent computers or
processors that are connected by an arbitrary interconnection network [1, 2].
The objective of a task assignment [3, 1] in a distributed system is to find
an optimal or suboptimal assignment of tasks to processors (or agents), while
satisfying temporal and spatial constraints imposed on the system. A task
assignment is either preemptive or non-preemptive [4]. If a task assignment is
preemptive, a task reassignment is allowed in such a way that tasks are
transferred between processors (or agents) during their execution for
improving the system performance [4, 5]. Recent advances in software agent
technology [6, 7, 8] in distributed systems allow software entities to observe
their environment, and cooperate with other entities if necessary to
accomplish their goals. Task migration 111In this paper we use task migration
and process migration interchangeably. between software agents intends to
improve the system throughput in a distributed system in which the loads
incurred by tasks vary over time [8]. A task reassignment can be achieved by
iterative local task swappings, where a task swapping involves task migrations
between a pair of agents as a method of local task reassignment [9]. A
subclass of task assignment (or reassignment) problems involves an equal
number of tasks and agents, finding a bijective task assignment between tasks
and agents in such a way that the total task assignment (or reassignment)
benefit is maximized [10]. Those bijective task assignment problems and their
variants appear in a wide variety of areas in computer science and mathematics
[11, 12, 10, 13]. Given $n$ tasks and $n$ agents whose connections are
described by a (connected) network topology, task swapping cost between two
agents often relies on a distance in the network topology; the larger the
distance between two agents in the network topology, the larger communication
delays of migrating tasks caused by the network. Therefore, we need to
consider how task swappings are performed on a given network topology for task
reassignments. In this type of problems a group theory can be used to
represent task reassignments including iterative task swappings. A group-
theoretic approach to representing task assignments or reassignments have
already been researched [14, 15]. However, little work has done about task
swappings for task reassignments between tasks and agents by using group
theory. We propose a group-theoretic model of global task reassignments
involving $n$ tasks and $n$ agents by using local task swappings in a
distributed network of several well-known topologies.

This paper is organized as follows. Section 2 presents the problem formulation
and its assumptions. We give the necessary definitions for the problem
formulation in this section. Section 3 gives an introduction to permutation
groups and Cayley graphs. We also discuss transposition graphs of several
network topologies and their relationship to permutation sortings in this
section. We present task swapping graphs and their examples in distributed
systems in Section 4. Group-theoretic properties of task swapping graphs and
their examples are discussed in this section. Finally, we conclude in Section
5.

##  2 Problem formulation and assumptions

An _agent graph_ $G_{a}=(V_{a},E_{a})$ [16] is an undirected graph, where
$V_{a}$ denotes a set of agents in a distributed system and $E_{a}$ denotes
communication links between agents. Let $T=\\{t_{1},t_{2},\ldots,t_{n}\\}$ be
a set of $n$ tasks and $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$ be a set of $n$
agents represented by an agent graph $G_{a}=(V_{a},E_{a})$. Now, each task is
assigned to each agent in $G_{a}=(V_{a},E_{a})$ bijectively as an initial task
assignment by using a task assignment algorithm. Suppose the load on each
agent varies over time, implying that an initial task assignment may not
remain optimal or suboptimal. The _load rebalancing_ intends to find a task
reassignment in order to decrease makespan [17], or to achieve a target load
balance level along with minimum task migration cost [18]. Task migration
between agents incurs a task migration cost [19] to transfer the state of the
running task (e.g., execution state, I/O state, etc) of one agent to the other
agent. This cost is not trivial, following that only nearby agents (or
processors) in the network topology are often involved to perform a task
migration [18, 20]. Moreover, if we restrict each task reassignment to be
bijective between tasks and agents, then iterative local task swappings can be
used for a global task reassignment. A _swapping distance_ is defined as the
distance between agents in an agent graph $G_{a}$ for a task swapping. For
example, a task swapping of swapping distance 1 is a task swapping between
adjacent agents in $G_{a}$, and a task swapping of swapping distance 2 is a
task swapping between agents whose distance is 2 in $G_{a}$. Now, the overall
cost difference before task swapping and after task swapping for
computationally intensive tasks (rather than communicationally intensive
tasks) is roughly the cost of a target task assignment after task swapping
subtracted by the cost of a source task assignment before task swapping, and
added by the task swapping cost itself. In the remainder of this paper we
assume the followings:

  1. 1.

Each task and agent are not necessarily homogeneous, and the load on each
agent may vary over time.

  2. 2.

An agent network described by $G_{a}=(V_{a},E_{a})$ is static without taking
mobility (e.g., dynamic join or leave by agents [21]) into account.

  3. 3.

A task swapping cost is uniform between adjacent agents in the agent network.

  4. 4.

A task swapping cost is assumed to be proportional to a task swapping
distance.

  5. 5.

Each task is long-lived and computationally intensive.

  6. 6.

A global task reassignment is obtained by using iterative and sequential local
task swappings.

  7. 7.

A task startup cost and the message passing overhead for task migration
protocol are ignored.

  8. 8.

Every agent in $G_{a}=(V_{a},E_{a})$ is cooperative [22], pursuing the same
goal to improve their collective performance for task assignments.

It follows that the expected total cost of task migrations hinges on how many
local task swappings are needed from a source task assignment to a target task
assignment. A decision making by the coordinator agent(s) whether or not a
task reassignment is performed is based on the information regarding the total
cost of task migrations along with the cost difference involving a source and
target task assignment. Let $g_{1}$ be a bijective source task assignment
between a set of $n$ tasks $T=\\{t_{1},t_{2},\ldots,t_{n}\\}$ and a set of $n$
agents $A=\\{a_{1},a_{2},\ldots,a_{n}\\}$ before task migrations. Let $g_{2}$
be a feasible target task assignment between $T$ and $A$ after task
migrations, which implies that $g_{2}$ can be obtained by using iterative
local task swappings. Let $h_{1}$ be the cost of task assignment $g_{1}$ and
let $h_{2}$ be the cost of task assignment $g_{2}$. Let
$f(g_{1},g_{2},s_{1},s_{2},\ldots,s_{k})$ be the total cost of task
migrations, where $s_{i}$ for $1\leq i\leq k<n$ is the number of local task
swappings of swapping distance $i$ involved in converting $g_{1}$ to $g_{2}$.
Then, a task reassignment benefit $b(h_{1},h_{2},f)$ is defined as
$-(h_{2}-h_{1}+f(g_{1},g_{2},s_{1},s_{2},\ldots,s_{k}))$, i.e.,
$h_{1}-h_{2}-f(g_{1},g_{2},s_{1},s_{2},\ldots,s_{k})$. The higer value of
$b(h_{1},h_{2},f)$ implies that a task reassignment is more desirable, while
the negative value of $b(h_{1},h_{2},f)$ implies that a task reassignment from
$g_{1}$ to $g_{2}$ is not desirable at all. If we restrict a local task
swapping to be a task swapping between adjacent agents in
$G_{a}=(V_{a},E_{a})$, $f(g_{1},g_{2},s_{1},s_{2},\ldots,s_{k})$ is simply
$cs_{1}$, where $c$ is constant. If we restrict a local task swapping to be a
task swapping between agents in $G_{a}=(V_{a},E_{a})$ within distance $m$,
$f(g_{1},g_{2},s_{1},s_{2},\ldots,s_{k})$ is $cs_{1}+2cs_{2}+\cdots+mcs_{m}$,
where $c$ is constant and $s_{r}$ $(1\leq r\leq m)$ is the number of task
swappings of swapping distance $r$ involved in converting $g_{1}$ to $g_{2}$.
The problem is formulated as follows:

Given a source task assignment $g_{1}$ and a feasible target task assignment
$g_{2}$ on the agent network described by an agent graph
$G_{a}=(V_{a},E_{a})$, find the minimum total cost of task migrations
$f(g_{1},g_{2},s_{1},s_{2},\ldots,s_{k})$ to reach from $g_{1}$ to $g_{2}$.

In this paper we only concern local task swappings of swapping distance 1,
which are adjacent task swappings between agents in $G_{a}=(V_{a},E_{a})$.
Since we assumed that a task swapping cost is uniform between adjacent agents
in $G_{a}=(V_{a},E_{a})$, the problem is reduced to find the minimum number of
adjacent task swappings needed from a source task assignment to reach a target
task assignment in $G_{a}=(V_{a},E_{a})$.

##  3 Transposition and Cayley graphs

We first give a brief introduction to finite groups found in [23, 24, 25, 15].

A _group_ $(G,\,\cdot\,)$ is a nonempty set _G_ , closed under a binary
operation $\cdot:G\times G\rightarrow G$, such that the following axioms are
satisfied: (i) $(a\cdot b)\cdot c=a\cdot(b\cdot c)$ for all $a,b,c\in G$; (ii)
there is an element _e_ $\in$ _G_ such that for all $x\in G,~{}e\cdot x=x\cdot
e=x$; (iii) for each element $a\in G$, there is an element $a^{-1}\in G$ such
that $a\cdot a^{-1}=a^{-1}\cdot a=e$. If $H$ is a nonempty subset of $G$ and
is also a group under the binary operation $\cdot$ in $G$, then $H$ is called
a _subgroup_ of $G$.

The group of all bijections $I_{n}\rightarrow I_{n}$, where
$I_{n}=\\{1,2,\ldots,n\\}$, is called the _symmetric group on n letters_ and
denoted $\mathfrak{S}_{n}$. Since $\mathfrak{S}_{n}$ is the group of all
permutations of $I_{n}=\\{1,2,\ldots,n\\}$, it has order $n!$. A _permutation
group_ is a subgroup of some $\mathfrak{S}_{n}$.

Let $i_{1},i_{2},\ldots,i_{n}$ be distinct elements of
$I_{n}=\\{1,2,\ldots,n\\}$. Then,
$\begin{pmatrix}1&2&\cdots&n\\\ i_{1}&i_{2}&\cdots&i_{n}\end{pmatrix}$
$\stackrel{{\scriptstyle\rm{def}}}{{=}}i_{1}\,i_{2}\,\cdots\,i_{n}$$\in\mathfrak{S}_{n}$
denotes the permutation that maps $1\mapsto i_{1},2\mapsto
i_{2},\ldots,n\mapsto i_{n}$.

Let $i_{1},i_{2},\ldots,i_{r}\,(r\leq n)$ be distinct elements of
$I_{n}=\\{1,2,\ldots,n\\}$. Then $(i_{1}\,i_{2}\cdots i_{r})$ is defined as
the permutation that maps $i_{1}\mapsto i_{2}$, $i_{2}\mapsto i_{3}$,…,
$i_{r-1}$$\mapsto i_{r}$ and $i_{r}\mapsto i_{1}$, and every other element of
$I_{n}$ maps onto itself. Then, $(i_{1}\,i_{2}\cdots i_{r})$ is called a cycle
of length $r$ or an $r$-cycle; a 2-cycle is called a _transposition_.

Let $G$ be a group and let $s_{i}\in G$ for $i\in I$. The subgroup generated
by $S=\\{s_{i}:i\in I\\}$ is the smallest subgroup of $G$ containing the set
$S$. If this subgroup is all of $G$, then $S$ is called a _generating set_ of
$G$.

An (right) action of a group $G$ on a set $X$ is a function $X\times
G\rightarrow X$ (usually denoted by $(x,\,g)\mapsto xg$) such that for all
$x\in X$ and $g_{1},g_{2}\in G$: (i) $xe=x$; (ii)
$x(g_{1}g_{2})=(xg_{1})g_{2}$. When such an action is given, we say that $G$
acts (right) on the set $X$. The set $X$ is called a (right) $G$-set. If $X$
is $G$ as a set, we say that $G$ acts on itself.

######  Theorem 3.1 ([24]).

Every non-identity permutation in $\mathfrak{S}_{n}$ can be expressed as a
product of disjoint cycles of length at least 2. Further, $\mathfrak{S}_{n}$
can be expressed as a product of (not necessarily disjoint) transpositions. ∎

For example, $p=2\,1\,6\,3\,4\,5\in\mathfrak{S}_{6}$ is written as
$(1\,2)(3\,6\,5\,4)$ as a product of disjoint cycles or
$(1\,2)(3\,4)(3\,5)(3\,6)$ as a product of transpositions.

Let $G$ be a finite group and $S$ be a generating set of $G$. Then,
$\text{Cay}(G,S)$ denotes the _Cayley graph_ [26, 25, 27] of $G$ with the
generating set $S$, where the set of vertices $V$ of $\text{Cay}(G,S)$
corresponds to the elements of $G$, and the set of edges $E$ of
$\text{Cay}(G,S)$ corresponds to the action of generators in such a way that
$E=\\{<x,y>_{g}:x,y\in G\text{ and }g\in S\text{ such that }y=x\cdot g\\}$. In
this paper we assume that $G$ is a finite permutation group and the elements
of $S$ are transpositions in $\text{Cay}(G,S)$. It follows that $S$ is closed
under inverses, and $E$ is undirected. In other words, an edge $<x,y>$ of the
resulting $\text{Cay}(G,S)$ is viewed as both $<x,y>_{g}$ and $<y,x>_{g}$. If
$G$ is a finite group and $S$ is a set of transpositions that generates $G$,
then a _transposition graph_ $T=(<n>,S)$ [27] is an undirected graph in which
$<n>$ denotes a vertex set of cardinality $n$ and each edge $<i,\,j>$ denotes
transposition $(i\,j)$. If a transposition graph is a tree, we call the
resulting transposition graph as a _transposition tree_. We next provide
examples of the generating sets for permutation groups including their
transposition trees.

Let

$S_{1}=\\{(i\,i+1):1\leq i<n\\},\\\ $ (1) $S_{2}=\\{(2i-1\,2i):1\leq i\leq
n\\},\\\ $ (2) $S_{3}=\\{(1\,i):2\leq i\leq n\\},\\\ $ (3)
$S_{4}=\\{(i\,j):1\leq i<j\leq n\\},\\\ $ (4) $S_{5}=\\{(i\,j):1\leq i\leq
k<j\leq n\\},\\\ $ (5) $S_{6}=S_{1}\cup\\{(1\,n)\\}.$ (6)

Fig. 1: Examples of transposition graphs $T=(<n>,S)$ [27].

Fig. 1 shows different kinds of transposition graphs corresponding to the
generating sets $S_{1},\,S_{2},\ldots,\,S_{6}$ for some $n$ and $k$. In this
paper a transposition graph having $n$ vertices are labeled from 1 to $n$
without any duplication. The Cayley graph generated by $S_{1}$ is called the
_bubble-sort_ graph $\text{BS}_{n}$ [26, 27], by $S_{2}$ is called the
_hypercube_ graph $\text{HC}_{n}$ [25], by $S_{3}$ is called the _star_ graph
$\text{ST}_{n}$ [26, 27, 25], by $S_{4}$ is called the _complete
transposition_ graph $\text{CT}_{n}$ [27], by $S_{5}$ is called the
_generalized star_ graph $\text{GST}_{n,k}$ [25], and by $S_{6}$ is called the
_modified bubble sort_ graph $\text{MBS}_{n}$ [27].

Fig. 2: The bubble sort graph $\text{BS}_{4}$ [25].

A path $p$ from vertex $v_{1}$ to vertex $v_{2}$ in $\text{Cay}(G,S)$ can be
represented by a sequence of generators $g_{1},g_{2},\ldots,g_{k}$, where
$g_{i}\in S$ for $1\leq i\leq k$. By abuse of notation, we let
$p=g_{1}g_{2}\ldots g_{k}$. Note that $p$ is also a path from vertex
$v_{2}^{-1}v_{1}$ to vertex $I$ (i.e., $v_{1}p=v_{2}$ if and only if
$v_{2}^{-1}v_{1}p=I$ for the identity permutation $I$ in $G$). Thus, to find a
path from vertex $v_{1}$ to vertex $v_{2}$ is reduced to find a path from
vertex $v_{2}^{-1}v_{1}$ to vertex $I$, which in turn is reduced to the
problem of sorting $v_{2}^{-1}v_{1}$ to $I$ using the generating set $S$ [26].

Fig. 2 shows the bubble sort graph $\text{BS}_{4}$ of the transposition tree
$T=(<4>,S_{1})$. Since adjacent transpositions $(1\,2),(2\,3)$, and $(3\,4)$
generate $\mathfrak{S}_{4}$, $\text{BS}_{4}$ has $|\mathfrak{S}_{4}|=24$
vertices, each of which has degree 3. To find a path from permutation $p_{1}$
to permutation $p_{2}$ in $\text{BS}_{4}$ is obtained by using the bubble sort
algorithm [28]. For example, let vertex $v_{1}$ be $2\,1\,3\,4$ and vertex
$v_{2}$ be $3\,1\,4\,2$ in $\text{BS}_{4}$. Then, to find path $p$ from
$v_{1}=2\,1\,3\,4$ to $v_{2}=3\,1\,4\,2$ is equivalent to find path $p$ from
$v_{2}^{-1}v_{1}=4\,2\,1\,3$ to permutation $I$:
$4\,2\,1\,3\xrightarrow{<1,2>}$$2\,4\,1\,3\xrightarrow{<2,3>}$$2\,1\,4\,3\xrightarrow{<3,4>}$$2\,1\,3\,4\xrightarrow{<1,2>}$$1\,2\,3\,4$,
where the label of each arrow denotes an edge in $\text{BS}_{4}$. Thus, we
have $p=(1\,2)(2\,3)(3\,4)(1\,2)$.

Fig. 3: The star graph $\text{ ST}_{4}$ [25].

Fig. 3 shows the star graph $\text{ ST}_{4}$ of the transposition tree
$T=(<4>,S_{3})$. Similarly to the bubble sort graph $\text{ BS}_{4}$, star
transpositions $(1\,2),(1\,3)$, and $(1\,4)$ generate $\mathfrak{S}_{4}$.
Therefore, $\text{ST}_{4}$ has $|\mathfrak{S}_{4}|=24$ vertices, each of which
has degree 3.

Note that transpositions denoted by a transposition tree of order $n$ labeled
from 1 to $n$ generate $\mathfrak{S}_{n}$ [26]. However, not every
transposition graph having $n\,(n\geq 2)$ vertices yields a Cayley graph of
$\mathfrak{S}_{n}$. For example, Fig. 1(b) shows a transposition graph having
6 vertices, but it yields a Cayley graph of a group isomorphic to $C_{2}\times
C_{2}\times C_{2}$ instead of $\mathfrak{S}_{6}$, where $C_{2}$ is the cyclic
group of order 2.

The _minimum generator sequence_ [29] for permutation $p$ of a permutation
group $G$ using the generating set $S$ is a minimum-length sequence consisting
of generators in $S$ whose composition is $p$. For example, permutation
$\pi=4\,2\,3\,1\in\mathfrak{S}_{4}$ can be expressed as
$\pi=(1\,2)(2\,3)(3\,4)(2\,3)(1\,2)$ of length 5 or $\pi=(1\,4)$ of length 1
using the generating set $S_{6}^{\prime}=\\{(i\,i+1):1\leq
i<4\\}\cup\\{(1\,4)\\}$ in which $\pi=(1\,4)$ is the minimum generator
sequence of length 1. Further, if an element $s$ in the generating set $S$ can
be expressed as the product of elements in $S$ other than $s$, then the
generating set is called _redundant_ [27]. For example, $S_{6}$ is redundant,
since $(1\,n)$ can be expressed as
$(1\,2)(2\,3)\cdots(n-1\,n)\cdots(2\,3)(1\,2)$.

Recall that the _diameter_ [30] of a connected graph is the length of the
”longest shortest path” between two vertices of the graph. Thus, the diameter
of $\text{Cay}(G,S)$ is an upper bound of distance $d(\sigma,I)$ from an
arbitrary vertex $\sigma$ to vertex $I$ in $\text{Cay}(G,S)$, where the
computation of $d(\sigma,I)$ is obtained by sorting permutation $\sigma$ to
the identity permutation $I$ in $G$ by means of the minimum generator sequence
using the generating set $S$ [25]. Thus, the diameter of $\text{Cay}(G,S)$ is
an upper bound of the lengths of minimum generator sequences for permutations
in $G$ using the generating set $S$ [26].

Table 1: Properties of some known Cayley graphs [27]. Types | Number of Vertices | Degree | Diameter
---|---|---|---
$\text{BS}_{n}$ | $n!$ | $n-1$ | $n(n-1)/2$
$\text{ST}_{n}$ | $n!$ | $n-1$ | $\lfloor 3(n-1)/2\rfloor$
$\text{CT}_{n}$ | $n!$ | $n(n-1)/2$ | $n-1$
$\text{GST}_{n,k}$ | $n!$ | $k(n-k)$ | $n-1+\max{(\lfloor k/2\rfloor,\lfloor(n-k)/2\rfloor)}$
$\text{MBS}_{n}$ | $n!$ | $n$ | Unknown
$\text{HC}_{n}$ | $2^{n}$ | $n$ | $n$
|  |  |
|  |  |

Now, consider a _permutation puzzle_ [26] on a transposition tree described as
follows: Given a transposition tree $T$ having $n$ vertices labeled from 1 to
$n$, place $n$ markers, each of which is labeled from 1 to $n$, at the
vertices of $T$ arbitrarily in such a way that each vertex of $T$ is paired
with an exactly one marker. Let $P$ be such an arbitrary initial position of
markers. Each legal move of the puzzle is to interchange the markers placed at
the ends of an edge in $T$. The terminal position of markers, denoted $Q$, is
the position in which each marker is paired with each vertex of $T$ having the
same label. The puzzle is to find a sequence of legal moves from a given
initial position $P$ to the final position $Q$ with the minimum number of
legal moves.

######  Theorem 3.2 ([26]).

Let $T$ be a transposition tree having $n$ vertices. Given an initial position
$P$ for a permutation puzzle on $T$, the final position $Q$ for the puzzle can
be reached by legal moves in the following number of steps

$c(p)-n+\displaystyle\sum_{i=1}^{n}{d(i,p(i))}$,

where $p$ is the permutation for $P$ as an assignment of markers to the
vertices of $T$, $c(p)$ is the number of cycles in $p$, and $d(i,j)$ is the
distance between vertex $i$ and vertex $j$ in $T$. ∎

######  Corollary 3.1 ([25]).

Let Diam(Cay(G, S)) be the diameter of Cay(G, S) of a transposition tree $T$
having $n$ vertices. Let $P$ be an initial position and $Q$ be the final
position for a permutation puzzle on $T$. Then,

$\text{Diam(Cay(G, S))}\leq\displaystyle\max_{p\in
G}\\{c(p)-n+\sum_{i=1}^{n}{d(i,p(i))}\\}$,

where $p$ is the permutation for $P$ as an assignment of markers to the
vertices of $T$, $c(p)$ is the number of cycles in $p$, and $d(i,j)$ is the
distance between vertex $i$ and vertex $j$ in $T$. ∎

The Cay(G, S) of a transposition tree $T$ can be viewed as the state diagram
of a permutation puzzle on $T$, where the vertices of Cay(G, S) is the
possible positions of markers on $T$ and each edge of Cay(G, S) corresponds to
a legal move of the permutation puzzle on $T$. An upper bound of the minimum
number of legal moves to reach the final position $Q$ for a given initial
position $P$ is indeed the diameter of Cay(G, S) [26] of a transposition tree
$T$. Moreover, the inequality in Corollary 3.1 can be replaced by the equality
for the cases of bubble sort and star graphs [25].

We close this section by describing the main ideas behind Theorem 3.2 (an
interested reader may refer to [26] for further details). Consider a
permutation puzzle on a transposition tree $T$ having $n$ vertices. Let $p$ be
a permutation for position $P$ as an assignment of $n$ markers to the $n$
vertices of $T$. The marker $i$ is said to be _homed_ if $i=p(i)$. If there
exists any unhomed marker in the assignment, either one of two cases occurs.
The first case is that there exists an edge of $T$ involving two unhomed
markers $x$ and $y$ such that they need to move toward each other for the
final position $Q$. The second case is that there exists an edge of $T$
involving one unhomed marker $x$ and one homed marker $y$ such that $x$ needs
to move toward $y$ for the final position $Q$. In both cases, interchanging
markers $x$ and $y$ reduces the number of steps in Theorem 3.2. Finally, if
there is no such case in the assignment (i.e., all markers are homed), then
the number is reduced to 0.

##  4 Task swapping networks

In Section 3 we discussed a permutation puzzle on a transposition tree $T$
having $n$ vertices and its legal moves. We now consider a transposition tree
as a network topology in which each vertex of $T$ corresponds to an agent and
each marker to a task. Further, consider a position of $n$ markers placed at
$n$ vertices of $T$ as a task assignment involving $n$ tasks and $n$ agents.
Each legal move of a permutation puzzle then corresponds to an adjacent task
swapping in the network topology. We apply the idea of the permutation puzzle
on a transposition tree to task assignments in a task swapping network. We
first define a _task swapping graph_.

A _task swapping graph_ $\Gamma$ having $n$ vertices is a connected graph in
which each vertex represents an agent and each edge represents a direct
communication between agents. The label next to each vertex denotes an agent
ID in $\Gamma$. Now, $n$ tasks are assigned to $n$ vertices of $\Gamma$ as a
task assignment in which the label of each vertex in $\Gamma$ denotes a task
ID. We assume that each task and agent ID are distinct numbers from the set
$\\{1,2,\ldots,n\\}$, where $n$ is the number of vertices in $\Gamma$.
Therefore, each task assignment in $\Gamma$ is represented by permutation
$p=\begin{pmatrix}1&2&\cdots&n\\\ t_{1}&t_{2}&\cdots&t_{n}\end{pmatrix}$
$\in\mathfrak{S}_{n}$, where each element in the first row of $p$ denotes an
agent ID and each element in the second row of $p$ denotes a task ID. If it is
clear from the context, we simply denote $p$ as a one-line notation
$t_{1}\,t_{2}\,\cdots\,t_{n}\in\mathfrak{S}_{n}$. For example, task
assignments in the task swapping graphs in Fig. 4(a) and Fig. 5(a) are
represented by $2\,5\,6\,3\,1\,4\,8\,7$ and $5\,4\,2\,1\,6\,9\,7\,8\,3$,
respectively. Let $p\in\mathfrak{S}_{n}$ be a permutation representing a task
assignment in $\Gamma$. Then, we denote this labeled task swapping graph
$\Gamma$ as $\Gamma_{p}$. Now, we define a task swapping of swapping distance
$k$ in $\Gamma_{p}$. A task swapping of swapping distance $k$ is the swapping
of tasks between agents whose distance is $k$ in $\Gamma_{p}$. Recall that a
right multiplication of permutation $p$ by transposition $(a\,b)$ exchanges
the values in position $a$ and position $b$ of $p$. It follows that a task
swapping of swapping distance $k$ in $\Gamma_{p}$ is represented by a right
multiplication of $p$ by transposition
$t=(i(v_{1})\,i(v_{2}))\in\mathfrak{S}_{n}$, where the distance between vertex
$v_{1}$ and vertex $v_{2}$ is $k$ and $i(v)$ denotes the agent ID for vertex
$v$ in $\Gamma_{p}$. Therefore, it converts $\Gamma_{p}$ into $\Gamma_{pt}$,

A _task swapping network_ is simply a distributed network represented by a
task swapping graph $\Gamma$. In this paper a task swapping network is
referred to as a task swapping graph $\Gamma$ unless otherwise stated. Based
on the assumptions and the problem formulation in Section 2, the problem is
now reduced and rephrased by using a task swapping graph $\Gamma$:

Given a source task assignment $t_{1}$ and a feasible target task assignment
$t_{2}$ in a task swapping graph $\Gamma$, find a minimum-length sequence of
adjacent task swappings (i.e., task swappings of swapping distance 1) needed
from $\Gamma_{t_{1}}$ to reach $\Gamma_{t_{2}}$. If $t_{1}=t_{2}$, then
nothing needs to be done. Similarly, a task swapping graph having one vertex
involves no task swapping, which returns the empty sequence. A task swapping
graph of two vertices involves only a single task swapping, which gives an
immediate solution. In the remainder of this paper we assume that $t_{1}\neq
t_{2}$ and a task swapping graph has at least three vertices unless otherwise
stated.

Fig. 4: Task swapping graphs of line topology.

We find the solution of the problem for task swapping graphs of several key
topologies. We first find the solution of the problem for a task swapping
graph of line topology.

Line topology [21, 31, 32, 10] is one of the simplest interconnection network
topologies, where each agent is connected to exactly two neighboring agents
other than the two end agents that are connected to only one neighboring agent
(see Fig. 4). We assume that each agent in a task swapping graph of line
topology is labeled in ascending order from left to right as shown in Fig. 4.
A task swapping graph of line topology having $n$ agents with their task
assignment represented by permutation $p\in\mathfrak{S}_{n}$ is denoted as
$\Gamma_{p}^{L(n)}$. For example, a task swapping graph of Fig. 4(a) is
denoted as $\Gamma_{p_{1}}^{L(8)}$ and a task swapping graph of Fig. 4(b) is
denoted as $\Gamma_{p_{2}}^{L(8)}$, respectively, where
$p_{1}=2\,5\,6\,3\,1\,4\,8\,7\in\mathfrak{S}_{8}$ and
$p_{2}=1\,6\,2\,3\,4\,5\,7\,8\in\mathfrak{S}_{8}$. Recall that a right
multiplication of permutation $p$ by transposition $(i\,i+1)$ exchanges the
values in position $i$ and position $i+1$ of $p$. Since only adjacent task
swappings are allowed, we use the generating set $S_{1}=\\{(i\,i+1):1\leq
i<n\\}$ to find a minimum-length sequence of adjacent task swappings needed
from $\Gamma_{\pi_{1}}^{L(n)}$ for $\pi_{1}\in\mathfrak{S}_{n}$ to reach
$\Gamma_{\pi_{2}}^{L(n)}$ for $\pi_{2}\in\mathfrak{S}_{n}$. For example, the
number of the minimum adjacent task swappings needed from
$\Gamma_{p_{1}}^{L(8)}$ in Fig. 4(a) to reach $\Gamma_{p_{2}}^{L(8)}$ in Fig.
4(b) is the minimum length of a permutation factorization of
${p_{1}}^{-1}p_{2}$ using the generating set $S_{1}^{\prime}=\\{(i\,i+1):1\leq
i<8\\}$. Observe that ${p_{1}}^{-1}p_{2}$ takes $p_{1}$ to $p_{2}$, i.e.,
$p_{1}({p_{1}}^{-1}p_{2})=(p_{1}{p_{1}}^{-1})p_{2}=p_{2}$. Equivalently, it is
viewed as taking $p_{2}^{-1}p_{1}$ to the identity permutation $I$, i.e.,
$p_{2}^{-1}p_{1}({p_{1}}^{-1}p_{2})=I$. Thus, a minimum-length permutation
factorization of ${p_{1}}^{-1}p_{2}$ using the generating set $S_{1}^{\prime}$
corresponds to a shortest path from vertex $p_{2}^{-1}p_{1}$ to vertex $I$ in
the bubble sort Cayley graph $\text{BS}_{8}$. Thus, it is reduced to find a
shortest path from $p_{2}^{-1}p_{1}=3\,6\,2\,4\,1\,5\,8\,7$ to permutation $I$
in the bubble sort Cayley graph $\text{BS}_{8}$:
$3\,6\,2\,4\,1\,5\,8\,7\xrightarrow{<2,3>}3\,2\,6\,4\,1\,5\,8\,7$$\xrightarrow{<3,4>}3\,2\,4\,6\,1\,5\,8\,7\xrightarrow{<4,5>}3\,2\,4\,1\,6\,5\,8\,7$$\xrightarrow{<5,6>}3\,2\,4\,1\,5\,6\,8\,7\xrightarrow{<7,8>}3\,2\,4\,1\,5\,6\,7\,8$$\xrightarrow{<1,2>}2\,3\,4\,1\,5\,6\,7\,8\xrightarrow{<3,4>}2\,3\,1\,4\,5\,6\,7\,8$$\xrightarrow{<2,3>}2\,1\,3\,4\,5\,6\,7\,8\xrightarrow{<1,2>}1\,2\,3\,4\,5\,6\,7\,8$,
where the label of each arrow denotes an edge in $\text{BS}_{8}$. Therefore,
${p_{1}}^{-1}p_{2}={(p_{2}^{-1}p_{1})}^{-1}=(2\,3)(3\,4)(4\,5)(5\,6)(7\,8)(1\,2)(3\,4)(2\,3)(1\,2)$.
It follows that the resulting minimum-length sequence of adjacent task
swappings needed from $\Gamma_{p_{1}}^{L(8)}$ to reach $\Gamma_{p_{2}}^{L(8)}$
is $((2\,3)$, $(3\,4)$, $(4\,5)$, $(5\,6)$, $(7\,8)$, $(1\,2)$, $(3\,4)$,
$(2\,3)$, $(1\,2))$. It is interpreted as a sequence of task swappings so that
a task swapping between agents in the first term (agent 2 and agent 3) is
followed by a task swapping between agents in the second term (agent 3 and
agent 4), and so on, until arriving at a task swapping between agents in the
last term (agent 1 and agent 2) of the sequence. We see that the length of the
sequence is 9, implying that at least 9 adjacent task swappings are needed
from $\Gamma_{p_{1}}^{L(8)}$ to reach $\Gamma_{p_{2}}^{L(8)}$. Algorithm 1
describes the procedure of converting $\Gamma_{\pi_{1}}^{L(n)}$ into
$\Gamma_{\pi_{2}}^{L(n)}$ by using a minimum-length sequence of adjacent task
swappings. It is known from group theory that the minimum length of
permutation $p\in\mathfrak{S}_{n}$ using the generating set $S_{1}$ is the
_inversion number_ [33, 28] of $p$, where the inversion number of $p$ is
defined as $|\\{(i,j):i<j,p(i)>p(j)\\}|$. The maximum inversion number of
permutations of $n$ elements is $n(n-1)/2$, which corresponds to permutation
$n\,n-1\,\cdots\,2\,1$ [33]. Now, the minimum number of adjacent task
swappings needed from $\Gamma_{\pi_{1}}^{L(n)}$ for
$\pi_{1}\in\mathfrak{S}_{n}$ to reach $\Gamma_{\pi_{2}}^{L(n)}$ for
$\pi_{2}\in\mathfrak{S}_{n}$ is the inversion number of
${\pi_{1}}^{-1}\pi_{2}$ (or ${\pi_{2}}^{-1}\pi_{1})$. It follows that the
least upper bound of the minimum number of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{L(n)}$ to reach $\Gamma_{\pi_{2}}^{L(n)}$ is $n(n-1)/2$,
which is the maximum inversion number of permutations of $n$ elements. We also
see that it coincides the diameter of bubble sort Cayley graph
$\text{BS}_{n}$.

Input: A source and a target task assignment in a task swapping graph of line
topology $\Gamma_{\pi_{1}}^{L(n)}$ and $\Gamma_{\pi_{2}}^{L(n)}$,
respectively.

Output: A minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{L(n)}$ to reach $\Gamma_{\pi_{2}}^{L(n)}$.

begin

Find a minimum-length permutation factorization of $\pi_{1}^{-1}\pi_{2}$ using
a shortest path from vertex $\pi_{2}^{-1}\pi_{1}$ to vertex $I$ in the bubble-
sort Cayley graph $\text{BS}_{n}$;

Obtain a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{L(n)}$ to reach $\Gamma_{\pi_{2}}^{L(n)}$ by using the
above permutation factorization of $\pi_{1}^{-1}\pi_{2}$;

end

Algorithm 1 A task reassignment by using adjacent task swappings in a task
swapping graph of line topology

In Algorithm 1 222An alternative method to find a minimum-length permutation
factorization of permutation $\pi\in\mathfrak{S}_{n}$ using the generating set
$S_{1}=\\{(i\,i+1):1\leq i<n\\}$ is to apply _numbers game_ [34, 35] of finite
Coxeter group of type $A_{n-1}$ [36, 33]. An interested reader may refer to
[34, 35, 36, 33] for further details., we do not need to generate every
bubble-sort Cayley graph $\text{BS}_{n}$ to find a shortest path from vertex
$\pi_{2}^{-1}\pi_{1}$ to vertex $I$. If a right multiplication of
$\pi_{2}^{-1}\pi_{1}$ by an adjacent transposition reduces an inversion number
by 1, the vertex of the resulting permutation comes closer to vertex $I$ in
terms of a distance in $\text{BS}_{n}$ in which permutation $I$ has the 0
inversion number [33, 26]. By swapping adjacent out-of-order elements in the
permutation using the bubble-sort algorithm, it reduces an inversion number by
1. Therefore, we may apply a bubble-sort algorithm of $O(n^{2})$ complexity
[28] to $\pi_{2}^{-1}\pi_{1}$ in order to keep track of a shortest path from
vertex $\pi_{2}^{-1}\pi_{1}$ to vertex $I$ as shown by the example in this
section. Note that a minimum-length sequence of adjacent task swappings needed
from $\Gamma_{\pi_{1}}^{L(n)}$ to reach $\Gamma_{\pi_{2}}^{L(n)}$ is not
necessarily unique. However, the length of a minimum-length sequence is
unique, which is the inversion number of permutation $\pi_{2}^{-1}\pi_{1}$. It
is also the distance from vertex $\pi_{2}^{-1}\pi_{1}$ to vertex $I$ in
$\text{BS}_{n}$.

Fig. 5: Task swapping graphs of star topology.

######  Proposition 4.1.

An upper bound for the minimum number of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{L(n)}$ for $\pi_{1}\in\mathfrak{S}_{n}$ to reach
$\Gamma_{\pi_{2}}^{L(n)}$ for $\pi_{2}\in\mathfrak{S}_{n}$ is $n(n-1)/2$.

######  Proof 1.

Reduction from the diameter of Cayley graph $\text{BS}_{n}$ [27, 25] and from
Algorithm 1. ∎

We next discuss a task swapping graph of star topology. A star topology
consists of a supervisor agent and worker agents, where a supervisor agent
communicates directly to worker agents and each worker agent communicates
indirectly to other worker agent(s) [37, 21, 38]. We assume that a task
swapping graph of star topology having $n\,(n\geq 3)$ agents is labeled in
such a way that a supervisor agent is labeled 1 and worker agents are labeled
in ascending order (clockwise) starting from 2 to $n$. A task swapping graph
of star topology having $n$ agents with their task assignment represented by
permutation $p\in\mathfrak{S}_{n}$ is denoted as $\Gamma_{p}^{S(n)}$. For
example, a task swapping graph of Fig. 5(a) is denoted as
$\Gamma_{p_{1}}^{S(9)}$ and a task swapping graph of Fig. 5(b) is denoted as
$\Gamma_{p_{2}}^{S(9)}$, respectively, where
$p_{1}=5\,4\,2\,1\,6\,9\,7\,8\,3\in\mathfrak{S}_{9}$ and
$p_{2}=7\,8\,9\,2\,4\,5\,1\,6\,3\in\mathfrak{S}_{9}$. Let
$p\in\mathfrak{S}_{n}$ be a permutation representing a task assignment in
$\Gamma_{p}^{S(n)}$. We see that a right multiplication of permutation $p$ by
a _star transposition_ [39, 40] $(1\,i)$ for $2\leq i\leq n$ exchanges the
values in position $1$ (a supervisor agent’s position) of $p$ and position $i$
(a worker agent’s position) of $p$. Therefore, to find a minimum-length
sequence of adjacent task swappings needed from $\Gamma_{\pi_{1}}^{S(n)}$ for
$\pi_{1}\in\mathfrak{S}_{n}$ to reach $\Gamma_{\pi_{2}}^{S(n)}$ for
$\pi_{2}\in\mathfrak{S}_{n}$ is equivalent to finding a minimum-length
permutation factorization of $\pi_{1}^{-1}\pi_{2}$ using the generating set
$S_{3}=\\{(1\,i):2\leq i\leq n\\}$. Observe that every non-identity
permutation is denoted as a product of disjoint cycles, one of which includes
element 1. Therefore, a non-identity permutation $\pi\in\mathfrak{S}_{n}$ is
expressed as $\pi=(1\,q_{2}\cdots q_{s})(p_{1}^{1}\cdots
p_{l_{1}}^{1})\cdots(p_{1}^{m}\cdots p_{l_{m}}^{m})\in\mathfrak{S}_{n}$ if
$s\geq 2$ [40]. If a cycle including element 1 is a cycle of length 1, then
permutation $\pi\in\mathfrak{S}_{n}$ is expressed as $\pi=(p_{1}^{1}\cdots
p_{l_{1}}^{1})\cdots(p_{1}^{m}\cdots p_{l_{m}}^{m})\in\mathfrak{S}_{n}$. It is
easily verified that $(1\,q_{2}\cdots q_{s})$ in $\pi$ for $s\geq 2$ is
factorized into $(1\,q_{s})(1\,q_{s-1})\cdots(1\,q_{2})$ using the generating
set $S_{3}$, whose length is $s-1$. Similarly, if $l_{k}\geq 2$, then
$(p_{1}^{k}\cdots p_{l_{k}}^{k})$ in $\pi$ is factorized into
$(1\,p_{1}^{k})$$(1\,p_{l_{k}}^{k})(1\,p_{l_{k}-1}^{k})\cdots(1\,p_{1}^{k})$
of length $l_{k}+1$ using the generating set $S_{3}$ [40]. It turns out these
factorizations are minimal in the sense that no other way of factorizations
can have less length when using the generating set $S_{3}$ [40]. Therefore,
the minimum length of the above $\pi\in\mathfrak{S}_{n}$ using the generating
set $S_{3}$ is $n+m-k-1$, where $k$ is the number of cycle(s) of length 1. For
example, if $\pi=(1\,2\,3\,4)(5\,6\,7)\in\mathfrak{S}_{8}$, then $\pi$ is
factorized into $\pi=(1\,4)(1\,3)(1\,2)(1\,5)(1\,7)(1\,6)(1\,5)$ using the
generating set $S_{3}^{\prime}=\\{(1\,i):2\leq i\leq 8\\}$, whose length is
$8+1-1-1=7$.

Input: A source and a target task assignment in a task swapping graph of star
topology $\Gamma_{\pi_{1}}^{S(n)}$ and $\Gamma_{\pi_{2}}^{S(n)}$,
respectively.

Output: A minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{S(n)}$ to reach $\Gamma_{\pi_{2}}^{S(n)}$.

begin

Compute $\pi_{1}^{-1}\pi_{2}$ and set it as $\pi$;

Denote $\pi$ as a product of disjoint cycles such that $(1\,q_{2}\cdots
q_{s})(p_{1}^{1}\cdots p_{l_{1}}^{1})\cdots(p_{1}^{m}\cdots
p_{l_{m}}^{m})\in\mathfrak{S}_{n}$ if $s\geq 2$. Denote $\pi$ as
$(p_{1}^{1}\cdots p_{l_{1}}^{1})\cdots(p_{1}^{m}\cdots
p_{l_{m}}^{m})\in\mathfrak{S}_{n}$ otherwise;

if  _$s\geq 3$_ then

$(1\,q_{2}\cdots q_{s})$ in $\pi$ is factorized into
$(1\,q_{s})(1\,q_{s-1})\cdots(1\,q_{2})$;

end if

for  _$k\leftarrow 1$ to $m$_ do

if  _$l_{k}\geq 2$_ then

$(p_{1}^{k}\cdots p_{l_{k}}^{k})$ in $\pi$ is factorized into
$(1\,p_{1}^{k})$$(1\,p_{l_{k}}^{k})(1\,p_{l_{k}-1}^{k})\cdots(1\,p_{1}^{k})$;

end if

end for

Obtain a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{S(n)}$ to reach $\Gamma_{\pi_{2}}^{S(n)}$ by using the
above permutation factorization of $\pi_{1}^{-1}\pi_{2}$;

end

Algorithm 2 A task reassignment by using adjacent task swappings in a task
swapping graph of star topology

Algorithm 2 describes the procedure of converting $\Gamma_{\pi_{1}}^{S(n)}$
into $\Gamma_{\pi_{2}}^{S(n)}$ by using a minimum-length sequence of adjacent
task swappings. For example, we find a minimum-length sequence of adjacent
task swappings needed from $\Gamma_{p_{1}}^{S(9)}$ to reach
$\Gamma_{p_{2}}^{S(9)}$ in Fig. 5, where
$p_{1}=5\,4\,2\,1\,6\,9\,7\,8\,3\in\mathfrak{S}_{9}$ and
$p_{2}=7\,8\,9\,2\,4\,5\,1\,6\,3\in\mathfrak{S}_{9}$. A simple computation
shows that
$p_{1}^{-1}p_{2}=7\,8\,6\,3\,2\,1\,4\,5\,9=(1\,7\,4\,3\,6)(2\,8\,5)\in\mathfrak{S}_{9}$.
We factorize $p_{1}^{-1}p_{2}$ into a product of star transpositions, i.e.,
$p_{1}^{-1}p_{2}=(1\,6)(1\,3)(1\,4)(1\,7)(1\,2)(1\,5)(1\,8)(1\,2)$ by applying
Algorithm 2. Now, a minimum-length sequence of adjacent task swappings needed
from $\Gamma_{p_{1}}^{S(9)}$ to reach $\Gamma_{p_{2}}^{S(9)}$ is $((1\,6)$,
$(1\,3)$, $(1\,4)$, $(1\,7)$, $(1\,2)$, $(1\,5)$, $(1\,8)$, $(1\,2))$ of
length 8.

Observe that a sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{S(n)}$ to reach $\Gamma_{\pi_{2}}^{S(n)}$ in Algorithm 2
corresponds to a path from vertex $\pi_{2}^{-1}\pi_{1}$ to vertex $I$ in a
star graph $\text{ST}_{n}$. Therefore, an upper bound of the minimum number of
adjacent task swappings needed from $\Gamma_{\pi_{1}}^{S(n)}$ to reach
$\Gamma_{\pi_{2}}^{S(n)}$ in Algorithm 2 is the diameter of a star graph
$\text{ST}_{n}$, which is $\lfloor 3(n-1)/2\rfloor$ [26, 27].

######  Proposition 4.2.

An upper bound for the minimum number of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{S(n)}$ for $\pi_{1}\in\mathfrak{S}_{n}$ to reach
$\Gamma_{\pi_{2}}^{S(n)}$ for $\pi_{2}\in\mathfrak{S}_{n}$ is $\lfloor
3(n-1)/2\rfloor$.

######  Proof 2.

Reduction from the diameter of Cayley graph $\text{ST}_{n}$ [27, 26] and from
Algorithm 2. ∎

Fig. 6: Task swapping graphs of complete topology.

A task swapping graph of complete topology is a fully-connected task swapping
graph in which each agent has direct links with all other agents in the
topology. Although the complete topology provides redundancy in terms of
communication links between pairs of agents, the cost is often too high when
setting up communication links between agents in the topology (i.e.,
$n(n-1)/2$ total communication links are required for $n$ agents in the
complete topology) [37, 21]. A task swapping graph of complete topology having
$n$ agents with their task assignment represented by permutation
$p\in\mathfrak{S}_{n}$ is denoted as $\Gamma_{p}^{C(n)}$. For example, a task
swapping graph of Fig. 6(a) is denoted as $\Gamma_{p_{1}}^{C(6)}$ and a task
swapping graph of Fig. 6(b) is denoted as $\Gamma_{p_{2}}^{C(6)}$,
respectively, where $p_{1}=1\,3\,4\,2\,6\,5\in\mathfrak{S}_{6}$ and
$p_{2}=1\,5\,6\,3\,2\,4\in\mathfrak{S}_{6}$. Since each agent has direct links
with all other agents in the complete topology, an adjacent task swapping may
occur between any pair of agents in the topology. Now, to find a minimum-
length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{C(n)}$ to reach $\Gamma_{\pi_{2}}^{C(n)}$ is reduced to
find a minimum-length permutation factorization of $\pi_{1}^{-1}\pi_{2}$ using
the generating set $S_{4}=\\{(i\,j):1\leq i<j\leq n\\}$. Verify that each
cycle $(q_{1}\,q_{2}\cdots q_{l})$ of length $l>2$ can be factorized into a
product of $l-1$ transpositions
$(q_{1}\,q_{l})(q_{1}\,q_{l-1})\cdots(q_{1}\,q_{2})$. It is known from group
theory that a cycle of length $l>2$ cannot be written as a product of fewer
than $l-1$ transpositions in the generating set $S_{4}$ [41, 42]. Thus, a
minimum-length permutation factorization of $\pi_{1}^{-1}\pi_{2}$ is obtained
by first denoting it as a product of disjoint cycles, then factorizing all the
cycle(s) of length greater than 2 using the generating set $S_{4}$ as
described.

Input: A source and a target task assignment in a task swapping graph of
complete topology $\Gamma_{\pi_{1}}^{C(n)}$ and $\Gamma_{\pi_{2}}^{C(n)}$,
respectively.

Output: A minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{C(n)}$ to reach $\Gamma_{\pi_{2}}^{C(n)}$.

begin

Compute $\pi_{1}^{-1}\pi_{2}$ and set it as $\pi$;

Denote $\pi$ as a product of disjoint cycles such that $(q_{1}^{1}\,\cdots
q_{l_{1}}^{1})(q_{1}^{2}\cdots q_{l_{2}}^{2})\cdots(q_{1}^{m}\cdots
q_{l_{m}}^{m})\in\mathfrak{S}_{n}$;

for  _$k\leftarrow 1$ to $m$_ do

if  _$l_{k}\geq 3$_ then

$(q_{1}^{k}\,q_{2}^{k}\cdots q_{l}^{k})$ in $\pi$ is factorized into
$(q_{1}^{k}\,q_{l}^{k})\cdots(q_{1}^{k}\,q_{2}^{k})$;

end if

end for

Obtain a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{C(n)}$ to reach $\Gamma_{\pi_{2}}^{C(n)}$ by using the
above permutation factorization of $\pi_{1}^{-1}\pi_{2}$;

end

Algorithm 3 A task reassignment by using adjacent task swappings in a task
swapping graph of complete topology

Algorithm 3 describes the procedure of converting $\Gamma_{\pi_{1}}^{C(n)}$
into $\Gamma_{\pi_{2}}^{C(n)}$ by using a minimum-length sequence of adjacent
task swappings. We see that a minimum length of permutation
$\pi\in\mathfrak{S}_{n}$ using the generating set $S_{4}$ is $n-r$, where
$\pi$ consists of $r$ disjoint cycles.

Now, we find a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{p_{1}}^{C(6)}$ to reach $\Gamma_{p_{2}}^{C(6)}$ in Fig. 6, where
$p_{1}=1\,3\,4\,2\,6\,5\in\mathfrak{S}_{6}$ and
$p_{2}=1\,5\,6\,3\,2\,4\in\mathfrak{S}_{6}$. A direct computation shows that
$p_{1}^{-1}p_{2}=1\,6\,5\,2\,4\,3=(2\,6\,3\,5\,4)\in\mathfrak{S}_{6}$. Then,
we factorize $p_{1}^{-1}p_{2}$ as a product of transpositions, i.e.,
$p_{1}^{-1}p_{2}=(2\,4)$$(2\,5)$$(2\,3)$$(2\,6)$ by applying Algorithm 3.
Therefore, a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{p_{1}}^{C(6)}$ to reach $\Gamma_{p_{2}}^{C(6)}$ is $((2\,4)$,
$(2\,5)$, $(2\,3)$, $(2\,6))$ of length 4.

In Section 3 we discussed that a Cayley graph of $\mathfrak{S}_{n}$ generated
by $S_{4}=\\{(i\,j):1\leq i<j\leq n\\}$ is the complete transposition graph
$\text{CT}_{n}$. It follows that a sequence of adjacent task swappings needed
from $\Gamma_{\pi_{1}}^{C(n)}$ to reach $\Gamma_{\pi_{2}}^{C(n)}$ in Algorithm
3 corresponds to a path from vertex $\pi_{2}^{-1}\pi_{1}$ to vertex $I$ in the
complete transposition graph $\text{CT}_{n}$. To find a shortest path from
vertex $\pi_{2}^{-1}\pi_{1}$ to vertex $I$ in $\text{CT}_{n}$ [27], one may
apply a greedy algorithm to transpose and locate each element in the
permutation to its homed position iteratively from left to right until
arriving at $I$. For example, a shortest path from vertex
$p_{2}^{-1}p_{1}={(p_{1}^{-1}p_{2})}^{-1}=1\,4\,6\,5\,3\,2\in\mathfrak{S}_{6}$
to vertex $I$ in $\text{CT}_{6}$ is as follows:
$1\,4\,6\,5\,3\,2\xrightarrow{<2,4>}1\,5\,6\,4\,3\,2\xrightarrow{<2,5>}1\,3\,6\,4\,5\,2$$\xrightarrow{<2,3>}1\,6\,3\,4\,5\,2\xrightarrow{<2,6>}1\,2\,3\,4\,5\,6$,
where the label of each arrow denotes an edge in $\text{CT}_{6}$. Therefore,
${p_{1}}^{-1}p_{2}={(p_{2}^{-1}p_{1})}^{-1}=(2\,4)$$(2\,5)$$(2\,3)$$(2\,6)$,
which coincides the above permutation factorization of ${p_{1}}^{-1}p_{2}$
using the generating set $S_{4}$.

It follows that an upper bound for the minimum number of adjacent task
swappings needed from $\Gamma_{\pi_{1}}^{C(n)}$ to reach
$\Gamma_{\pi_{2}}^{C(n)}$ in Algorithm 3 is the diameter of a complete
transposition graph $\text{CT}_{n}$, which is $n-1$ [27].

######  Proposition 4.3.

An upper bound for the minimum number of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{C(n)}$ for $\pi_{1}\in\mathfrak{S}_{n}$ to reach
$\Gamma_{\pi_{2}}^{C(n)}$ for $\pi_{2}\in\mathfrak{S}_{n}$ is $n-1$.

######  Proof 3.

Reduction from the diameter of Cayley graph $\text{CT}_{n}$ [27, 25] and from
Algorithm 3. ∎

Fig. 7: Task swapping graphs of complete bipartite topology.

Recall that a graph is _bipartite_ if its vertex set admits a partition into
two classes in such a way that every edge has its ends in two different
classes [43, 44]. A _complete bipartite graph_ [44] is a bipartite graph in
which every two vertices from two different classes are adjacent. A task
swapping graph of _complete bipartite topology_ [37, 45] is a complete
bipartite task swapping graph, where agents are grouped in two layers or
classes (the upper and lower) in such a way that agents between different
layers are fully-connected, while agents in the same layer are not directly
connected. The agents at the upper layer have a centralized control over the
agents at the lower layer in a distributed manner in this topology. We assume
that each agent in a task swapping graph of complete bipartite topology is
labeled in ascending order from the upper left to bottom right as shown in
Fig. 7. A task swapping graph of complete bipartite topology having $n$ agents
with their task assignment represented by permutation $p\in\mathfrak{S}_{n}$
is denoted as $\Gamma_{p}^{B(n,k)}$, where $k$ is the number of agents at the
upper layer in $\Gamma_{p}^{B(n,k)}$. We call $k$ as _bipartite index_. As
with other task swapping graphs, we assume $n\geq 3$ for
$\Gamma_{p}^{B(n,k)}$. We also assume $1\leq k<n$ for $\Gamma_{p}^{B(n,k)}$.
Note that $\Gamma_{p}^{B(n,k)}$ is simply $\Gamma_{p}^{S(n)}$ when bipartite
index $k$ is 1. For example, the task swapping graph of Fig. 7(a) is denoted
as $\Gamma_{p_{1}}^{B(8,3)}$ and the task swapping graph of Fig. 7(b) is
denoted as $\Gamma_{p_{2}}^{B(8,3)}$, respectively, where
$p_{1}=3\,7\,1\,6\,5\,4\,8\,2\in\mathfrak{S}_{8}$ and
$p_{2}=2\,4\,7\,8\,6\,1\,3\,5\in\mathfrak{S}_{8}$. We see that a right
multiplication of permutation $p_{1}\in\mathfrak{S}_{8}$ by transposition
$(1\,4)$ represents an adjacent task swapping between agent 1 and agent 4 in
$\Gamma_{p_{1}}^{B(8,3)}$, while a right multiplication of permutation
$p_{1}\in\mathfrak{S}_{8}$ by transposition $(1\,2)$ does not represent an
adjacent task swapping in $\Gamma_{p_{1}}^{B(8,3)}$. Therefore, the generating
set $S_{5}^{\prime}=\\{(i\,j):1\leq i\leq 3<j\leq 8\\}$ is required for
finding a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{p_{1}}^{B(8,3)}$ to reach $\Gamma_{p_{2}}^{B(8,3)}$.

We next find a minimum-length permutation factorization of
$\pi_{1}^{-1}\pi_{2}$ using the generating set $S_{5}=\\{(i\,j):1\leq i\leq
k<j\leq n\\}$ by which we obtain a minimum-length sequence of adjacent task
swappings needed from $\Gamma_{\pi_{1}}^{B(n,k)}$ for
$\pi_{1}\in\mathfrak{S}_{n}$ to reach $\Gamma_{\pi_{2}}^{B(n,k)}$ for
$\pi_{2}\in\mathfrak{S}_{n}$. We consider several types of cycles to factorize
$\pi_{1}^{-1}\pi_{2}$ using the generating set $S_{5}=\\{(i\,j):1\leq i\leq
k<j\leq n\\}$. Set $\pi=\pi_{1}^{-1}\pi_{2}$ and represent it as a product of
(commutative) disjoint cycles $C_{s}$ for $1\leq s\leq t$ such that
$\pi=C_{1}\cdots C_{i}C_{i+1}\cdots C_{e}C_{e+1}\cdots C_{t}$, where each
element in each cycle of $C_{1}\cdots C_{i}$ is less than or equal to
(bipartite index) $k$, each element in each cycle of $C_{i+1}\cdots C_{e}$ is
greater than $k$, and each cycle of $C_{e+1}\cdots C_{t}$ has both element(s)
less than or equal to $k$ and element(s) greater than $k$. We first consider
the first type of a cycle, referred to as an _internal cycle_ [45], which is a
cycle in $C_{1}\cdots C_{i}$ of $\pi$. Let $C_{x}$ be an internal cycle such
that $C_{x}=(c_{1}\,c_{2}\,\cdots\,c_{v})$, where $1\leq c_{u}\leq k$ for
$1\leq u\leq v$. Then, $C_{x}$ is factorized into
$(c_{1}\,t)(c_{v}\,t)\cdots(c_{2}\,t)(c_{1}\,t)$ using the generating set
$S_{5}=\\{(i\,j):1\leq i\leq k<j\leq n\\}$, where $t$ is an arbitrary number
satisfying $k<t\leq n$. We next consider the second type of a cycle, referred
to as an _external cycle_ [45], which is a cycle in $C_{i+1}\cdots C_{e}$ of
$\pi$. Let $C_{y}$ be an external cycle, i.e.,
$C_{y}=(c_{1}\,\cdots\,c_{q-1}\,c_{q})$, where $k<c_{p}\leq n$ for $1\leq
p\leq q$. Then, $C_{y}=(c_{1}\,\cdots\,c_{q-1}\,c_{q})$ is factorized into
$(u\,c_{q})(u\,c_{q-1})\cdots(u\,c_{1})(u\,c_{q})$ using the generating set
$S_{5}$, where $u$ is an arbitrary number satisfying $1\leq u\leq k$. Now, we
consider the final type of a cycle, referred to as a _mixed cycle_ [45], which
is a cycle in $C_{e+1}\cdots C_{t}$ of $\pi$. Each mixed cycle $C_{m}$ for
$e+1\leq m\leq t$ is written as $(E_{m_{1}}E_{m_{2}}\cdots E_{m_{s}})$, where
each $E_{m_{i}}$ for $1\leq i\leq s$ can be denoted as a concatenation of two
blocks of numbers [45]. Each number of the first block of $E_{m_{i}}$ for
$1\leq i\leq s$ is less than or equal to $k$, while each number of the second
block of $E_{m_{i}}$ for $1\leq i\leq s$ is greater than $k$. We call
$E_{m_{i}}$ as a _simple cycle_. For example, a mixed cycle
$C_{m}^{\prime}=(1\,3\,4\,5\,7\,2\,6\,8)\in\mathfrak{S}_{8}$ for $k=3$ is
written as $(E_{m_{1}}^{\prime}E_{m_{2}}^{\prime})$, where
$E_{m_{1}}^{\prime}=1\,3\,4\,5\,7$ and $E_{m_{2}}^{\prime}=2\,6\,8$. It
follows that the first block of $E_{m_{1}}^{\prime}$ is $1\,3$, while the
second block of $E_{m_{1}}^{\prime}$ is $4\,5\,7$.

Let $E_{m_{i}}=i_{1}\,i_{2}\cdots i_{a}\,j_{1}\,j_{2}\cdots j_{b}$, where
$1\leq i_{u}\leq k$ for $1\leq u\leq a$ and $k<j_{v}\leq n$ for $1\leq v\leq
b$. Observe that $(E_{m_{i}})$ is factorized into
$(i_{1}\,j_{b})\cdots(i_{1}\,j_{2})(i_{a}\,j_{1})\cdots(i_{2}\,j_{1})(i_{1}\,j_{1})$
using the generating set $S_{5}$. For example,
$(1\,3\,4\,5\,7)\in\mathfrak{S}_{8}$ is factorized into
$(1\,7)(1\,5)(3\,4)(1\,4)$ using the generating set
$S_{5}^{\prime}=\\{(i\,j):1\leq i\leq 3<j\leq 8\\}$. Further, observe that a
mixed cycle $C_{m}^{\prime}=(E_{m_{1}}^{\prime}E_{m_{2}}^{\prime})$ is written
as $(1\,2)(E_{m_{1}}^{\prime})(E_{m_{2}}^{\prime})$, where 1 in $(1\,2)$ is
the first element in $E_{m_{1}}^{\prime}$ and 2 in $(1\,2)$ is the first
element in $E_{m_{2}}^{\prime}$. Thus,
$C_{m}^{\prime}=(E_{m_{1}}^{\prime}E_{m_{2}}^{\prime})=(1\,2)(E_{m_{1}}^{\prime})(E_{m_{2}}^{\prime})=(1\,2)(1\,7)(1\,5)(3\,4)(1\,4)(2\,8)(2\,6)$.
However, $(1\,2)$ in $C_{m}^{\prime}$ is not a transposition in
$S_{5}^{\prime}$. Therefore, we use a transposition $(1\,7)$ next to $(1\,2)$
and convert $(1\,2)(1\,7)$ into $(1\,7)(2\,7)$ in which transposition $(1\,7)$
and transposition $(2\,7)$ are transpositions in $S_{5}^{\prime}$.

In general $C_{m}=(E_{m_{1}}E_{m_{2}}\cdots E_{m_{s}})$ is recursively
factorized into $C_{m}=(v_{1}\,v_{2})(E_{m_{1}})(E_{m_{2}}\cdots E_{m_{s}})$,
where $v_{1}$ is the first element of $E_{m_{1}}$ and $v_{2}$ is the first
element of $E_{m_{2}}$ [45]. Let $(w_{1}\,w_{2})$ be the first transposition
of a factorization of $E_{m_{1}}$ using the generating set $S_{5}$. Then, we
have $v_{1}=w_{1}$. Now, we see that $E_{m_{1}}$ is factorized using
transpositions in the generating set $S_{5}$ such that
$(v_{1}\,v_{2})(w_{1}\,w_{2})$ with $v_{1}=w_{1}$ is rearranged into
$(v_{1}\,w_{2})(v_{2}\,w_{2})$. Therefore, $C_{m}$ is recursively factorized
using transpositions in the generating set $S_{5}$. Furthermore, it turns out
that the above way of factorizing an arbitrary permutation
$p\in\mathfrak{S}_{n}$ using the generating set $S_{5}$ for a given $1\leq
k<n$ yields the length of $p$ not greater than $n-1+\max{(\lfloor
k/2\rfloor,\lfloor(n-k)/2\rfloor)}$ [45]. Algorithm 4 describes the procedure
of converting $\Gamma_{\pi_{1}}^{B(n,k)}$ into $\Gamma_{\pi_{2}}^{B(n,k)}$ by
using a minimum-length sequence of adjacent task swappings. Now, we obtain a
minimum-length sequence of adjacent task swappings needed from a task swapping
graph $\Gamma_{p_{1}}^{B(8,3)}$ in Fig. 7(a) to reach a task swapping graph
$\Gamma_{p_{2}}^{B(8,3)}$ in Fig. 7(b), where
$p_{1}=3\,7\,1\,6\,5\,4\,8\,2\in\mathfrak{S}_{8}$ and
$p_{2}=2\,4\,7\,8\,6\,1\,3\,5\in\mathfrak{S}_{8}$. We first compute
$p_{1}^{-1}p_{2}$, which is
$8\,6\,2\,7\,4\,3\,1\,5=(1\,8\,5\,4\,7)(3\,2\,6)\in\mathfrak{S}_{8}$. Then, we
factorize $p_{1}^{-1}p_{2}$ using the generating set $S_{5}^{\prime}$. Observe
that $p_{1}^{-1}p_{2}$ is the product of simple cycles $(E_{1})(E_{2})$, where
$E_{1}=1\,8\,5\,4\,7$ and $E_{2}=3\,2\,6$. Then,
$(E_{1})=(1\,7)(1\,4)(1\,5)(1\,8)$ and $(E_{2})=(2\,6)(3\,6)$. Therefore, a
minimum-length sequence of adjacent task swapping needed from
$\Gamma_{p_{1}}^{B(8,3)}$ in Fig. 7(a) to reach $\Gamma_{p_{2}}^{B(8,3)}$ in
Fig. 7(b) is $((1\,7),(1\,4),(1\,5),(1\,8),(2\,6),(3\,6))$ of length 6.

Input: A source and a target task assignment in a task swapping graph of
complete bipartite topology $\Gamma_{\pi_{1}}^{B(n,k)}$ and
$\Gamma_{\pi_{2}}^{B(n,k)}$, respectively.

Output: A minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{B(n,k)}$ to reach $\Gamma_{\pi_{2}}^{B(n,k)}$.

begin

Compute $\pi_{1}^{-1}\pi_{2}$ and set it as $\pi$;

Write $\pi$ as a product of disjoint cycles $C_{m}$ for $1\leq m\leq t$ such
that $\pi=C_{1}\cdots C_{i}C_{i+1}\cdots C_{e}C_{e+1}\cdots C_{t}$, where each
cycle of $C_{1}\cdots C_{i}$ is an internal cycle, each cycle of
$C_{i+1}\cdots C_{e}$ is an external cycle, and each cycle of $C_{e+1}\cdots
C_{t}$ is a mixed cycle;

for  _$m\leftarrow 1$ to $t$_ do

if  _$C_{m}$ is an $r$-cycle for $r\geq 3$_ then

//  see Alogorithm 5 BipartiteCycleFactorization ($C_{m}$, $k$);

end if

end for

Obtain a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{B(n,k)}$ to reach $\Gamma_{\pi_{2}}^{B(n,k)}$ by using the
above permutation factorization of $\pi_{1}^{-1}\pi_{2}$;

end

Algorithm 4 A task reassignment by using adjacent task swappings in a task
swapping graph of complete bipartite topology

Input: An $r$-cycle $C_{m}$ ($3\leq r\leq n$) and bipartite index $k$ ($1\leq
k<n$).

Output: A factorization of $C_{m}$ into a product of transpositions in
$S_{5}$.

begin

if  _$C_{m}$ is an internal cycle_ then

Let $C_{m}=(c_{1}\,c_{2}\,\cdots\,c_{v})$. Then, $C_{m}$ is factorized into
$(c_{1}\,t)(c_{v}\,t)\cdots(c_{2}\,t)(c_{1}\,t)$, where $t$ is any number in
$k<t\leq n$;

end if

else if  _$C_{m}$ is an external cycle_ then

Let $C_{m}=(c_{1}\,\cdots\,c_{q-1}\,c_{q})$. Then, $C_{m}$ is factorized into
$(u\,c_{q})(u\,c_{q-1})\cdots(u\,c_{1})(u\,c_{q})$, where $u$ is any number in
$1\leq u\leq k$.

end if

else // $C_{m}$ is a mixed cycle

if  _$C_{m}$ is a simple cycle_ then

Let $C_{m}=(i_{1}\,i_{2}\cdots i_{a}\,j_{1}\,j_{2}\cdots j_{b})$, where $1\leq
i_{u}\leq k$ for $1\leq u\leq a$ and $k<j_{v}\leq n$ for $1\leq v\leq b$.
Then, $C_{m}$ is factorized into
$(i_{1}\,j_{b})\cdots(i_{1}\,j_{2})(i_{a}\,j_{1})\cdots(i_{2}\,j_{1})(i_{1}\,j_{1})$;

end if

else

Let $C_{m}=(E_{m_{1}}E_{m_{2}}\cdots E_{m_{t}})$, where each $(E_{m_{i}})$ for
$1\leq i\leq t$ is a simple cycle. Then,
$C_{m}=(v_{1}\,v_{2})(E_{m_{1}})(E_{m_{2}}\cdots E_{m_{t}})$, where $v_{1}$
and $v_{2}$ are the first elements of $E_{m_{1}}$ and $E_{m_{2}}$,
respectively. Factorize a simple cycle $(E_{m_{1}})$ as indicated above. Let
$(w_{1}\,w_{2})$ be the first transposition of a factorization of $E_{m_{1}}$.
If $v_{1}=w_{1}$, rearrange $(v_{1}\,v_{2})(w_{1}\,w_{2})$ into
$(w_{1}\,w_{2})(v_{2}\,w_{2})$. Otherwise, rearrange
$(v_{1}\,v_{2})(w_{1}\,w_{2})$ into
$(w_{1}\,w_{2})(v_{2}\,w_{2})(v_{1}\,w_{2})(v_{2}\,w_{2})$. Then, $C_{m}$ is
written as a product of transpositions in $S_{5}$ followed by
$(E_{m_{2}}\cdots E_{m_{t}})$. We repeat this process recursively to
$(E_{m_{2}}\cdots E_{m_{t}})$ until we completely factorize $C_{m}$ using
$S_{5}$.

end if

end if

end

Algorithm 5 A bipartite cycle factorization using the generating set
$S_{5}=\\{(i\,j):1\leq i\leq k<j\leq n\\}$ [45]

As discussed in Section 3, a Cayley graph of $\mathfrak{S}_{n}$ generated by
$S_{5}=\\{(i\,j):1\leq i\leq k<j\leq n\\}$ is the generalized star graph
$\text{GST}_{n,k}$. Therefore, an upper bound of the minimum number of
adjacent task swappings needed from $\Gamma_{\pi_{1}}^{B(n,k)}$ for
$\pi_{1}\in\mathfrak{S}_{n}$ to reach $\Gamma_{\pi_{2}}^{B(n,k)}$ for
$\pi_{2}\in\mathfrak{S}_{n}$ in Algorithm 4 is the diameter of a generalized
star graph $\text{GST}_{n,k}$, which is $n-1+\max{(\lfloor
k/2\rfloor,\lfloor(n-k)/2\rfloor)}$ [45].

######  Proposition 4.4.

An upper bound for the minimum number of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{B(n,k)}$ for $\pi_{1}\in\mathfrak{S}_{n}$ to reach
$\Gamma_{\pi_{2}}^{B(n,k)}$ for $\pi_{2}\in\mathfrak{S}_{n}$ is
$n-1+\max{(\lfloor k/2\rfloor,\lfloor(n-k)/2\rfloor)}$.

######  Proof 4.

Reduction from the diameter of Cayley graph $\text{GST}_{n,k}$ [25, 45], a
bipartite cycle factorization algorithm given in [45], and Algorithm 4. ∎

Fig. 8: Task swapping graphs of ring topology.

A task swapping graph of ring topology is a circular task swapping graph in
which each agent has direct links with exactly two other agents in the
topology. In case any direct link of two agents is removed, a ring topology is
changed into a line topology [21]. We assume that a task swapping graph of
ring topology having $n$ agents for $n\geq 3$ is labeled in such a way that
$n$ agents are labeled clockwise in ascending order starting from 1 to $n$
(see Fig. 8). Now, we denote a task swapping graph of ring topology having $n$
agents with their task assignment represented by permutation
$p\in\mathfrak{S}_{n}$ as $\Gamma_{p}^{R(n)}$. We call the corresponding
permutation $p\in\mathfrak{S}_{n}$ for $\Gamma_{p}^{R(n)}$ as a _circular
permutation_ [46] in which position $i$ of a circular permutation
$p\in\mathfrak{S}_{n}$ is referred to as verex (agent) $i$ for $1\leq i\leq n$
in $\Gamma_{p}^{R(n)}$. For example, a task swapping graph of Fig. 8(a) is
denoted as $\Gamma_{p_{1}}^{R(8)}$ and a task swapping graph of Fig. 8(b) is
denoted as $\Gamma_{p_{2}}^{R(8)}$, respectively, where
$p_{1}=5\,7\,3\,4\,8\,2\,6\,1\in\mathfrak{S}_{8}$ and
$p_{2}=3\,2\,8\,4\,7\,1\,5\,6\in\mathfrak{S}_{8}$.

Now, observe that a minimum-length sequence of adjacent task swappings needed
from $\Gamma_{\pi_{1}}^{R(n)}$ to reach $\Gamma_{\pi_{2}}^{R(n)}$ is obtained
by finding a minimum-length permutation factorization of $\pi_{1}^{-1}\pi_{2}$
using the generating set $S_{6}=\\{(i\,i+1):1\leq i<n\\}\cup\\{(1\,n)\\}$.
Note that adjacent task swappings in $\Gamma_{p}^{R(n)}$ are adjacent task
swappings in $\Gamma_{p}^{L(n)}$ along with an adjacent task swapping between
agent 1 and agent $n$.

A _displacement vector_ [29, 46] $d=(d_{1},d_{2},d_{3},\ldots,d_{n})$ of a
circular permutation $p\in\mathfrak{S}_{n}$ is introduced to sort a circular
permutation $p$ into $I$ using the generating set $S_{6}=\\{(i\,i+1):1\leq
i<n\\}\cup\\{(1\,n)\\}$ by which we obtain a permutation factorization of $p$
using the same generating set. Each component $d_{i}$ in $d$ is defined as
$d_{i}=j-i$, where $p(j)=i$ for $1\leq i,j\leq n$. For any displacement vector
$d=(d_{1},d_{2},d_{3},\ldots,d_{n})$, we have $\sum_{i=1}^{n}{d_{i}}=0$, and
each $d_{i}=0$ if $d$ is a displacement vector of the identity permutation of
$\mathfrak{S}_{n}$. For example, a displacement vector of a circular
permutation $5\,7\,3\,4\,8\,2\,6\,1\in\mathfrak{S}_{8}$ in Fig. 8(a) is
$(7,4,0,0,-4,1,-5,-3)$. Intuitively, each $|d_{i}|$ in $d$ is interpreted as
the length of a path from position (vertex) $i$ to position (vertex) $k$ on
which element $i$ is placed for a circular permutation $p\in\mathfrak{S}_{n}$,
where $d_{i}$ is signed positive if the path from position $i$ to position $k$
is clockwise, and signed negative if the path from position $i$ to position
$k$ is counterclockwise. We denote the corresponding path as
$\text{path}(d_{i})$, which is uniquely determined by $d_{i}$ of its circular
permutation $p\in\mathfrak{S}_{n}$. Let $d_{s}$ be the maximum-valued
component of a displacement vector $d$ of a circular permutation
$p\in\mathfrak{S}_{n}$, and $d_{t}$ be the minimum-valued component of the
displacement vector $d$. Since $\sum_{i=1}^{n}{d_{i}}=0$, $d_{s}$ is greater
than 0 and $d_{t}$ is less than 0 for any non-identity circular permutation
$p\in\mathfrak{S}_{n}$. If $d_{s}-d_{t}>n$ for each pair of indices $s$ and
$t$, then we renew $d_{s}$ as $d_{s}-n$ and $d_{t}$ as $d_{t}+n$,
respectively. This process is called _strictly contracting transformation_
[46]. If a displacment vector $d$ admits no strictly contracting
transformation, we say that a displacement vector $d$ is _stable_ , denoted
$\bar{d}$. For example, the maximum and minimum component values of
displacement vector $d^{\prime}=(7,4,0,0,-4,1,-5,-3)$ of the circular
permutation $5\,7\,3\,4\,8\,2\,6\,1\in\mathfrak{S}_{8}$ in Fig. 8(a) are
$d_{1}^{\prime}=7$ and $d_{7}^{\prime}=-5$, respectively. Since
$d_{1}^{\prime}-d_{7}^{\prime}=12>8$, we renew $d_{1}^{\prime}$ as
$d_{1}^{\prime}=7-8=-1$, and $d_{7}^{\prime}=-5+8=3$. This procedure continues
until we obtain a stable displacement vector $\bar{d}^{\prime}$, i.e., no pair
of maximum-valued component $d_{s}^{\prime}$ and the minimum-valued component
$d_{t}^{\prime}$ of $d^{\prime}$ satisfies $d_{s}^{\prime}-d_{t}^{\prime}>8$.
We leave it for the reader to verify that
$\bar{d}^{\prime}=(-1,4,0,0,-4,1,3,-3)$.

The value $\sum_{i=1}^{n}{|d_{i}|}$ of a stable displacement vector $\bar{d}$
of a circular permutation $p\in\mathfrak{S}_{n}$ is a key indicator of how
close a circular permutation $p\in\mathfrak{S}_{n}$ is to the identity
permutation in terms of a length using the generating set $S_{6}$. Note that
$\sum_{i=1}^{n}{|d_{i}|}$ is not zero for any non-identity permutation in
$\mathfrak{S}_{n}$, while $\sum_{i=1}^{n}{|d_{i}|}$ is 0 for the identity
permutation. By using a stable displacement vector $\bar{d}$, an inversion
number $I(\bar{d})$ is defined as
$I(\bar{d})=|\\{(i,j):(i+\bar{d_{i}}>j+\bar{d_{j}})\cup(i+\bar{d_{i}}+n<j+\bar{d_{j}}),\;1\leq
i<j\leq n\\}|$, which is the minimum length of a permutation factorization of
$p\in\mathfrak{S}_{n}$ using the generating set $S_{6}=\\{(i\,i+1):1\leq
i<n\\}\cup\\{(1\,n)\\}$ [29]. Now, at each step of sorting a circular
permutation $p\in\mathfrak{S}_{n}$ into $I$, we find an adjacent swapping to
reduce an inversion number by 1. Observe that if an adjacent pair of positions
(vertices) $v_{1}$ and $v_{2}$ have elements $s$ and $t$, respectively, such
that $\text{path}(s)$ and $\text{path}(t)$ are directed oppositely having an
intersection of edge $(v_{1},v_{2})$, then swapping elements $s$ and $t$ on
vertices $v_{1}$ and $v_{2}$ reduces an inversion number by 1. Observe also
the case where an adjacent pair of vertices $v_{1}$ and $v_{2}$ have elements
$s$ and $t$, respectively, such that $s$ is homed (i.e., $p(s)=s$) and $t$ is
not homed. If $\text{path}(t)$ crosses vertex $v_{1}$, then swapping elements
$s$ and $t$ on vertices $v_{1}$ and $v_{2}$ reduces an inversion number by 1.
Now, each step of the sorting procedure is to find an adjacent swapping that
reduces an inversion number by 1. As stated earlier in this section, if
$\bar{d}$ is a stable displacement vector of a circular permutation
$p\in\mathfrak{S}_{n}$, then the inversion number $I(\bar{d})$ is the minimum
length of a permutation factorization of $p$ using the generating set $S_{6}$.
Therefore, $I(\bar{d})$ is the minimum number of adjacent swappings required
for sorting a circular permutation $p\in\mathfrak{S}_{n}$ to the identity
permutation $I$ using the generating set $S_{6}$.

Input: A source and a target task assignment in a task swapping graph of ring
topology $\Gamma_{\pi_{1}}^{R(n)}$ and $\Gamma_{\pi_{2}}^{R(n)}$,
respectively.

Output: A minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{R(n)}$ to reach $\Gamma_{\pi_{2}}^{R(n)}$.

// Find a minimum-length permutation factorization of $\pi_{1}^{-1}\pi_{2}$ by
sorting $\pi_{2}^{-1}\pi_{1}$ to the identity permutation $I$ using the
generating set $S_{6}=\\{(i\,i+1):1\leq i<n\\}\cup\\{(1\,n)\\}$ begin

Let $\pi=\pi_{2}^{-1}\pi_{1}\in\mathfrak{S}_{n}$. Find a stable displacement
vector $\bar{d}$ of $\pi$, and calculate the inversion number $I(\bar{d})$;

while  _$\pi\neq I$_ do

In a circular permutation $\pi\in\mathfrak{S}_{n}$ in $\Gamma_{\pi}^{R(n)}$,
find an adjacent pair of vertices $v_{1}$ and $v_{2}$ having elements $s$ and
$t$, respectively, such that $\text{path}(s)$ and $\text{path}(t)$ derived
from its stable displacement vector of $\pi$ are directed oppositely having an
intersection of edge $(v_{1},v_{2})$. If no such an adjacent pair exists, then
find an adjacent pair of vertices $v_{1}$ and $v_{2}$ having elements $s$ and
$t$, respectively, such that $s$ is homed (i.e., $\pi(s)=s$) and $t$ is not
homed in which $\text{path}(t)$ crosses vertex $v_{1}$;

Swap elements $s$ and $t$ on vertices $v_{1}$ and $v_{2}$, replacing $\pi$
with the resulting permutation. Compute a stable displacement vector of the
(updated) circular permutation $\pi$;

end while

Obtain a minimum-length sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{R(n)}$ to reach $\Gamma_{\pi_{2}}^{R(n)}$ by using the
above permutation factorization of $\pi_{1}^{-1}\pi_{2}$;

end

Algorithm 6 A task reassignment by using adjacent task swappings in a task
swapping graph of ring topology

Algorithm 6 describes the procedure of converting $\Gamma_{\pi_{1}}^{R(n)}$
into $\Gamma_{\pi_{2}}^{R(n)}$ by using a minimum-length sequence of adjacent
task swappings. By using Algorithm 6, we obtain a minimum-length sequence of
adjacent task swappings needed from a task swapping graph
$\Gamma_{p_{1}}^{R(8)}$ in Fig. 8(a) to reach a task swapping graph
$\Gamma_{p_{2}}^{R(8)}$ in Fig. 8(b), where
$p_{1}=5\,7\,3\,4\,8\,2\,6\,1\in\mathfrak{S}_{8}$ and
$p_{2}=3\,2\,8\,4\,7\,1\,5\,6\in\mathfrak{S}_{8}$. A direct computation shows
that $p_{2}^{-1}p_{1}$ is $7\,5\,1\,4\,3\,2\,8\,6$ and its stable displacement
vector is $(2,-4,2,0,-3,2,2,-1)$. An adjacent swapping between 7th position
(element 8) and 8th position (element 6) of $p_{2}^{-1}p_{1}$ reduces an
inversion number by 1. This sorting procedure is continued by using Algorithm
6 until arriving at the identity permutation (see below):

$7\,5\,1\,4\,3\,2\,8\,6\xrightarrow{<7,8>}7\,5\,1\,4\,3\,2\,6\,8$$\xrightarrow{<2,3>}7\,1\,5\,4\,3\,2\,6\,8\xrightarrow{<6,7>}7\,1\,5\,4\,3\,6\,2\,8$$\xrightarrow{<3,4>}7\,1\,4\,5\,3\,6\,2\,8\xrightarrow{<4,5>}7\,1\,4\,3\,5\,6\,2\,8$$\xrightarrow{<7,8>}7\,1\,4\,3\,5\,6\,8\,2\xrightarrow{<1,8>}2\,1\,4\,3\,5\,6\,8\,7$$\xrightarrow{<1,2>}1\,2\,4\,3\,5\,6\,8\,7\xrightarrow{<7,8>}1\,2\,4\,3\,5\,6\,7\,8$$\xrightarrow{<3,4>}1\,2\,3\,4\,5\,6\,7\,8$.

Now, we have the resulting minimum-length sequence of adjacent task swappings
needed from $\Gamma_{p_{1}}^{R(8)}$ to reach $\Gamma_{p_{2}}^{R(8)}$, which is
$((7\,8)$, $(2\,3)$, $(6\,7)$, $(3\,4)$, $(4\,5)$, $(7\,8)$, $(1\,8)$,
$(1\,2)$, $(7\,8)$, $(3\,4))$ of length 10.

Note that an upper bound of the number of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{R(n)}$ to reach $\Gamma_{\pi_{2}}^{R(n)}$ is subject to the
diameter of the modified bubble-sort graph $MBS_{n}$ discussed in Section 3.
To the best of our knowledge, the formula of the diameter of $MBS_{n}$ is not
known [46, 27, 47]. Nevertheless, a minimum-length sequence of sorting an
aribtrary circular permutation $p\in\mathfrak{S}_{n}$ into the identity
permutation $I$ using the generating set $S_{6}=\\{(i\,i+1):1\leq
i<n\\}\cup\\{(1\,n)\\}$ in Algorithm 6 is obtained in polynomial time [29]. It
follows that Algorithm 6 runs in polynomial time as with other algorithms
involving permutation sortings discussed in this paper.

Input: A source and a target task assignment in a task swapping graph of an
arbitrary tree topology $\Gamma_{\pi_{1}}^{T(n)}$ and
$\Gamma_{\pi_{2}}^{T(n)}$, respectively.

Output: A sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{T(n)}$ to reach $\Gamma_{\pi_{2}}^{T(n)}$ in the number
$c(\pi)-n+\sum_{i=1}^{n}{d(i,\pi(i))}$ of steps, where
$\pi=\pi_{2}^{-1}\pi_{1}$, $c(\pi)$ is the number of cycles in $\pi$, and
$d(i,j)$ is the distance between agent $i$ and agent $j$ in
$\Gamma_{\pi}^{T(n)}$.

begin

Let $\pi=\pi_{2}^{-1}\pi_{1}$ and start the procedure of sorting
$\Gamma_{\pi}^{T(n)}$ to $\Gamma_{I}^{T(n)}$;

while  _$\pi\neq I$_ do

In $\Gamma_{\pi}^{T(n)}$ find an adjacent pair of agents $a_{1}$ and $a_{2}$
such that their unhomed tasks $t_{1}$ and $t_{2}$, respectively, need to move
toward each other for their homed positions (i.e., $\pi(t_{k})=t_{k}$ for
$k=1$ and $k=2$). Or find an adjacent pair of agents $a_{1}$ and $a_{2}$ such
that its task $t_{1}$ is homed and its task $t_{2}$ is not homed,
respectively, in which task $t_{2}$ needs to move toward and cross agent
$a_{1}$ for its homed position (i.e., $\pi(t_{2})=t_{2}$). Then, swap task
$t_{1}$ on agent $a_{1}$ and task $t_{2}$ on agent $a_{2}$, replacing $\pi$
with the resulting permutation;

end while

Obtain a sequence of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{T(n)}$ to reach $\Gamma_{\pi_{2}}^{T(n)}$ by using the
above sorting procedure;

end

Algorithm 7 A task reassignment by using adjacent task swappings in a task
swapping graph of an arbitrary tree topology

Finally, we discuss a task swapping graph of an arbitrary tree topology that
has not been discussed in this section. A task swapping graph of a tree
topology having $n$ agents with their task assignment represented by
permutation $p\in\mathfrak{S}_{n}$ is denoted as $\Gamma_{p}^{T(n)}$. We
concern the procedure of converting a source task assignment in
$\Gamma_{\pi_{1}}^{T(n)}$ to a target task assignment in
$\Gamma_{\pi_{2}}^{T(n)}$ by using the minimum number of adjacent task
swappings.

Due to Corollary 3.1, we may not always obtain a tight upper bound for the
number of steps to convert $\Gamma_{\pi_{1}}^{T(n)}$ into
$\Gamma_{\pi_{2}}^{T(n)}$ for $\pi_{1}\in\mathfrak{S}_{n}$ and
$\pi_{2}\in\mathfrak{S}_{n}$. However, we may apply Theorem 3.2 to convert
$\Gamma_{\pi_{1}}^{T(n)}$ into $\Gamma_{\pi_{2}}^{T(n)}$ in the number
$c(\pi)-n+\sum_{i=1}^{n}{d(i,\pi(i))}$ of steps, where
$\pi=\pi_{2}^{-1}\pi_{1}$, $c(\pi)$ is the number of cycles in $\pi$, and
$d(i,j)$ is the distance between position (vertex) $i$ and position (vertex)
$j$ in $\Gamma_{\pi}^{T(n)}$. Algorithm 7 describes the procedure of
converting $\Gamma_{\pi_{1}}^{T(n)}$ into $\Gamma_{\pi_{2}}^{T(n)}$ in the
above number of steps.

######  Proposition 4.5.

An upper bound for the number of adjacent task swappings needed from
$\Gamma_{\pi_{1}}^{T(n)}$ for $\pi_{1}\in\mathfrak{S}_{n}$ to reach
$\Gamma_{\pi_{2}}^{T(n)}$ for $\pi_{2}\in\mathfrak{S}_{n}$ is
$c(\pi)-n+\sum_{i=1}^{n}{d(i,\pi(i))}$, where $\pi=\pi_{2}^{-1}\pi_{1}$ and
$c(\pi)$ is the number of cycles in $\pi$.

######  Proof 5.

Reduction from Theorem 3.2, Corollary 3.1, and Algorithm 7. ∎

##  5 Conclusions

This paper presented task swapping networks of several basic topologies used
in distributed systems. Task swappings between adjacent agents in a network
topology are represented by task swappings of swapping distance 1 in the
corresponding task swapping graph. We considered the situation in which the
total cost of task migrations relies on the number of adjacent task swappings
involved in a given network topology. Minimum generator sequence algorithms
using several known generating sets for $\mathfrak{S}_{n}$ allow us to find a
minimum-length sequence of adjacent task swappings needed from a source task
assignment to reach a target task assignment in a task swapping graph of
several topologies, such as line, star, complete, complete bipartite, and
ring.

Task swapping graphs of the more complex topologies (e.g., 2D and 3D meshes,
hypercubes, etc) along with task swappings of swapping distance $k\geq 2$ have
not been discussed in this paper. We leave them to our future works.

## References

  * [1] S. Ramakrishnan, I.-H. Cho, L. A. Dunning, A Close Look at Task Assignment in Distributed Systems, in: INFOCOM ’91, IEEE, 1991, pp. 806–812.
  * [2] A. S. Tanenbaum, Distributed Operating Systems, Prentice Hall, 1995.
  * [3] K. G. Shin, M.-S. Chen, On the Number of Acceptable Task Assignments in Distributed Computing Systems, IEEE Transactions on Computers 39 (1990) 99–110.
  * [4] D. S. Miloj́ičić, F. Douglis, Y. Paindaveine, R. Wheeler, S. Zhou, Process migration, ACM Computing Surveys 32 (2000) 241–299.
  * [5] J. Robinson, S. H. Russ, B. Heckel, B. Flachs, A Task Migration Implementation of the Message-Passing Interface, in: Proceedings of the 5th IEEE International Symposium on High Performance Distributed Computing, 1996, pp. 61–68.
  * [6] N. Jennings, M. Wooldridge, Software Agents, IEE Review 42 (1) (1996) 17–20.
  * [7] H. S. Nwana, Software Agents: An Overview, Knowledge Engineering Review 11 (1996) 205–244.
  * [8] P. Kalinowski, R. Katarzyniak, Methods of Task Redistribution in Multiagent Systems, in: Agent and Multi-Agent Systems: Technologies and Applications, Vol. 6070, 2010, pp. 72–81.
  * [9] L. Chen, C.-L. Wang, F. C. M. Lau, Process reassignment with reduced migration cost in grid load rebalancing., in: IEEE International Parallel and Distributed Processing Symposium, 2008, pp. 1–13.
  * [10] M. M. Zavlanos, L. Spesivtsev, G. J. Pappas, A distributed auction algorithm for the assignment problem, in: Proceedings of 47th IEEE Conference on Decision and Control, 2008, pp. 1212–1217.
  * [11] N. S. Bowen, C. N. Nikolaou, A. Ghafoor, On the assignment problem of arbitrary process systems to heterogeneous distributed computer systems, Transactions on Computers 41 (3) (1992) 257–273.
  * [12] M. M. Zavlanos, G. J. Pappas, Distributed Formation Control with Permutation Symmetries, in: IEEE Conference on Decision and Control, 2007, pp. 2894–2899.
  * [13] R. Burkard, M. Dell’Amico, S. Martello, Assignment Problems, Society for Industrial and Applied Mathematics, 2009.
  * [14] J. E. Rowe, M. D. Vose, A. H. Wright, Group properties of crossover and mutation, Evolutionary Computation 10 (2002) 151–184.
  * [15] D. Kim, Representations of task assignments in distributed systems using young tableaux and symmetric groups, arXiv.org arXiv:1012.1288 [cs.DC].
URL http://arxiv.org/abs/1012.1288v3

  * [16] T. Enokido, M. Takizawa, Group Communication Protocol for Autonomic Computing, in: International Conference on Parallel and Distributed Systems, 2005, pp. 443–447.
  * [17] G. Aggarwal, R. Motwani, A. Zhu, The load rebalancing problem, in: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, 2003, pp. 258–265.
  * [18] L. Chen, C.-L. Wang, F. C. M. Lau, Process reassignment with reduced migration cost in grid load rebalancing., in: IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2008, 2008, pp. 1–13.
  * [19] C. Du, X.-H. Sun, M. Wu, Dynamic Scheduling with Process Migration, in: Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, 2007, pp. 92–99.
  * [20] Y. F. Hu, R. J. Blake, D. R. Emerson, An optimal migration algorithm for dynamic load balancing, Concurrency: Practice and Experience (1998) 467–483.
  * [21] H. L. Zhang, C. H. C. Leung, G. K. Raikundalia, Classification of Intelligent Agent Network Topologies and a New Topological Description Language for Agent Networks, in: Intelligent Information Processing, 2006, pp. 21–31.
  * [22] K. P. Sycara, Multiagent systems, AI Magazine 19 (2) (1998) 79–92.
  * [23] J. B. Fraleigh, A First Course in Abstract Algebra, Addison-Wesley, Reading, 1998\.
  * [24] T. Hungerford, Algebra, 2nd Edition, Springer-Verlag, 1980.
  * [25] M. Heydemann, Cayley Graphs and Interconnection Networks, in: Graph Symmetry: Algebraic Methods and Applications, Springer, 1997, pp. 167–224.
  * [26] S. B. Akers, B. Krishnamurthy, A Group-Theoretic Model for Symmetric Interconnection Networks, IEEE Transactions on Computers 38 (1989) 555–566.
  * [27] S. Lakshmivarahan, J.-S. Jwo, S. K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Computing 19 (4) (1993) 361–407.
  * [28] D. E. Knuth, The art of computer programming. Vol. 3: Sorting and searching, Addison-Wesley Publishing Company, 1973.
  * [29] M. Jerrum, The complexity of finding minimum-length generator sequences, Theoretical Computer Science 36 (1985) 265–289.
  * [30] C. Enyioha, D. Tarraf, L. Li, J. C. Doyle, On the graph of trees, in: IEEE Multiconference on Systems and Control, 2009, pp. 246–248.
  * [31] Y. Gong, M. Nakamura, T. Matsumura, K.Onaga, A distributed parallel genetic local search with tree-based migration on irregular network topologies, IEICE transactions, on Fundamentals of Electronics, Communications and Computer Sciences E87-A (6) (2004) 1377–1385.
  * [32] Y. Gong, M. Nakamura, S. Tamaki, Parallel genetic algorithms on line topology of heterogeneous computing resources, in: GECCO ’05, Proceedings of the 2005 conference on Genetic and evolutionary computation, 2005, pp. 1447–1454.
  * [33] A. Garsia, The Saga of Reduced Factorizations of Elements of the Symmetric Group, Publications du LaCIM 29, Université du Québec á Montréal (2002).
  * [34] A. Björner, F. Brenti, Combinatorics of Coxeter Groups, Springer, 2005.
  * [35] H. Eriksson, Computational and combinatorial aspects of Coxeter groups, Ph.D. thesis, KTH, Stockholm, Sweden (1994).
  * [36] B. E. Tenner, The combinatorics of reduced decompositions, Ph.D. thesis, MIT, Cambridge, United States (2006).
  * [37] Q. Zhu, Topologies of agents interactions in knowledge intensive multi-agent systems for networked information services, Advanced Engineering Informatics 20 (2006) 31–45.
  * [38] H. El-Rewini, T. G. Lewis, Distributed and Parellel Computing, Manning Publications, 1998.
  * [39] I. Pak, Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and $k$-ARY trees, Discrete Mathematics 204 (1999) 329–335.
  * [40] J. Irving, A. Rattan, Factorizations of Permutations into Star Transpositions, Discrete Mathematics 309 (2009) 1435–1442.
  * [41] D. Neuenschwander, On the Representation of Permutations as Products of Transpositions, Elemente der Mathematik 56 (2001) 1–3.
  * [42] G. Mackiw, Permutations as Products of Transpositions, The American Mathematical Monthly 102 (1995) 438–440.
  * [43] N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1974.
  * [44] R. Diestel, Graph Theory, 3rd Edition, Springer, 2005.
  * [45] H. Zhu, Z. Sun, New classes of interconnection topology structures and their properties, Wuhan University Journal of Natural Sciences 1 (1996) 371–385.
  * [46] X. Feng, B. Chitturi, H. Sudborough, Sorting Circular Permutations by Bounded Transpositions, in: Advances in Computational Biology, Vol. 680, 2011, pp. 725–736.
  * [47] L. Stacho, I. Vrt’o, Bisection width of transposition graphs, Discrete Applied Mathematics 84 (1-3) (1998) 221–235.