25. PODC 2006: Denver, Colorado, USA

Eric Ruppert, Dahlia Malkhi (Eds.): Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006. ACM 2006, ISBN 1-59593-384-0 BibTeX

Maurice Herlihy:
The art of multiprocessor programming. 1-2
Electronic Edition (ACM DL) BibTeX
Danny Dolev:
Century papers at the first quarter-century milestone. 3-4
Electronic Edition (ACM DL) BibTeX
Jon M. Kleinberg:
Distributed social systems. 5-6
Electronic Edition (ACM DL) BibTeX

Graph algorithms

Fabian Kuhn, Roger Wattenhofer:
On the complexity of distributed graph coloring. 7-15
Electronic Edition (ACM DL) BibTeX
Daniel Golovin, Anupam Gupta, Bruce M. Maggs, Florian Oprea, Michael K. Reiter:
Quorum placement in networks: minimizing network congestion. 16-25
Electronic Edition (ACM DL) BibTeX
Amos Korman, Shay Kutten:
Distributed verification of minimum spanning trees. 26-34
Electronic Edition (ACM DL) BibTeX

Game theory

Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer:
When selfish meets evil: byzantine players in a virus inoculation game. 35-44
Electronic Edition (ACM DL) BibTeX
Avrim Blum, Eyal Even-Dar, Katrina Ligett:
Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games. 45-52
Electronic Edition (ACM DL) BibTeX
Ittai Abraham, Danny Dolev, Rica Gonen, Joseph Y. Halpern:
Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. 53-62
Electronic Edition (ACM DL) BibTeX
Idit Keidar, Roie Melamed, Ariel Orda:
EquiCast: scalable multicast with selfish users. 63-71
Electronic Edition (ACM DL) BibTeX

Algorithms

Bogdan Caprita, Jason Nieh, Clifford Stein:
Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling. 72-81
Electronic Edition (ACM DL) BibTeX
Srikanta Tirthapura, Bojian Xu, Costas Busch:
Sketching asynchronous streams over a sliding window. 82-91
Electronic Edition (ACM DL) BibTeX
Bogdan S. Chlebus, Dariusz R. Kowalski, Mariusz A. Rokicki:
Adversarial queuing on the multiple-access channel. 92-101
Electronic Edition (ACM DL) BibTeX
Yitzhak Birk, Idit Keidar, Liran Liss, Assaf Schuster, Ran Wolff:
Veracity radius: capturing the locality of distributed computations. 102-111
Electronic Edition (ACM DL) BibTeX
Werner Vogels:
Life is not a state-machine: the long road from research to production. 112
Electronic Edition (ACM DL) BibTeX

Peer-to-peer

Damon Mosk-Aoyama, Devavrat Shah:
Computing separable functions via gossip. 113-122
Electronic Edition (ACM DL) BibTeX
Laurent Massoulié, Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi J. Ganesh:
Peer counting and sampling in overlay networks: random walk methods. 123-132
Electronic Edition (ACM DL) BibTeX
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer:
On the topologies formed by selfish peers. 133-142
Electronic Edition (ACM DL) BibTeX

Agreement problems

Ariel Daliot, Danny Dolev:
Self-stabilizing byzantine agreement. 143-152
Electronic Edition (ACM DL) BibTeX
Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers:
Irreducibility and additivity of set agreement-oriented failure detector classes. 153-162
Electronic Edition (ACM DL) BibTeX
Matthias Fitzi, Martin Hirt:
Optimally efficient multi-valued byzantine agreement. 163-168
Electronic Edition (ACM DL) BibTeX
Idit Keidar, Alexander Shraer:
Timeliness, failure-detectors, and consensus performance. 169-178
Electronic Edition (ACM DL) BibTeX

Graph algorithms

Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc:
Oracle size: a new measure of difficulty for communication tasks. 179-187
Electronic Edition (ACM DL) BibTeX
Ittai Abraham, Cyril Gavoille:
Object location using path separators. 188-197
Electronic Edition (ACM DL) BibTeX
Goran Konjevod, Andréa W. Richa, Donglin Xia:
Optimal-stretch name-independent compact routing in doubling metrics. 198-207
Electronic Edition (ACM DL) BibTeX
Mirela Damian, Saurav Pandit, Sriram V. Pemmaraju:
Local approximation schemes for topology control. 208-217
Electronic Edition (ACM DL) BibTeX

Shared memory

Yehuda Afek, Eli Gafni, Adam Morrison:
Common2 extended to stacks and unbounded concurrency. 218-227
Electronic Edition (ACM DL) BibTeX
Panagiota Fatourou, Nikolaos D. Kallimanis:
Single-scanner multi-writer snapshot implementations are fast! 228-237
Electronic Edition (ACM DL) BibTeX
Wojciech M. Golab, Danny Hendler, Philipp Woelfel:
An O(1) RMRs leader election algorithm. 238-247
Electronic Edition (ACM DL) BibTeX

Fault tolerance

Rachid Guerraoui, Marko Vukolic:
How fast can a very robust read be? 248-257
Electronic Edition (ACM DL) BibTeX
Chiu-Yuen Koo, Vartika Bhandari, Jonathan Katz, Nitin H. Vaidya:
Reliable broadcast in radio networks: the bounded collision case. 258-264
Electronic Edition (ACM DL) BibTeX
Kannan Srinathan, C. Pandu Rangan:
Possibility and complexity of probabilistic reliable communication in directed networks. 265-274
Electronic Edition (ACM DL) BibTeX

Algorithms and lower bounds

Rui Fan, Nancy A. Lynch:
An Omega (n log n) lower bound on the cost of mutual exclusion. 275-284
Electronic Edition (ACM DL) BibTeX
Dan Holtby, Bruce M. Kapron, Valerie King:
Lower bound for scalable Byzantine Agreement. 285-291
Electronic Edition (ACM DL) BibTeX
Dana Angluin, James Aspnes, David Eisenstat:
Stably computable predicates are semilinear. 292-299
Electronic Edition (ACM DL) BibTeX

Shared memory synchronization

Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kouznetsov:
Synchronizing without locks is inherently expensive. 300-307
Electronic Edition (ACM DL) BibTeX
Hagit Attiya, Leah Epstein, Hadas Shachnai, Tami Tamir:
Transactional contention management as a non-clairvoyant scheduling problem. 308-315
Electronic Edition (ACM DL) BibTeX
Rachid Guerraoui, Maurice Herlihy, Bastian Pochon:
Towards a theory of transactional contention managers. 316-317
Electronic Edition (ACM DL) BibTeX