Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1978782.1978789 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
log log n,oriented ring,state agent,randomized rendezvous,n-node ring,expected time,limited memory,memory requirement,identical agent,linear time,distributed computing | Log-log plot,Discrete mathematics,Combinatorics,Existential quantification,Rendezvous,Corollary,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 3 | 1549-6325 |
Citations | PageRank | References |
4 | 0.38 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evangelos Kranakis | 1 | 3107 | 354.48 |
| Danny Krizanc | 2 | 1778 | 191.04 |
| Pat Morin | 3 | 1610 | 178.95 |