Randomized rendezvous with limited memory
Evangelos Kranakis, Danny Kriz̧anc, Pat Morin · ACM Transactions on Algorithms · 2011
We present a trade-off between the expected time for two identical agents to rendezvous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show there exists a 2 t state agent which can achieve rendezvous 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 Θ(log log n ) bits of memory are necessary and sufficient to achieve rendezvous in linear time.