Distributed Computing

1. Front Matter

   Pages I-XXIV

   PDF

2. Fast Two-Robot Disk Evacuation with Wireless Communication

   • Ioannis Lamprou, Russell Martin, Sven Schewe

   Pages 1-15

3. Deterministic Leader Election in \(O(D+\log n)\) Time with Messages of Size O(1)

   • Arnaud Casteigts, Yves Métivier, John Michael Robson, Akka Zemmari

   Pages 16-28

4. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks

   • Amir Abboud, Keren Censor-Hillel, Seri Khoury

   Pages 29-42

5. Fast Distributed Algorithms for Testing Graph Properties

   • Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, Yadu Vasudev

   Pages 43-56

6. Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems

   • François Le Gall

   Pages 57-70

7. Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks

   • Christian Scheideler, Alexander Setzer, Thim Strothmann

   Pages 71-84

8. Asynchronous Embedded Pattern Formation Without Orientation

   • Serafino Cicerone, Gabriele Di Stefano, Alfredo Navarra

   Pages 85-98

9. Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model

   • Dan Hefetz, Fabian Kuhn, Yannic Maus, Angelika Steger

   Pages 99-113

10. Optimal Consistent Network Updates in Polynomial Time

    • Pavol Černý, Nate Foster, Nilesh Jagnik, Jedidiah McClurg

    Pages 114-128

11. Distributed Construction of Purely Additive Spanners

    • Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, Amir Yehudayoff

    Pages 129-142

12. Optimal Fair Computation

    • Rachid Guerraoui, Jingjing Wang

    Pages 143-157

13. Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs

    • Bernhard Haeupler, Taisuke Izumi, Goran Zuzic

    Pages 158-172

14. Anonymity-Preserving Failure Detectors

    • Zohir Bouzid, Corentin Travers

    Pages 173-186

15. Certified Universal Gathering in \(\mathbb {R} ^2\) for Oblivious Mobile Robots

    • Pierre Courtieu, Lionel Rieg, Sébastien Tixeuil, Xavier Urbain

    Pages 187-200

16. Non-local Probes Do Not Help with Many Graph Problems

    • Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela

    Pages 201-214

17. Are Byzantine Failures Really Different from Crash Failures?

    • Damien Imbs, Michel Raynal, Julien Stainer

    Pages 215-229

18. Sublinear-Space Distance Labeling Using Hubs

    • Paweł Gawrychowski, Adrian Kosowski, Przemysław Uznański

    Pages 230-242

19. Online Balanced Repartitioning

    • Chen Avin, Andreas Loukas, Maciej Pacut, Stefan Schmid

    Pages 243-256

20. Lower Bound on the Step Complexity of Anonymous Binary Consensus

    • Hagit Attiya, Ohad Ben-Baruch, Danny Hendler

    Pages 257-268

This book constitutes the proceedings of the 30th International Symposium on Distributed Computing, DISC 2016, held in Paris, France, in September 2016.

The 32 full papers, 10 brief annoucements and 3 invited lectures presented in this volume were carefully reviewed and selected from 145 submissions.The focus of the conference is on following topics: theory, design, implementation, modeling, analysis, or application of distributed systems and networks.

• big data
• distributed computation
• dynamic networks
• overlay networks
• wireless
• algorithm analysis and problem complexity

• LABRI, Univ of Bordeaux LABRI, Talence Cedex, France

  Cyril Gavoille

• CNRS, Universite Bordeaux 1 CNRS, Talence Cedex, France

  David Ilcinkas

Policies and ethics