Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2021 Apr 22:7:e466.
doi: 10.7717/peerj-cs.466. eCollection 2021.

Compacting oblivious agents on dynamic rings

Shantanu Das  1 , Giuseppe Antonio Di Luna  2 , Daniele Mazzei  3 , Giuseppe Prencipe  3
Affiliations

Compacting oblivious agents on dynamic rings

Shantanu Das et al. PeerJ Comput Sci. .

Abstract

In this paper we investigate dynamic networks populated by autonomous mobile agents. Dynamic networks are networks whose topology can change continuously, at unpredictable locations and at unpredictable times. These changes are not considered to be faults, but rather an integral part of the nature of the system. The agents can autonomously move on the network, with the goal of solving cooperatively an assigned common task. Here, we focus on a specific network: the unoriented ring. More specifically, we study 1-interval connected dynamic rings (i.e., at any time, at most one of the edges might be missing). The agents move according to the widely used Look-Compute-Move life cycle, and can be homogenous (thus identical) or heterogenous (agents are assigned colors from a set of c > 1 colors). For identical agents, their goal is to form a compact segment, where agents occupy a continuous part of the ring and no two agents occupy the same node: we call this the Compact Configuration Problem. In the case of agents with colors, called the Colored Compact Configuration Problem, the goal is to group agents such that each group is formed by all agents having the same color, it occupies a continuous segment of the network, and groups of agents having different colors occupy distinct areas of the network. In this paper we determine the necessary conditions to solve both proposed problems. For all solvable cases, we provide algorithms for both the monochromatic and the colored version of the compact configuration problem. All our algorithms work even for the simplest model where agents have no persistent memory, no communication capabilities and do not agree on a common orientation within the network. To the best of our knowledge this is the first work on the compaction problem in a dynamic network.

Keywords: Compacting problem; Distributed computing; Dynamic networks; Mobile agents; Ring network.

PubMed Disclaimer

Conflict of interest statement

The authors declare that they have no competing interests.

Figures

Figure 1
Figure 1. Examples of configurations that are: (A) periodic with 4 axes of symmetry; (B) with a mirror symmetry, and (C) aperiodic.
Figure 2
Figure 2. Example of (A) a configuration where solving ColoredCCP with only swap of agents is not possible, and (B) a configuration that is a solution for our definition of ColoredCCP.
Figure 3
Figure 3. An asymmetric configuration where CCP is unsolvable with visibility radius R = 3.
Figure 4
Figure 4. Proof of Theorem 4. (A) Axis passes through one edge and one node. Agents move towards the elected edge. (B) One of the agents is blocked, the other moves. (C) The symmetry axis changes, as well as the elected edge. (D) Axis passes through two edges: agents move towards the elected edge. (E) One of the agents is blocked. (F) If the other agent moves, a configuration where CCP is unsolvable is reached: the axis passes through two nodes. (G) The agents have to move in the other direction. (H) The configuration is symmetric to the initial one (i.e., the configuration in (D)).
Figure 5
Figure 5. Asymmetric initial configuration. (A) |S1| = |S2|. (B) |S1| < |S2|.
Figure 6
Figure 6. (A) Definition of S1+. (B) Movement of S1+ (the arrows denotes the direction of movement).
Figure 7
Figure 7. Case 2 of Algorithm 1: the distance between S1 and S2 is 1.
Figure 8
Figure 8. Example configurations for CCP in the case of a single axis of symmetry.
Figure 9
Figure 9. Pattern 1 of Algorithm 5. The bold node represents the rally point for agents having red color. (A) The dangling agents are not blocked. They move counter-clockwise towards their rally line. (B) The dangling agents are blocked. The last agent changes direction and moves clockwise towards its rally line.
Figure 10
Figure 10. Pattern 2 of Algorithm 5. (A) The black agent switches direction. (B) The vertical striped agent switches direction.
Figure 11
Figure 11. Separating an interleaved line with h = 2 and two colors.
See this image and copyright information in PMC

References

    1. Augustine J, Pandurangan G, Robinson P. Distributed algorithmic foundations of dynamic networks. SIGACT News. 2016;47(1):69–98. doi: 10.1145/2902945.2902959. - DOI
    1. Bérard B, Lafourcade P, Millet L, Potop-Butucaru MG, Thierry-Mieg Y, Tixeuil S. Formal verification of mobile robot protocols. Distributed Computing. 2016;6(29):459–487.
    1. Bhagat S, Flocchini P, Mukhopadhyaya K, Santoro N. Weak robots performing conflicting tasks without knowing who is in their team. Proc. of the 21st International Conference on Distributed Computing and Networking (ICDCN).2020.
    1. Biely M, Robinson P, Schmid U, Schwarz M, Winkler K. Gracefully degrading consensus and k-set agreement in directed dynamic networks. 2nd International Conference on Networked Systems (NETSYS); 2015. pp. 109–124.
    1. Bournat M, Dubois S, Petit F. Gracefully degrading gathering in dynamic rings. Proc. 20th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS) 2018; 2018. pp. 349–364.

LinkOut - more resources