List of accepted papers for PODC 2011:


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 Vukolic. 
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 

Luis Ceze, Laura Effinger-Dean, Alexander Jaffe, Thomas Moscibroda 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