research-article

How to meet asynchronously at polynomial cost

Authors:

Yoann Dieudonné,

Vincent VillainAuthors Info & Claims

PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

Pages 92 - 99

https://doi.org/10.1145/2484239.2484245

Published: 22 July 2013 Publication History

Abstract

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it, but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents.

As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: team size, in which every agent has to find the total number of agents, leader election, in which all agents have to output the label of a single agent, perfect renaming in which all agents have to adopt new different labels from the set 1,...,k}, where k is the number of agents, and gossiping, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm we solve all these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents.

References

[1]

H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg and R. Reischuk,Renaming in an asynchronous environment, Journal of the ACM 37 (1990), 524--548.

Digital Library

[2]

N. Agmon and D. Peleg, Fault-tolerant gathering algorithms for autonomous mobile robots, SIAM J. Comput. 36 (2006), 56--82.

Digital Library

[3]

S. Alpern,The rendezvous search problem,SIAM J. on Control and Optimization 33 (1995), 673--683.

Digital Library

[4]

S. Alpern,Rendezvous search on labelled networks,Naval Research Logistics 49 (2002), 256--274.

[5]

S. Alpern and S. Gal,The theory of search games and rendezvous.Int. Series in Operations research and Management Science,Kluwer Academic Publisher, 2002.

[6]

J. Alpern, V. Baston, and S. Essegaier,Rendezvous search on a graph,Journal of Applied Probability 36 (1999), 223--231.

[7]

E. Anderson and R. Weber,The rendezvous problem on discrete locations,Journal of Applied Probability 28 (1990), 839--851.

[8]

E. Anderson and S. Fekete,Asymmetric rendezvous on the plane,Proc. 14th Annual ACM Symp. on Computational Geometry (1998), 365--373.

Digital Library

[9]

E. Anderson and S. Fekete,Two-dimensional rendezvous search,Operations Research 49 (2001), 107--118.

Digital Library

[10]

E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, A. Labourel, Almost optimal asynchronous rendezvous in infinite multidimensional grids, Proc. 24th International Symposium on Distributed Computing (DISC 2010), LNCS 6343, 297--311.

Digital Library

[11]

V. Baston and S. Gal,Rendezvous search when marks are left at the starting points,Naval Research Logistics 48 (2001), 722--731.

[12]

J. Chalopin, S. Das, A. Kosowski, Constructing a map of an anonymous graph: Applications of universal sequences,Proc. 14th International Conference on Principles of Distributed Systems (OPODIS 2010), 119--134.

Digital Library

[13]

M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro, Solving the robots gathering problem, Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), 1181--1196.

Digital Library

[14]

R. Cohen and D. Peleg, Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM J. Comput. 34 (2005), 1516--1528.

Digital Library

[15]

R. Cohen and D. Peleg, Convergence of autonomous mobile robots with inaccurate sensors and movements, SIAM J. Comput. 38 (2008), 276--302.

Digital Library

[16]

A. Collins, J. Czyzowicz, L. Gasieniec, A. Labourel,Tell me where I am so I can meet you sooner. Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), 502--514.

Digital Library

[17]

J. Czyzowicz, A. Kosowski and A. Pelc,How to meet when you forget: Log-space rendezvous in arbitrary graphs, Distributed Computing, 25, 165--178 (2012)

[18]

J. Czyzowicz, A. Labourel, A. Pelc, How to meet asynchronously (almost) everywhere, ACM Transactions on Algorithms 8 (2012), article 37.

Digital Library

[19]

G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro, Asynchronous deterministic rendezvous in graphs, Theoretical Computer Science, 355, 315--326 (2006)

Digital Library

[20]

A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc.Deterministic rendezvous in graphs.Algorithmica 46 (2006), 69--96.

Digital Library

[21]

Y. Dieudonné, A. Pelc, Anonymous Meeting in Networks, Proc. 24rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), 737--747.

[22]

Y. Dieudonné, A. Pelc, D. Peleg, Gathering despite mischief, Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 527--540.

Digital Library

[23]

P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer,Gathering of asynchronous oblivious robots with limited visibility,Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science(STACS 2001),Springer LNCS 2010, 247--258.

Digital Library

[24]

P. Fraigniaud, E. Lazard, Methods and problems of communication in usual networks. Discrete Applied Mathematics 53 (1994), 79--133.

Digital Library

[25]

P. Fraigniaud, A. Pelc, Deterministic rendezvous in trees with little memory, Proc. 22nd International Symposium on Distributed Computing (DISC 2008), LNCS 5218, 242--256.

Digital Library

[26]

P. Fraigniaud, A. Pelc, Delays induce an exponential memory gap for rendezvous in trees, Proc. 22nd Ann. ACM Symposium on Parallel Algorithms and Architectures (SPAA 2010), 224--232.

Digital Library

[27]

P. Fraigniaud, A. Pelc, Decidability classes for mobile agents computing, Proc. 10th Latin American Theoretical Informatics Symposium (LATIN 2012), LNCS 7256, 362--374.

Digital Library

[28]

S. Guilbault, A. Pelc, Asynchronous rendezvous of anonymous agents in arbitrary graphs, Proc. 15th International Conference on Principles of Distributed Systems (OPODIS 2011), LNCS 7109, 162--173.

Digital Library

[29]

