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

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
Randomized Consensus in Expected O ( n 2 ) Total Work Using Single-Writer Registers....Pages 363-373
Structured Derivation of Semi-Synchronous Algorithms....Pages 374-388
Byzantine Agreement Using Partial Authentication....Pages 389-403
On Approximate Distance Labels and Routing Schemes with Affine Stretch....Pages 404-415
The Complexity of Data Aggregation in Directed Networks....Pages 416-431
Black Hole Search with Finite Automata Scattered in a Synchronous Torus....Pages 432-446
Synchronous Rendezvous for Location-Aware Agents....Pages 447-459
Toward a Formal Semantic Framework for Deterministic Parallel Programming....Pages 460-474
CAFÉ: Scalable Task Pools with Adjustable Fairness and Contention....Pages 475-488
Oblivious Collaboration....Pages 489-504
Back Matter....Pages -