Randomized rendezvous algorithms for agents on a ring with different speeds

Evangelos Kranakis, Danny Krizanc, Fraser MacQuarrie, Sunil Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We provide randomized rendezvous algorithms for two synchronous robots in a bi-directional ring of length n (n is a real number): the robots are equipped with identical chronometers, execute identical algorithms, but have different speeds u, 1 (where u > 1). In general, neither of the robots are aware of their own speed but in some cases they may be aware either of the magnitude of u or some quantity of time that depends on u, n. The robots start by choosing a direction uniformly and independently at random. Given integer k ≥ 0, we design algorithms that have the two robots alternate for k + 1 rounds between choosing the direction at random followed by walking for a predetermined time. In the last round the robots walk until rendezvous. The first algorithm, RV0, works with one random bit per robot and consists of a single round: after choosing their initial directions the robots never change direction. Rendezvous is established in u·n/2(u2-1) expected time and this is shown to be optimal among all randomized algorithms employing a single random bit during their execution. The second algorithm RV1(k), for k ≥ 1, has the two robots alternate for k + 1 rounds between choosing the direction at random followed by walking for a predetermined time n/u+1; in the last step the robots walk until rendezvous. Among all algorithms that use k + 1 random bits we establish a sharp threshold; for u ≤ 2, RV1(k) is optimal in terms of expected rendezvous time while for u > 2, RV0 is optimal. Further, we provide new randomized rendezvous algorithms employing more random bits and analyze their expected rendezvous time depending on the knowledge of the robots about the length n of the ring and their speeds (u > 1).

Original languageEnglish (US)
Title of host publicationICDCN 2015 - Proceedings of the 16th International Conference on Distributed Computing and Networking
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450329286
DOIs
StatePublished - Jan 4 2015
Event16th International Conference on Distributed Computing and Networking, ICDCN 2015 - Goa, India
Duration: Jan 4 2015Jan 7 2015

Publication series

NameACM International Conference Proceeding Series
Volume04-07-January-2015

Other

Other16th International Conference on Distributed Computing and Networking, ICDCN 2015
Country/TerritoryIndia
CityGoa
Period1/4/151/7/15

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Keywords

  • Random bits
  • Randomized algorithm
  • Rendezvous
  • Ring
  • Robots
  • Speeds

Fingerprint

Dive into the research topics of 'Randomized rendezvous algorithms for agents on a ring with different speeds'. Together they form a unique fingerprint.

Cite this