30. PODC 2011: San Jose, CA, USA

Cyril Gavoille, Pierre Fraigniaud (Eds.): Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011. ACM 2011, ISBN 978-1-4503-0719-2

Consensus and agreement

Fabian Kuhn, Rotem Oshman, Yoram Moses:
Coordinated consensus in dynamic networks. 1-10
Guanfeng Liang, Nitin H. Vaidya:
Error-free multi-valued consensus with byzantine failures. 11-20
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert, Hung Tran-The:
Byzantine agreement with homonyms. 21-30

Local algorithms

Kishore Kothapalli, Sriram V. Pemmaraju:
Distributed graph coloring in a few rounds. 31-40
Christoph Lenzen, Roger Wattenhofer:
MIS on trees. 41-48
Amos Korman, Jean-Sébastien Sereni, Laurent Viennot:
Toward more localized local algorithms: removing assumptions concerning global knowledge. 49-58

Reliable and robust algorithms

Dan Dobre, Rachid Guerraoui, Matthias Majuntke, Neeraj Suri, Marko Vukolic:
The complexity of robust atomic storage. 59-68
Thomas Moscibroda, Rotem Oshman:
Resilience of mutual exclusion algorithms to transient memory faults. 69-78
Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy A. Lynch, Calvin C. Newport:
Structuring unreliable radio networks. 79-88
Alexander Jaffe, Thomas Moscibroda, Laura Effinger-Dean, Luis Ceze, Karin Strauss:
The impact of memory models on software reliability in multiprocessors. 89-98

Coherency and concurrency

Aleksandar Dragojevic, Maurice Herlihy, Yossi Lev, Mark Moir:
On the power of hardware transactional memory to simplify memory management. 99-108
Wojciech M. Golab:
A complexity separation between the cache-coherent and distributed shared memory models. 109-118
Yehuda Afek, Adam Morrison, Guy Wertheim:
From bounded to unbounded concurrency objects and back. 119-128

Best papers

Leonid Barenboim, Michael Elkin:
Distributed deterministic edge coloring using bounded neighborhood independence. 129-138
Maryam Helmi, Lisa Higham, Eduardo Pacheco, Philipp Woelfel:
The space complexity of long-lived and one-shot timestamp implementations. 139-148

Compact or sparse distributed structures

Gábor Rétvári, András Gulyás, Zalán Heszberger, Márton Csernai, József Bíró:
Compact policy routing. 149-158
Mika Göös, Jukka Suomela:
Locally checkable proofs. 159-168
Michael Dinitz, Robert Krauthgamer:
Fault-tolerant spanners: better and simpler. 169-178

Security and consistency

Juan A. Garay, Jonathan Katz, Ranjit Kumaresan, Hong-Sheng Zhou:
Adaptively secure broadcast, revisited. 179-186
Varsha Dani, Mahnush Movahedi, Yamel Rodriguez, Jared Saia:
Scalable rational secret sharing. 187-196
Wojciech M. Golab, Xiaozhou Li, Mehul A. Shah:
Analyzing consistency properties for fun and profit. 197-206

Brief announcements

Alberto Montresor, Francesco De Pellegrini, Daniele Miorandi:
Distributed k-core decomposition. 207-208
Matthias Majuntke, Dan Dobre, Neeraj Suri:
Fork-consistent constructions from registers. 209-210
Miguel A. Mosteiro, Antonio Fernández Anta, Jorge Ramón Muñoz:
Unbounded contention resolution in multiple-access channels. 211-212
Graham Cormode, Ke Yi:
Tracking distributed aggregates over time-based sliding windows. 213-214
Vijay K. Garg, John Bridgman, Bharath Balasubramanian:
Accurate byzantine agreement with feedback. 215-216
Alberto Mozo, José Luis López-Presa, Antonio Fernández Anta:
B-neck: a distributed and quiescent max-min fair algorithm. 217-218
Stephan Holzer, Yvonne Anne Pignolet, Jasmin Smula, Roger Wattenhofer:
Information dissemination on multiple channels. 219-220
Cristina Basescu, Christian Cachin, Ittay Eyal, Robert Haas, Marko Vukolic:
Robust data sharing with key-value stores. 221-222
Christian Schindelhauer, Zvi Lotker, Johannes Wendeberg:
Network synchronization and localization based on stolen signals. 223-224
Roberto Baldoni, Silvia Bonomi, Amir Soltani Nezhad:
Validity bound of regular registers with churn and byzantine processes. 225-226
Martin Biely, Peter Robinson, Ulrich Schmid:
Easy impossibility proofs for k-set agreement in message passing systems. 227-228
Sotiris Kentros, Aggelos Kiayias:
Solving the at-most-once problem with nearly optimal effectiveness. 229-230

