Distributed Computing 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24-26, 2007, Proceedings

This book constitutes the refereed proceedings of the 21st International Symposium on Distributed Computing, DISC 2007, held in Lemesos, Cyprus, in September 2007.
The 32 revised full papers, selected from 100 submissions, are presented together with abstracts of 3 invited papers and 9 brief announcements of ongoing works; all of them were carefully selected for inclusion in the book. The papers cover all current issues in distributed computing - theory, design, analysis, implementation, and application of distributed systems and networks - ranging from foundational and theoretical topics to algorithms and systems issues and to applications in various fields. This volume concludes with a section devoted to the 20th anniversary of the DISC conferences that took place during DISC 2006, held in Stockholm, Sweden, in September 2006.

Invited Talks.- Routing and Scheduling with Incomplete Information.- Time-Efficient Broadcasting in Radio Networks.- A Subjective Visit to Selected Topics in Distributed Computing.- Regular Papers.- Bounded Wait-Free Implementation of Optimally Resilient Byzantine Storage Without (Unproven) Cryptographic Assumptions.- A Simple Population Protocol for Fast Robust Approximate Majority.- A Denial-of-Service Resistant DHT.- Mobility Versus the Cost of Geocasting in Mobile Ad-Hoc Networks.- Self-stabilizing Counting in Mobile Sensor Networks with a Base Station.- Scalable Load-Distance Balancing.- Time Optimal Asynchronous Self-stabilizing Spanning Tree.- Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links.- Weakening Failure Detectors for k-Set Agreement Via the Partition Approach.- Amnesic Distributed Storage.- Distributed Approximations for Packing in Unit-Disk Graphs.- From Crash-Stop to Permanent Omission: Automatic Transformation and Weakest Failure Detectors.- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time.- On Self-stabilizing Synchronous Actions Despite Byzantine Attacks.- Gossiping in a Multi-channel Radio Network.- The Space Complexity of Unbounded Timestamps.- Approximating Wardrop Equilibria with Finitely Many Agents.- Energy and Time Efficient Broadcasting in Known Topology Radio Networks.- A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree.- On the Message Complexity of Indulgent Consensus.- Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result.- Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes.- On the Communication Surplus Incurred by Faulty Processors.- Output Stability Versus Time Till Output.- A Distributed Maximal Scheduler for Strong Fairness.- Cost-Aware Caching Algorithms for Distributed Storage Servers.- Push-to-Pull Peer-to-Peer Live Streaming.- Probabilistic Opaque Quorum Systems.- Detecting Temporal Logic Predicates on Distributed Computations.- Optimal On-Line Colorings for Minimizing the Number of ADMs in Optical Networks.- Efficient Transformations of Obstruction-Free Algorithms into Non-blocking Algorithms.- Automatic Classification of Eventual Failure Detectors.- Brief Announcements.- When 3f?+?1 Is Not Enough: Tradeoffs for Decentralized Asynchronous Byzantine Consensus.- On the Complexity of Distributed Greedy Coloring.- Fault-Tolerant Implementations of the Atomic-State Communication Model in Weaker Networks.- Transaction Safe Nonblocking Data Structures.- Long Live Continuous Consensus.- Fully Distributed Algorithms for Convex Optimization Problems.- On the Power of Impersonation Attacks.- Perfectly Reliable and Secure Communication in Directed Networks Tolerating Mixed Adversary.- A Formal Analysis of the Deferred Update Technique.- DISC 20th Anniversary.- DISC at Its 20th Anniversary (Stockholm, 2006).- DISC 20th Anniversary: Invited Talk Time, Clocks, and the Ordering of My Ideas About Distributed Systems.- DISC 20th Anniversary: Invited Talk My Early Days in Distributed Computing Theory: 1979-1982.- DISC 20th Anniversary: Invited Talk Provably Unbreakable Hyper-Encryption Using Distributed Systems.