Papers Accepted to PODC 2011

Regular Papers

Guanfeng Liang and Nitin Vaidya.
Error-Free Multi-Valued Consensus with Byzantine Failures

Leonid Barenboim and Michael Elkin.
Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

Gabor Retvari, Andras Gulyas, Zalan Heszberger and Marton Csernai.
Compact Policy Routing

Wojciech Golab, Xiaozhou Li and Mehul Shah.
Analyzing consistency properties for fun and profit

Amitabh Trehan and Gopal Pandurangan.
Xheal: Localized Self-Healing Using Expanders

Christoph Lenzen and Roger Wattenhofer.
MIS on Trees

Dan Dobre, Rachid Guerraoui, Matthias Majuntke, Neeraj Suri and Marko Vukolić.
The Complexity of Robust Atomic Storage

Juan Garay, Jonathan Katz, Ranjit Kumaresan and Hong-Sheng Zhou.
Adaptively Secure Broadcast, Revisited

Michael Dinitz and Robert Krauthgamer.
Fault-Tolerant Spanners: Better and Simpler

Mika Goos and Jukka Suomela.
Locally checkable proofs

Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci and Eli Upfal.
Tight Bounds on Information Dissemination in Sparse Mobile Networks

Yoram Moses, Mark Tuttle and Maurice Herlihy.
Transforming Worst-case Optimal Solutions for Simultaneous Tasks into All-case Optimal Solutions

Maryam Helmi, Lisa Higham, Eduardo Pacheco and Philipp Woelfel.
The Space Complexity of Long-Lived and One-Shot Timestamp Implementations

Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan and Murtaza Zafer.
Minimum Congestion Mapping in a Cloud

Amos Korman, Jean-Sebastien Sereni and Laurent Viennot.
Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge

Kishore Kothapalli and Sriram Pemmaraju.
Distributed Coloring in Few Rounds

Amos Korman, Shay Kutten and Toshimitsu Masuzawa.
Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST

Valerie King, Jared Saia and Maxwell Young.
Conflict on a Communication Channel

Boaz Patt-Shamir and Marat Teplitsky.
The Round Complexity of Distributed Sorting

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert and Morteza Zadimoghaddam.
Optimal-Time Adaptive Tight Renaming, with Applications to Counting

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The.
Byzantine Agreement with Homonyms

Fabian Kuhn, Yoram Moses and Rotem Oshman.
Coordinated Consensus in Dynamic Networks

Thomas Moscibroda and Rotem Oshman.
Susceptibility of Mutual Exclusion Algorithms to Transient Memory Faults

Danupon Nanongkai, Atish Das Sarma and Gopal Pandurangan.
A tight unconditional lower bound on distributed random walk computation

Varsha Dani, Yamel Rodriguez and Jared Saia.
Scalable Rational Secret Sharing

Ji Zhu and Bruce Hajek.
Stability of a Peer-to-Peer Communication System

Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport.
Structuring Unreliable Radio Networks

Aleksandar Dragojevic, Maurice Herlihy, Yossi Lev and Mark Moir.
On The Power of Hardware Transactional Memory to Simplify Memory Management

Chen Avin, Michael Borokhovich, Keren Censor-Hillel and Zvi Lotker.
Order Optimal Information Spreading Using Algebraic Gossip

Alexander Jaffe, Thomas Moscibroda, Laura Effinger-Dean, Luis Ceze, and Karin Strauss.
The Impact of Memory Models on Software Reliability in Multiprocessors

Majid Khabbazian and Dariusz Kowalski.
Time-efficient randomized multiple-message broadcast in radio networks

Bernhard Haeupler and David Karger.
Network Coding: Beating Token Forwarding Lower Bounds in Dynamic Networks

Wojciech Golab.
A Complexity Separation Between Cache-Coherent and Distributed Shared Memory Models

Yehuda Afek, Adam Morrison and Guy Wertheim.
From Bounded to Unbounded Concurrency Objects and Back