Papers Accepted to PODC 2006 (sorted by author names)
-
Distributed Computing Meets Game Theory: Robust Mechanisms for Rational Secret Sharing and Multiparty Computation
Ittai Abraham, Danny Dolev, Rica Gonen, Joseph Halpern
-
Common2 extended to stacks and unbounded concurrency
Yehuda Afek, Eli Gafni, Adam Morrison
-
Stably Computable Predicates are Semilinear
Dana Angluin, James Aspnes, David Eisenstat
-
Transactional Contention Management as a Non-Clairvoyant Scheduling Problem
Hagit Attiya, Leah Epstein, Hadas Shachnai, Tami Tamir
-
Synchronizing without Locks is Inherently Expensive
Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kouznetsov
-
Veracity Radius - Capturing the Locality of Distributed Computations
Yitzhak Birk, Idit Keidar, Liran Liss, Assaf Schuster, Ran Wolff
-
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
Avrim Blum, Eyal Even-Dar, Katrina Ligett
-
Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling
Bogdan Caprita, Jason Nieh, Clifford Stein
-
Adversarial queuing on the multiple-access channel
Bogdan Chlebus, Dariusz Kowalski, Mariusz Rokicki
-
Self-Stabilizing Byzantine Agreement
Ariel Daliot, Danny Dolev
-
Local Approximation Schemes for Topology Control
Mirela Damian, Saurav Pandit, Sriram Pemmaraju
-
An $\Omega(n \log n)$ Lower Bound on the Cost of Mutual Exclusion
(Best Paper)
Rui Fan, Nancy Lynch
-
Optimally Efficient Multi-Valued Byzantine Agreement
Matthias Fitzi, Martin Hirt
-
Oracle size: a new measure of difficulty for communication tasks
Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc
-
Quorum Placement in Networks: Minimizing Network Congestion
Daniel Golovin, Anupam Gupta, Bruce Maggs, Florian Oprea, Michael Reiter
-
An O(1) RMRs Leader Election Algorithm
Danny Hendler, Philipp Woelfel
-
A Lower Bound for Scalable Byzantine Agreemnt
Dan Holtby, Bruce Kapron, Valerie King
-
Single-Scanner Multi-Writer Snapshot Implementations are Fast!
Panagiota Fatourou, Nikollaos Kallimanis
-
Timeliness, Failure-Detectors, and Consensus Performance
Idit Keidar, Alexander Shraer
-
EquiCast: Scalable Multicast with Selfish Users
Idit Keidar, Roie Melamed, Ariel Orda
-
Distributed Verification of Minimum Spanning Trees
Amos Korman, Shay Kutten
-
On the Complexity of Distributed Graph Coloring
Fabian Kuhn, Roger Wattenhofer
-
Reliable Broadcast in Radio Networks: The Bounded Collision Case
Chiu-Yuen Koo, Vartika Bhandari,Jonathan Katz, Nitin H. Vaidya
-
Peer Counting and Sampling in overlay networks: random walk methods
Laurent Massoulie, Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi Ganesh
-
On the Topologies Formed by Selfish Peers
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
-
When Selfish Meets Evil: Byzantine Players in a Virus Inoculation Game
Thomas Moscibroda, Stefan Schmid, Roger Wattenhofer
-
Computing Separable Functions via Gossip
Damon Mosk-Aoyama, Devavrat Shah
-
Sketching Asynchronous Streams Over Sliding Windows
Srikanta Tirthapura, Bojian Xu, Costas Busch
-
Irreducibility and Additivity of Set Agreement-oriented Failure Detector Classes
Corentin Travers, Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal
-
How fast can a very robust read be?
Marko Vukolic, Rachid Guerraoui