Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings

Front Matter....Pages I-XXIV
Fast Two-Robot Disk Evacuation with Wireless Communication....Pages 1-15
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks....Pages 16-28
Fast Distributed Algorithms for Testing Graph Properties....Pages 29-42
Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems....Pages 43-56
Towards a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks....Pages 57-70
Asynchronous Embedded Pattern Formation Without Orientation....Pages 71-84
Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model....Pages 85-98
Optimal Consistent Network Updates in Polynomial Time....Pages 99-113
Distributed Construction of Purely Additive Spanners....Pages 114-128
Optimal Fair Computation....Pages 129-142
Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs....Pages 143-157
Anonymity-Preserving Failure Detectors....Pages 158-172
Non-local Probes Do Not Help with Many Graph Problems....Pages 173-186
Are Byzantine Failures Really Different from Crash Failures?....Pages 187-200
Sublinear-Space Distance Labeling Using Hubs....Pages 201-214
Online Balanced Repartitioning....Pages 215-229
Lower Bound on the Step Complexity of Anonymous Binary Consensus....Pages 230-242
Opacity vs TMS2: Expectations and Reality....Pages 243-256
On Composition and Implementation of Sequential Consistency....Pages 257-268
k-Abortable Objects: Progress Under High Contention....Pages 269-283
Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model....Pages 284-297
Buffer Size for Routing Limited-Rate Adversarial Traffic....Pages 298-312
Distributed Testing of Excluded Subgraphs....Pages 313-327
How to Discreetly Spread a Rumor in a Crowd....Pages 328-341
Depth of a Random Binary Search Tree with Concurrent Insertions....Pages 342-356
Priority Mutual Exclusion: Specification and Algorithm....Pages 357-370
Information Spreading in Dynamic Networks Under Oblivious Adversaries....Pages 371-384
Non-Bayesian Learning in the Presence of Byzantine Agents....Pages 385-398
Asynchronous Computability Theorems for t-Resilient Systems....Pages 399-413
Upper Bounds for Boundless Tagging with Bounded Objects....Pages 414-427
Back Matter....Pages 428-441
....Pages 442-457