We present a tradeoff between the expected time for two identical agents to rendez-vous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show that there exists a 2t state agent, which can achieve rendez-vous on an n node ring in expected time O( n 2/2 t ∈+∈2 t ) and that any t/2 state agent requires expected time Ω( n 2/2 t ). As a corollary we observe that Θ(loglogn) bits of memory are necessary and sufficient to achieve rendez-vous in linear time.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-540-78773-0_52
Citation
Kranakis, E, Krizanc, D. (Danny), & Morin, P. (2008). Randomized rendez-vous with limited memory. doi:10.1007/978-3-540-78773-0_52