Archives
1985-2009

25th International Symposium on Distributed Computing

Rome, Italy, September 20-22, 2011

The proceedings of the conference is edited by
David Peleg
In: Lecture Notes in Computer Science Vol. 6950, Springer, 2011,
ISBN 978-3-642-24100-0.

List of papers:

Invited Lecture

• Andrzej Pelc : Deterministic Rendezvous in Networks: Survey of Models and Results,
  pages 1-15.
• Mahesh Balakrishnan and Dahlia Malkhi and Vijayan Prabhakaran and Ted Wobber : Going beyond Paxos,
  pages 208-210.
• Peter Widmayer : Polygon Reconstruction with Little Information: An Example for the Power of Simple Micro-robots,
  pages 332-332.

Accepted Papers

• Yehuda Afek and Michael Hakimi and Adam Morrison : Fast and Scalable Rendezvousing,
  pages 16-31.
• Yehuda Afek and Noga Alon and Ziv Bar-Joseph and Alejandro Cornejo and Bernhard Haeupler and Fabian Kuhn : Beeping a Maximal Independent Set,
  pages 32-50.
• Johannes Schneider and Roger Wattenhofer : Trading Bit, Message, and Time Complexity of Distributed Algorithms,
  pages 51-65.
• Leonid Barenboim and Michael Elkin : Combinatorial Algorithms for Distributed Graph Coloring,
  pages 66-81.
• Taisuke Izumi and Maria Gradinariu Potop-Butucaru and Mathieu Valero : Physical Expander in Virtual Tree Overlay,
  pages 82-96.
• Dan Alistarh and James Aspnes : Sub-logarithmic Test-and-Set against a Weak Adversary,
  pages 97-109.
• Gadi Taubenfeld : Tight Space Bounds for l-Exclusion,
  pages 110-124.
• Dmitri Perelman and Anton Byshevsky and Oleg Litmanovich and Idit Keidar : SMV: Selective Multi-Versioning STM,
  pages 125-140.
• Swan Dubois and Toshimitsu Masuzawa and Sébastien Tixeuil : Maximum Metric Spanning Tree Made Byzantine Tolerant,
  pages 150-164.
• Chryssis Georgiou and Dariusz R. Kowalski : Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts,
  pages 165-180.
• Elette Boyle and Shafi Goldwasser and Yael Tauman Kalai : Leakage-Resilient Coin Tossing,
  pages 181-196.
• Leslie Lamport : Byzantizing Paxos by Refinement,
  pages 211-224.
• Antonio Fernández Anta and Miguel A. Mosteiro and Jorge Ramón Muñoz : Unbounded Contention Resolution in Multiple-Access Channels,
  pages 225-236.
• Leonid Barenboim and Shlomi Dolev and Rafail Ostrovsky : Deterministic and Energy-Optimal Wireless Synchronization,
  pages 237-251.
• Shlomi Dolev and Seth Gilbert and Majid Khabbazian and Calvin Newport : Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast,
  pages 252-267.
• Mohsen Ghaffari and Nancy Lynch and Srikanth Sastry and Calvin Newport : Leader Election Using Loneliness Detection,
  pages 268-282.
• Srikanta Tirthapura and David P. Woodruff : Optimal Random Sampling from Distributed Streams Revisited,
  pages 283-297.
• Andrea E. F. Clementi and Riccardo Silvestri : Parsimonious Flooding in Geometric Random-Walks,
  pages 298-310.
• Yvonne Anne Pignolet and Stefan Schmid and Gilles Tredan : Misleading Stars: What Cannot Be Measured in the Internet?,
  pages 311-325.
• Pierre Fraigniaud and Sergio Rajsbaum and Corentin Travers and Calvin Newport : Locality and Checkability in Wait-Free Computing,
  pages 333-347.
• Allison Lewko : The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement,
  pages 348-362.
• James Aspnes : Randomized Consensus in Expected O(n²) Total Work Using Single-Writer Registers,
  pages 363-373.
