TY - JOUR
T1 - Communication and location discovery in geometric ring networks
AU - Gąsieniec, Leszek
AU - Jurdzinski, Tomasz
AU - Martin, Russell
AU - Stachowiak, Grzegorz
N1 - Funding Information:
This work was supported by Polish National Science Centre grant DEC-2012/06/M/ST6/00459 and, in the final stage, by grant 2017/25/B/ST6/02010 .
Funding Information:
This work was supported by Polish National Science Centre grant DEC-2012/06/M/ST6/00459 and, in the final stage, by grant 2017/25/B/ST6/02010.L. Gąsieniec and R. Martin acknowledge the support of the Networks Sciences and Technology (NeST) Initiative in the School of Electrical Engineering, Electronics and Computer Science at the University of Liverpool.
Funding Information:
This work was supported by Polish National Science Centre grant DEC-2012/06/M/ST6/00459 and, in the final stage, by grant 2017/25/B/ST6/02010. L. G?sieniec and R. Martin acknowledge the support of the Networks Sciences and Technology (NeST) Initiative in the School of Electrical Engineering, Electronics and Computer Science at the University of Liverpool. The authors also gratefully acknowledge anonymous reviewers for their valuable comments and suggestions improving the results and quality of presentation.
Publisher Copyright:
© 2018
PY - 2019/6
Y1 - 2019/6
N2 - We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronized rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., when an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that n mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The location discovery task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem. Assuming that agents are anonymous (there are no IDs distinguishing them), our solution applied to randomly chosen IDs from appropriately chosen range gives an (almost) optimal algorithm, improving upon the complexity of previous randomized results.
AB - We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronized rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., when an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that n mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The location discovery task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem. Assuming that agents are anonymous (there are no IDs distinguishing them), our solution applied to randomly chosen IDs from appropriately chosen range gives an (almost) optimal algorithm, improving upon the complexity of previous randomized results.
KW - Boundary patrolling
KW - Combinatorial structures
KW - Distributed algorithms
KW - Location discovery
KW - Mobile robots
UR - http://www.scopus.com/inward/record.url?scp=85058681727&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85058681727&partnerID=8YFLogxK
U2 - 10.1016/j.ic.2018.12.001
DO - 10.1016/j.ic.2018.12.001
M3 - Article
AN - SCOPUS:85058681727
SN - 0890-5401
VL - 266
SP - 19
EP - 48
JO - Information and Computation
JF - Information and Computation
ER -