Name
Abstract | ||
|---|---|---|
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(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 |
|---|---|---|
2008 | 10.1007/978-3-540-78773-0_52 | LATIN |
Keywords | Field | DocType |
log log n,oriented ring,state agent,n node ring,expected time,limited memory,memory requirement,identical agent,randomized rendez-vous,linear time,distributed computing | Log-log plot,Discrete mathematics,Combinatorics,Existential quantification,Computer science,Mobile agent,Rendezvous,Time complexity,Corollary | Conference |
Volume | ISSN | ISBN |
4957 | 0302-9743 | 3-540-78772-0 |
Citations | PageRank | References |
19 | 0.69 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evangelos Kranakis | 1 | 3107 | 354.48 |
| Danny Krizanc | 2 | 1778 | 191.04 |
| Pat Morin | 3 | 1610 | 178.95 |