• Hagit Attiya and Fatemeh Borran and Martin Hutle and Zarko Milosevic and André Schiper : Structured Derivation of Semi-Synchronous Algorithms,
  pages 374-388.
• Piyush Bansal and Prasant Gopal and Anuj Gupta and Kannan Srinathan and Pranav Kumar Vasishta : Byzantine Agreement Using Partial Authentication,
  pages 389-403.
• ttai Abraham and Cyril Gavoille : On Approximate Distance Labels and Routing Schemes with Affine Stretch,
  pages 404-415.
• Fabian Kuhn and Rotem Oshman : The Complexity of Data Aggregation in Directed Networks,
  pages 416-431.
• Jérémie Chalopin and Shantanu Das and Arnaud Labourel and Euripides Markou : Black Hole Search with Finite Automata Scattered in a Synchronous Torus,
  pages 432-446.
• Andrew Collins and Jurek Czyzowicz and Leszek Gąsieniec and Adrian Kosowski and Russell Martin : Synchronous Rendezvous for Location-Aware Agents,
  pages 447-459.
• Li Lu and Michael L. Scott : Toward a Formal Semantic Framework for Deterministic Parallel Programming,
  pages 460-474.
• Dmitry Basin and Rui Fan, Idit Keidar and Idit Keidar and Ofer Kiselov and Dmitri Perelman and Dmitri Perelman : CAFÉ: Scalable Task Pools with Adjustable Fairness and Contention,
  pages 475-488.
• Yehuda Afek and Yakov Babichenko and Uriel Feige and Eli Gafni and Nati Linial and Benny Sudakov : Oblivious Collaboration,
  pages 489-504.

Brief Anouncements

• Leslie Lamport : Leaderless Byzantine Paxos,
  pages 141-142.
• Keith Marzullo, Hein Meling and Alessandro Mei and Hein Meling and Alessandro Mei : When You Don’t Trust Clients: Byzantine Proposer Fast Paxos,
  pages 143-144.
• Carole Delporte-Gallet and Hugues Fauconnier and Eli Gafni and Petr Kuznetsov : On the Meaning of Solving a Task with a Failure Detector,
  pages 145-146.
• Evgenia Christoforou and Antonio Fernández Anta and Chryssis Georgiou and Miguel A. Mosteiro : Algorithmic Mechanisms for Internet-Based Computing under Unreliable Communication,
  pages 147-149.
• Shay Kutten and Ron Lavi and Amitabh Trehan : Composition Games for Distributed Systems: The EU Grants Games,
  pages 197-199.
• Andrzej Czygrinow and Michal Hanćkowiak and Krzysztof Krzywdziński and Edyta Szymańska and Wojciech Wawrzyniak : Distributed Approximations for the Semi-matching Problem,
  pages 200-201.
• Martín Farach-Colton and Antonio Fernández Anta and Alessia Milani and Miguel A. Mosteiro and Shmuel Zaks : Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism,
  pages 202-204.
• Siddhartha Sen and Sunghwan Ihm and Kay Ousterhout and Michael J. Freedman : Bridging the Theory-Practice Gap in Multi-commodity Flow Routing,
  pages 205-207.
• Meg Walraed-Sullivan and Radhika Niranjan Mysore and Keith Marzullo and Amin Vahdat : A Randomized Algorithm for Label Assignment in Dynamic Networks,
  pages 326-327.
• Mikel Larrea and Michel Raynal : ΔΩ: Specifying an Eventual Leader Service for Dynamic Systems,
  pages 328-329.
• Taisuke Izumi and Zohir Bouzid and Sébastien Tixeuil and Koichi Wada : The BG-Simulation for Byzantine Mobile Robots,
  pages 330-331.

Winner of Best Paper Award

• Pierre Fraigniaud and Sergio Rajsbaum and Corentin Travers : Locality and Checkability in Wait-Free Computing,
  pages 333-347.

Winner of Best Student Paper Award

• Yehuda Afek and Michael Hakimi and Adam Morrison : Fast and Scalable Rendezvousing,
  pages 16-32.