Distributed Computing: 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings

Front Matter....Pages I-XXI
On the Computational Complexity of MapReduce....Pages 1-15
Efficient Counting with Optimal Resilience....Pages 16-30
The Computational Power of Beeps....Pages 31-46
Byzantine Fireflies....Pages 47-59
Wait-Freedom is Harder Than Lock-Freedom Under Strong Linearizability....Pages 60-74
Simulating a Shared Register in an Asynchronous System that Never Stops Changing....Pages 75-91
Plane Formation by Synchronous Mobile Robots in the Three Dimensional Euclidean Space....Pages 92-106
Anonymous Graph Exploration with Binoculars....Pages 107-122
Limit Behavior of the Multi-agent Rotor-Router System....Pages 123-139
Elastic Configuration Maintenance via a Parsimonious Speculating Snapshot Solution....Pages 140-153
SmartMerge: A New Approach to Reconfiguration for Atomic Storage....Pages 154-169
Towards Automatic Lock Removal for Scalable Synchronization....Pages 170-184
Inherent Limitations of Hybrid Transactional Memory....Pages 185-199
Why Non-blocking Operations Should be Selfish....Pages 200-214
Hybrid Transactional Memory Revisited....Pages 215-231
Grasping the Gap Between Blocking and Non-Blocking Transactional Memories....Pages 232-247
Fast Consensus for Voting on General Expander Graphs....Pages 248-262
Randomness vs. Time in Anonymous Networks....Pages 263-275
Fast Byzantine Leader Election in Dynamic Networks....Pages 276-291
Local Information in Influence Networks....Pages 292-308
Amalgamated Lock-Elision....Pages 309-324
Transactional Interference-Less Balanced Tree....Pages 325-340
Analyzing the Performance of Lock-Free Data Structures: A Conflict-Based Model....Pages 341-355
A Constructive Approach for Proving Data Structures’ Linearizability....Pages 356-370
Modular Verification of Concurrency-Aware Linearizability....Pages 371-387
Transaction Chopping for Parallel Snapshot Isolation....Pages 388-404
Computing in Additive Networks with Bounded-Information Codes....Pages 405-419
Specifying Concurrent Problems: Beyond Linearizability and up to Tasks....Pages 420-435
From Geometric Semantics to Asynchronous Computability....Pages 436-451
On the Optimal Space Complexity of Consensus for Anonymous Processes....Pages 452-466
Compressing Communication in Distributed Protocols....Pages 467-479
Privacy-Conscious Information Diffusion in Social Networks....Pages 480-496
Fair Distributed Computation of Reactive Functions....Pages 497-512
Smoothed Analysis of Dynamic Networks....Pages 513-527
Fault Tolerant Reachability for Directed Graphs....Pages 528-543
Locally Optimal Load Balancing....Pages 544-558
Distributed Large Independent Sets in One Round on Bounded-Independence Graphs....Pages 559-572
Tight Bounds for MIS in Multichannel Radio Networks....Pages 573-587
Nonuniform SINR+Voroni Diagrams Are Effectively Uniform....Pages 588-601
Stable Leader Election in Population Protocols Requires Linear Time....Pages 602-616
Hardware Transactions in Nonvolatile Memory....Pages 617-630
Space-Optimal Counting in Population Protocols....Pages 631-646
Back Matter....Pages 647-678