Ebook: Distributed Computing: 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011. Proceedings

This book constitutes the refereed proceedings of the 25th International Symposium on Distributed Computing, DISC 2011, held in Rome, Italy, in September 2011. The 31 revised full papers presented together with invited lectures and brief announcements were carefully reviewed and selected from 136 submissions. The papers are organized in topical sections on distributed graph algorithms; shared memory; brief announcements; fault-tolerance and security; paxos plus; wireless; network algorithms; aspects of locality; consensus; concurrency.

---

This book constitutes the refereed proceedings of the 25th International Symposium on Distributed Computing, DISC 2011, held in Rome, Italy, in September 2011. The 31 revised full papers presented together with invited lectures and brief announcements were carefully reviewed and selected from 136 submissions. The papers are organized in topical sections on distributed graph algorithms; shared memory; brief announcements; fault-tolerance and security; paxos plus; wireless; network algorithms; aspects of locality; consensus; concurrency.

---

This book constitutes the refereed proceedings of the 25th International Symposium on Distributed Computing, DISC 2011, held in Rome, Italy, in September 2011. The 31 revised full papers presented together with invited lectures and brief announcements were carefully reviewed and selected from 136 submissions. The papers are organized in topical sections on distributed graph algorithms; shared memory; brief announcements; fault-tolerance and security; paxos plus; wireless; network algorithms; aspects of locality; consensus; concurrency.
Content:
Front Matter....Pages -
DISC 2011 Invited Lecture: Deterministic Rendezvous in Networks: Survey of Models and Results....Pages 1-15
Fast and Scalable Rendezvousing....Pages 16-31
Beeping a Maximal Independent Set....Pages 32-50
Trading Bit, Message, and Time Complexity of Distributed Algorithms....Pages 51-65
Combinatorial Algorithms for Distributed Graph Coloring....Pages 66-81
Physical Expander in Virtual Tree Overlay....Pages 82-96
Sub-logarithmic Test-and-Set against a Weak Adversary....Pages 97-109
Tight Space Bounds for ?-Exclusion....Pages 110-124
SMV: Selective Multi-Versioning STM....Pages 125-140
Brief Announcement: Leaderless Byzantine Paxos....Pages 141-142
Brief Announcement: When You Don’t Trust Clients: Byzantine Proposer Fast Paxos....Pages 143-144
Brief Announcement: On the Meaning of Solving a Task with a Failure Detector....Pages 145-146
Brief Announcement: Algorithmic Mechanisms for Internet-Based Computing under Unreliable Communication....Pages 147-149
Maximum Metric Spanning Tree Made Byzantine Tolerant....Pages 150-164
Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts....Pages 165-180
Leakage-Resilient Coin Tossing....Pages 181-196
Brief Announcement: Composition Games for Distributed Systems: The EU Grants Games....Pages 197-199
Brief Announcement: Distributed Approximations for the Semi-matching Problem....Pages 200-201
Brief Announcement: Opportunistic Information Dissemination in Mobile Ad-Hoc Networks:....Pages 202-204
Brief Announcement: Bridging the Theory-Practice Gap in Multi-commodity Flow Routing....Pages 205-207
DISC 2011 Invited Lecture by Dahlia Malkhi: Going beyond Paxos....Pages 208-210
Byzantizing Paxos by Refinement....Pages 211-224
Unbounded Contention Resolution in Multiple-Access Channels....Pages 225-236
Deterministic and Energy-Optimal Wireless Synchronization....Pages 237-251
Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast....Pages 252-267
Leader Election Using Loneliness Detection....Pages 268-282
Optimal Random Sampling from Distributed Streams Revisited....Pages 283-297
Parsimonious Flooding in Geometric Random-Walks....Pages 298-310
Misleading Stars: What Cannot Be Measured in the Internet?....Pages 311-325
Brief Announcement: A Randomized Algorithm for Label Assignment in Dynamic Networks....Pages 326-327
Brief Announcement: ??: Specifying an Eventual Leader Service for Dynamic Systems....Pages 328-329
Brief Announcement: The BG-Simulation for Byzantine Mobile Robots....Pages 330-331
DISC 2011 Invited Lecture: Polygon Reconstruction with Little Information: An Example for the Power of Simple Micro-robots....Pages 332-332
Locality and Checkability in Wait-Free Computing....Pages 333-347
The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement....Pages 348-362
Structured Derivation of Semi-Synchronous Algorithms....Pages 363-373
Byzantine Agreement Using Partial Authentication....Pages 374-388
On Approximate Distance Labels and Routing Schemes with Affine Stretch....Pages 389-403
The Complexity of Data Aggregation in Directed Networks....Pages 404-415
Black Hole Search with Finite Automata Scattered in a Synchronous Torus....Pages 416-431
Synchronous Rendezvous for Location-Aware Agents....Pages 432-446
Toward a Formal Semantic Framework for Deterministic Parallel Programming....Pages 447-459
CAF?: Scalable Task Pools with Adjustable Fairness and Contention....Pages 460-474
Oblivious Collaboration....Pages 475-488
Back Matter....Pages 489-504
....Pages -