D. Kowalski, A. Malinowski,How to meet in anonymous network,in 13th Int. Colloquium on Structural Information and Comm. Complexity,(SIROCCO 2006), Springer LNCS 4056, 44--58.

Digital Library

[30]

E. Kranakis, D. Krizanc, and P. Morin, Randomized rendez-vous with limited memory,Proc. 8th Latin American Theoretical Informatics (LATIN 2008), Springer LNCS 4957, 605--616.

Digital Library

[31]

E. Kranakis, D. Krizanc, N. Santoro and C. Sawchuk, Mobile agent rendezvous in a ring, Proc. 23rd Int. Conference on Distributed Computing Systems(ICDCS 2003), IEEE, 592--599.

Digital Library

[32]

W. Lim and S. Alpern,Minimax rendezvous on the line,SIAM J. on Control and Optimization 34 (1996), 1650--1665.

Digital Library

[33]

A. Pelc, Deterministic rendezvous in networks: A comprehensive survey, Networks 59 (2012), 331--347.

Digital Library

[34]

N.L. Lynch, Distributed algorithms, Morgan Kaufmann Publ. Inc.,San Francisco, USA, 1996.

Digital Library

[35]

O. Reingold, Undirected connectivity in log-space, Journal of the ACM 55 (2008).

Digital Library

[36]

A. Ta-Shma and U. Zwick.Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 599--608.

Digital Library

[37]

X. Yu and M. Yung, Agent rendezvous: a dynamic symmetry-breaking problem, Proc. International Colloquium on Automata,Languages, and Programming (ICALP 1996), Springer LNCS 1099, 610--621.

Digital Library

Cited By

Ozsoyeller DÖzkasap Ö(2024)Distributed asynchronous rendezvous planning on the line for multi-agent systemsFuture Generation Computer Systems10.1016/j.future.2024.06.054161(35-48)Online publication date: Dec-2024
https://doi.org/10.1016/j.future.2024.06.054
Miller APelc A(2019)Tradeoffs between cost and information for rendezvous and treasure huntJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.06.00483:C(159-167)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2015.06.004
Dieudonné YPelc A(2018)Anonymous Meeting in NetworksAlgorithmica10.1007/s00453-015-9982-074:2(908-946)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1007/s00453-015-9982-0
Show More Cited By

Index Terms

How to meet asynchronously at polynomial cost
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Time versus cost tradeoffs for deterministic rendezvous in networks
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent ...
How to meet asynchronously (almost) everywhere

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its ...
How to Meet Asynchronously at Polynomial Cost

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it but unknown to the other agent. Agents move in an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computing

July 2013

422 pages

ISBN:9781450320658

DOI:10.1145/2484239

General Chair:
Panagiota Fatourou
FORTH ICS & University of Crete, Greece
,
Program Chair:
Gadi Taubenfeld
IDC, Israel

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '13

Sponsor:

PODC '13: ACM Symposium on Principles of Distributed Computing

July 22 - 24, 2013

Québec, Montréal, Canada

Acceptance Rates

PODC '13 Paper Acceptance Rate 37 of 145 submissions, 26%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
370
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ozsoyeller DÖzkasap Ö(2024)Distributed asynchronous rendezvous planning on the line for multi-agent systemsFuture Generation Computer Systems10.1016/j.future.2024.06.054161(35-48)Online publication date: Dec-2024
https://doi.org/10.1016/j.future.2024.06.054
Miller APelc A(2019)Tradeoffs between cost and information for rendezvous and treasure huntJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.06.00483:C(159-167)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2015.06.004
Dieudonné YPelc A(2018)Anonymous Meeting in NetworksAlgorithmica10.1007/s00453-015-9982-074:2(908-946)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1007/s00453-015-9982-0
Dieudonné YPelc A(2018)Deterministic polynomial approach in the planeDistributed Computing10.1007/s00446-014-0216-528:2(111-129)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00446-014-0216-5
Kranakis EKrizanc DMarkou EPagourtzis ARamírez F(2017)Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary GraphsSOFSEM 2017: Theory and Practice of Computer Science10.1007/978-3-319-51963-0_7(79-90)Online publication date: 11-Jan-2017
https://doi.org/10.1007/978-3-319-51963-0_7
Miller APelc A(2015)Fast Rendezvous with AdviceAlgorithms for Sensor Systems10.1007/978-3-662-46018-4_5(75-87)Online publication date: 4-Jan-2015
https://doi.org/10.1007/978-3-662-46018-4_5
Elouasbi SPelc A(2015)Deterministic Rendezvous with Detection Using BeepsRevised Selected Papers of the 11th International Symposium on Algorithms for Sensor Systems - Volume 953610.1007/978-3-319-28472-9_7(85-97)Online publication date: 17-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-28472-9_7
Bouchard SDieudonné YDucourthial B(2015)Byzantine Gathering in NetworksPost-Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity - Volume 943910.1007/978-3-319-25258-2_13(179-193)Online publication date: 14-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-25258-2_13
Huus EKranakis E(2015)Rendezvous of Many Agents with Different Speeds in a CycleProceedings of the 14th International Conference on Ad-hoc, Mobile, and Wireless Networks - Volume 914310.1007/978-3-319-19662-6_14(195-209)Online publication date: 29-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-319-19662-6_14
Miller APelc AHalldórsson MDolev S(2014)Time versus cost tradeoffs for deterministic rendezvous in networksProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611473(282-290)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611473
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents