Paper Info
Title
Randomized Rendezvous Algorithms for Agents on a Ring with Different Speeds
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 u/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).
Year
DOI
Venue
2015
10.1145/2684464.2684468
ICDCN
Keywords
Field
DocType
algorithms,random bits,nonnumerical algorithms and problems,robots,randomized algorithm,ring,speeds,theory,rendezvous
Integer,Randomized algorithm,Computer science,Algorithm,Rendezvous,Robot,Real number,Distributed computing
Conference
Citations 
PageRank 
References 
4
0.45
19
Authors
4
Name
Order
Citations
PageRank
Evangelos Kranakis13107354.48
Danny Krizanc21778191.04
Fraser MacQuarrie3354.78
Sunil M. Shende421824.35