Distributed algorithms

Maurice Herlihy, Yoram Moses, Mark R. Tuttle:
Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions. 231-238
Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, Morteza Zadimoghaddam:
Optimal-time adaptive strong renaming, with applications to counting. 239-248
Boaz Patt-Shamir, Marat Teplitsky:
The round complexity of distributed sorting: extended abstract. 249-256

Communication and congestion

Danupon Nanongkai, Atish Das Sarma, Gopal Pandurangan:
A tight unconditional lower bound on distributed randomwalk computation. 257-266
Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan, Murtaza Zafer:
Minimum congestion mapping in a cloud. 267-276
Valerie King, Jared Saia, Maxwell Young:
Conflict on a communication channel. 277-286

Brief announcements

Damien Imbs, Sergio Rajsbaum, Michel Raynal:
The universe of symmetry breaking tasks. 287-288
Shlomi Dolev, Panagiota N. Panagopoulou, Mikaël Rabie, Elad Michael Schiller, Paul G. Spirakis:
Rationality authority for provable rational behavior. 289-290
Tomas Toft:
Secure data structures based on multi-party computation. 291-292
Seda Davtyan, Kishori M. Konwar, Alexander A. Shvartsman:
Robust network supercomputing without centralized control. 293-294
Monika Steinová:
On the hardness and approximation of minimum topic-connected overlay. 295-296
Gahyun Park:
A generalization of multiple choice balls-into-bins. 297-298
Oded Goldreich, Brendan Juba, Madhu Sudan:
A theory of goal-oriented communication. 299-300

Self-* systems

Gopal Pandurangan, Amitabh Trehan:
Xheal: localized self-healing using expanders. 301-310
Amos Korman, Shay Kutten, Toshimitsu Masuzawa:
Fast and compact self stabilizing verification, computation, and fault detection of an MST. 311-320
Ji Zhu, Bruce E. Hajek:
Stability of a peer-to-peer communication system. 321-330

Brief announcements

Hannes Payer, Harald Röck, Christoph M. Kirsch, Ana Sokolova:
Scalability versus semantics of concurrent FIFO queues. 331-332
Aaron D. Jaggard, Michael Schapira, Rebecca N. Wright:
Distributed computing with rules of thumb. 333-334
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar:
Incentive-compatible distributed greedy protocols. 335-336
Haifeng Yu, Phillip B. Gibbons, Chenwei Shi:
Sustaining collaboration in multicast despite rational collusion. 337-338
Brendan Juba:
Reliable end-user communication under a changing packet network protocol. 339-340
Michael Backes, Matteo Maffei, Kim Pecina:
Securing social networks. 341-342
Patrick Viry:
Parallel and distributed programming extensions for mainstream languages based on pi-calculus. 343-344
Yujie Liu, Michael F. Spear:
A nonblocking set optimized for querying the minimum value. 345-346
Jiaqi Wang, Jennifer L. Welch, Hyunyoung Lee:
Time bounds for shared objects in partially synchronous systems. 347-348
Pramod V. Koppol, Kedar S. Namjoshi, Thanos Stathopoulos, Gordon T. Wilfong:
The inherent difficulty of timely primary-backup replication. 349-350
Goran Konjevod, Andréa W. Richa, Donglin Xia, Ling Zhou:
Randomized compact routing in decomposable metrics. 351-352
Tsvetomira Radeva, Nancy A. Lynch:
Partial reversal acyclicity. 353-354

Information dissemination

Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci, Eli Upfal:
Tight bounds on information dissemination in sparse mobile networks. 355-362
Chen Avin, Michael Borokhovich, Keren Censor-Hillel, Zvi Lotker:
Order optimal information spreading using algebraic gossip. 363-372
Majid Khabbazian, Dariusz R. Kowalski:
Time-efficient randomized multiple-message broadcast in radio networks. 373-380
Bernhard Haeupler, David R. Karger:
Faster information dissemination in dynamic networks via network coding. 381-390

Last update Fri May 25 08:32:36 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page