## 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, RV_{0}, 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(u^{2}-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 RV_{1}(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, RV_{1}(k) is optimal in terms of expected rendezvous time while for u > 2, RV_{0} 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 language | English (US) |
---|---|

Title of host publication | ICDCN 2015 - Proceedings of the 16th International Conference on Distributed Computing and Networking |

Publisher | Association for Computing Machinery |

ISBN (Electronic) | 9781450329286 |

DOIs | |

State | Published - Jan 4 2015 |

Event | 16th International Conference on Distributed Computing and Networking, ICDCN 2015 - Goa, India Duration: Jan 4 2015 → Jan 7 2015 |

### Publication series

Name | ACM International Conference Proceeding Series |
---|---|

Volume | 04-07-January-2015 |

### Other

Other | 16th International Conference on Distributed Computing and Networking, ICDCN 2015 |
---|---|

Country/Territory | India |

City | Goa |

Period | 1/4/15 → 1/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