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.
展开▼
