Synchronization of Beads on a Ring

摘要

This paper analyzes a discrete-time algorithm to synchronize an even number of agents moving clockwise and counterclockwise on a boundary. Each agent or "bead" changes direction upon encountering another bead moving in the opposite direction. Communication is sporadic: only when two beads come sufficiently close they are able to exchange information. We propose a novel algorithm based on the distributed computation of dominance regions and common speed, as well as, on a careful balancing of accelerate/decelerate strategies outside of dominance regions. Our theoretical analysis relies upon consensus algorithms tools and upon the assumption that initially half of all agents move clockwise and the other half move counterclockwise.