Papers Accepted to PODC 2012

Regular Papers

Clemens Adolphs and Petra Berenbrink
Distributed Selfish Load Balancing with Weights and Speeds

Adi Akavia, Shafi Goldwasser, and Carmit Hazay
Distributed Public Key Schemes Secure against Continual Leakage

Hoda Akbari, Petra Berenbrink, and Thomas Sauerwald
A Simple Approach for Adapting Continuous Load Balancing Processes to Discrete Settings

James Aspnes
Faster Randomized Consensus with an Oblivious Adversary

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen
Faster than Optimal Snapshots (for a While)

Petra Berenbrink, Colin Cooper, and Tom Friedetzky
Random Walks which Prefer Unvisited Edges and Exploring High Girth Even Degree Expanders in Linear Time

Victor Bushkov, Rachid Guerraoui, and Michal Kapalka
On the Liveness of Transactional Memory

Venkatesan Chakaravarthy, Sambuddha Roy, and Yogish Sabharwal
Distributed algorithms for scheduling on line and tree networks

Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip Gibbons
The Cost of Fault-Tolerance in Multi-Party Communication Complexity

Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues
On the (Limited) Power of Non-Equivocation

Andrea Clementi, Riccardo Silvestri, and Luca Trevisan
Information Spreading in Dynamic Graphs

Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik
Coalescing Random Walks and Voting on Graphs

Alejandro Cornejo, Seth Gilbert, and Calvin Newport
Aggregation in Dynamic Networks

Alejandro Cornejo, Nancy Lynch, and Srikanth Sastry
Asynchronous Failure Detectors

Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin Newport
Leader Election in Shared Spectrum Radio Networks

Andrew Drucker, Fabian Kuhn, and Rotem Oshman
The Communication Complexity of Distributed Task Allocation

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov
Wait-Freedom with Advice

Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, and Corentin Travers
Universal Constructions that Ensure Disjoint-Access Parallelism and Wait-Freedom

Jose Faleiro, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam, and Kapil Vaswani
Generalized Lattice Agreement

George Giakkoupis and Philipp Woelfel
On the Time and Space Complexity of Randomized Test-And-Set

Seth Gilbert and Maxwell Young
Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks

Mika Göös, Juho Hirvonen, and Jukka Suomela
Lower Bounds for Local Approximation

Magnus M. Halldorsson and Pradipta Mitra
Distributed Connectivity of Wireless Networks

Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema
Weak Models of Distributed Computing, with Connections to Modal Logic

Maryam Helmi, Lisa Higham, and Philipp Woelfel
Strongly Linearizable Implementations: Possibilities and Impossibilities

Maurice Herlihy and Sergio Rajsbaum
Simulations and Reductions for Colorless Tasks

Juho Hirvonen and Jukka Suomela
Distributed Maximal Matching: Greedy is Optimal

Stephan Holzer and Roger Wattenhofer
Optimal Distributed All Pairs Shortest Paths and Applications

Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen
On the Price of Equivocation in Byzantine Agreement

Thomas Kesselheim
Dynamic Packet Scheduling in Wireless Networks

Guanfeng Liang and Nitin Vaidya
Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding

Amos Korman, Ofer Feinerman, Zvi Lotker, and Jean-Sebastien Sereni
Collaborative Search on the Plane without Communication

Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang
Competitive and Fair Throughput for Co-Existing Networks Under Adversarial Interference

Gadi Taubenfeld
A Closer Look at Fault Tolerance

Nitin Vaidya, Lewis Tseng, and Guanfeng Liang
Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs

Brief Announcements

George Giakkoupis and Philipp Woelfel
Brief Announcement: Tight RMR Lower Bounds for Randomized Mutual Exclusion

Zarko Milosevic, Martin Hutle, and André Schiper
Brief Announcement: Tolerating Permanent and Transient Value Faults

András Gulyás, Attila Korösi, Gábor Rétvári, and József Bíró
Brief Announcement: Network Formation Games Can Give Rise to Realistic Networks

Michel Raynal and Julien Stainer
Brief Announcement: Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors

Robert Lychev, Sharon Goldberg, and Michael Schapira
Brief Announcement: Network Destabilizing Attacks

Joan Feigenbaum, Brighten Godfrey, Aurojit Panda, Michael Schapira, Ankit Singla, and Scott Shenker
Brief Announcement: On the Resilience of Routing Tables

Eyjolfur Asgeirsson, Magnus M. Halldorsson, and Pradipta Mitra
Brief Announcement: Distributed Algorithms for Throughput Performance in Wireless Networks

John Bridgman and Vijay Garg
Brief Announcement: All-to-all Gradecast using Coding with Byzantine Failures

Ymir Vigfusson, Ken Birman, Daniel Freedman, Qi Huang, Kristjan Jonsson, and Gunnar Sveinbjornsson
Brief Announcement: Live Streaming with Utilities, Quality and Cost

Arnaud Casteigts, Paola Flocchini, Emmanuel Godard, Nicola Santoro, and Masafumi Yamashita
Brief Announcement: Waiting in Dynamic Networks

Andras Farago
Brief Announcement: An Obstacle to Scalability in Wireless Networks

Heger Arfaoui and Pierre Fraigniaud
Brief Announcement: What Can be Computed without Communications?

Michael Backes, Fabian Bendun, and Aniket Kate
Brief Announcement: Distributed Cryptography using TrInc

Oksana Denysyuk and Luis Rodrigues
Brief Announcement: Order-preserving Renaming in Synchronous Message Passing Systems with Byzantine Faults

Anduo Wang, Carolyn Talcott, Alexander J. T. Gurney, Boon Thau Loo, and Andre Scedrov
Brief Announcement: A Calculus of Policy-Based Routing Systems

Evgenia Christoforou, Antonio Fernandez Anta, Chryssis Georgiou, Miguel Mosteiro, and Angel Sanchez
Brief Announcement: Achieving Reliability in Master-Worker Computing via Evolutionary Dynamics

Shailesh Vaya
Brief Announcement: Delay or Deliver Dilemma in Organization Networks

Ashish Choudhury
Brief Announcement: Optimal Amortized Secret Sharing with Cheater Identification

Seda Davtyan, Kishori Konwar, and Alexander Shvartsman
Brief Announcement: Decentralized Network Supercomputing in the Presence of Malicious and Crash-Prone Workers

Ashish Choudhury and Arpita Patra
Brief Announcement: Efficient Optimally Resilient Statistical AVSS and Its Applications

Nuno Preguica, Carlos Baquero, Paulo Sérgio Almeida, Victor Fonte, and Ricardo Gonçalves
Brief Announcement: Decoupling Version Identification from Causality Tracking Information in Distributed Storage Systems

Armando Castaneda, Sergio Rajsbaum, and Michel Raynal
Brief Announcement: There are Plenty of Tasks Weaker than Perfect Renaming and Stronger than $(n-1)$-set Agreement

Vincent Gramoli, Petr Kuznetsov, and Srivatsan Ravi
Brief Announcement: From Sequential to Concurrent: Correctness and Relative Efficiency

Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan
Brief Announcement: Maintaining Large Dense Subgraphs on Dynamic Networks

Vita Bortnikov, Gregory Chockler, Dmitri Perelman, Alexey Roytman, Shlomit Shachor, and Ilya Shnayderman
Brief Announcement: Reconfigurable State Machine Replication from Non-Reconfigurable Building Blocks

Varsha Dani, Valerie King, Mahnush Movahedi, and Jared Saia
Brief Announcement: Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary