Randomized rendezvous with limited memory
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 2t state agent which can achieve rendezvous on an n-node ring in expected time O(n2/2t + 2t) and that any t/2 state agent requires expected time Ω(n2/2t). As a corollary we observe that Θ (log log n) bits of memory are necessary and sufficient to achieve rendezvous in linear time.
|Keywords||Distributed computing, Rendezvous|
|Journal||ACM Transactions on Algorithms|
Kranakis, E, Krizanc, D. (Danny), & Morin, P. (2011). Randomized rendezvous with limited memory. ACM Transactions on Algorithms (Vol. 7). doi:10.1145/1978782.1978789