More Web Proxy on the site http://driver.im/

research-article

Delays induce an exponential memory gap for rendezvous in trees

Authors:

Pierre Fraigniaud,

Andrzej PelcAuthors Info & Claims

SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

Pages 224 - 232

https://doi.org/10.1145/1810479.1810524

Published: 13 June 2010 Publication History

Abstract

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. The two identical agents start from arbitrary nodes in the graph and move from node to node with the goal of meeting. In this paper, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically.

We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Ω(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous in arbitrary trees of size at most n. Our main result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number L of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log L + log log n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most L leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Ω(log L + log log n) bits of memory is required for rendezvous, even in the class of trees with degrees bounded by 3.

References

[1]

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

Digital Library

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

Digital Library

[7]

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

Digital Library

[8]

V. Baston and S. Gal, Rendezvous on the line when the players' initial distance isgiven by an unknown probability distribution,SIAM J. on Control and Opt. 36 (1998), 1880--1889.

Digital Library

[9]

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

[10]

S. A. Cook and C. Rackoff. Space Lower Bounds for Maze Threadability on Restricted Machines.SIAM J. Comput. 9 (1980), 636--652.

[11]

T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill 1990.

Digital Library

[12]

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

Digital Library

[13]

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

Digital Library

[14]

K. Diks, P. Fraigniaud, E. Kranakis, A. Pelc, Tree exploration with little memory, Journal of Algorithms 51 (2004), 38--63.

Digital Library

[15]

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),LNCS 2010, 247--258.

Digital Library

[16]

P. Fraigniaud and C. Gavoille.A Space Lower Bound for Routing in Trees.In 19th Annual Symp. on Theoretical Aspects of Computer Science (STACS 2002), Springer LNCS 2285, 65--75.

Digital Library

[17]

P. Fraigniaud and C. Gavoille. Routing in Trees. In 28th Int. Colloquium on Automata, Languages and Programming (ICALP 2001), Springer LNCS 2076, 757--772.

Digital Library

[18]

P. Fraigniaud and D. Ilcinkas. Digraphs Exploration with Little Memory. 21st Symp. on Theoretical Aspects of Comp. Science (STACS 2004), Springer LNCS 2996, 246--257.

[19]

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

Digital Library

[20]

S. Gal, Rendezvous search on the line,Operations Research 47 (1999), 974--976.

Digital Library

[21]

L. Gasieniec, A. Pelc, T. Radzik, X. Zhang, Tree exploration with logarithmic memory, Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 585--594.

Digital Library

[22]

A. Israeli and M. Jalfon, Token management schemes and random walks yieldself stabilizing mutual exclusion, Proc. 9th Annual ACM Symposium onPrinciples of Distributed Computing (PODC 1990), 119--131.

Digital Library

[23]

M. Kouckỳ, Universal Traversal Sequences with Backtracking, Proc. 16th IEEE Conference on Computational Complexity (2001), 21--26. (Also, to appear in J. Computer and System Sciences.)

Digital Library

[24]

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

[25]

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

[26]

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

[27]

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

Digital Library

[28]

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

Digital Library

[29]

T. Schelling,The strategy of conflict,Oxford University Press, Oxford, 1960.

[30]

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

[31]

L. Thomas,Finding your kids when they are lost,Journal on Operational Res. Soc. 43 (1992), 637--639.

[32]

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

Digital Library

Cited By

TSUCHIDA MOOSHITA FINOUE M(2020)Byzantine-Tolerant Gathering of Mobile Agents in Asynchronous Arbitrary Networks with Authenticated WhiteboardsIEICE Transactions on Information and Systems10.1587/transinf.2019EDP7311E103.D:7(1672-1682)Online publication date: 1-Jul-2020
https://doi.org/10.1587/transinf.2019EDP7311
Czyzowicz JKosowski APelc A(2014)Time versus space trade-offs for rendezvous in treesDistributed Computing10.1007/s00446-013-0201-427:2(95-109)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1007/s00446-013-0201-4
Dieudonné YPelc AKhanna S(2013)Anonymous meeting in networksProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627870(737-747)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627870
Show More Cited By

Index Terms

Delays induce an exponential memory gap for rendezvous in trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Delays Induce an Exponential Memory Gap for Rendezvous in Trees

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this article, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration ...
Deterministic rendezvous in infinite trees
Abstract
The rendezvous task calls for two mobile agents, starting from different nodes of a network modeled as a graph to meet at the same node. Agents have different labels which are integers from a set { 1 , … , L }. They wake up at possibly different ...
Time versus space trade-offs for rendezvous in trees

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

June 2010

378 pages

ISBN:9781450300797

DOI:10.1145/1810479

General Chairs:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany
,
Cynthia Phillips
Sandia National Laboratories, USA

Copyright © 2010 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: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA 10

Sponsor:

SPAA 10: 22nd ACM Symposium on Parallelism in Algorithms and Architectures

June 13 - 15, 2010

Santorini, Thira, Greece

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
97
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

TSUCHIDA MOOSHITA FINOUE M(2020)Byzantine-Tolerant Gathering of Mobile Agents in Asynchronous Arbitrary Networks with Authenticated WhiteboardsIEICE Transactions on Information and Systems10.1587/transinf.2019EDP7311E103.D:7(1672-1682)Online publication date: 1-Jul-2020
https://doi.org/10.1587/transinf.2019EDP7311
Czyzowicz JKosowski APelc A(2014)Time versus space trade-offs for rendezvous in treesDistributed Computing10.1007/s00446-013-0201-427:2(95-109)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1007/s00446-013-0201-4
Dieudonné YPelc AKhanna S(2013)Anonymous meeting in networksProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627870(737-747)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627870
Dieudonné YPelc AVillain VFatourou PTaubenfeld G(2013)How to meet asynchronously at polynomial costProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484245(92-99)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484245
Fraigniaud PPelc A(2013)Delays Induce an Exponential Memory Gap for Rendezvous in TreesACM Transactions on Algorithms10.1145/2438645.24386499:2(1-24)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2438645.2438649
Baba DIzumi TOoshita FKakugawa HMasuzawa T(2013)Linear time and space gathering of anonymous mobile agents in asynchronous treesTheoretical Computer Science10.1016/j.tcs.2013.01.022478(118-126)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.tcs.2013.01.022
Dieudonné YPelc A(2013)Deterministic polynomial approach in the planeProceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-39212-2_47(533-544)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39212-2_47
Dieudonné YPelc APeleg D(2012)Gathering despite mischiefProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095161(527-540)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095161
Czyzowicz JKosowski APelc ABlelloch GHerlihy M(2012)Time vs. space trade-offs for rendezvous in treesProceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2312005.2312007(1-10)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1145/2312005.2312007
Elouasbi SPelc A(2012)Time of anonymous rendezvous in treesProceedings of the 19th international conference on Structural Information and Communication Complexity10.1007/978-3-642-31104-8_25(291-302)Online publication date: 30-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-31104-8_25
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