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. This book constitutes the refereed proceedings of the 21st International Symposium on Distributed Computing, DISC 2007. The 32 revised full papers, presented together with abstracts of three invited papers and nine brief announcements of ongoing works, cover all current issues in distributed computing, including theory, design, analysis, implementation, and application of distributed systems and networks. Coverage ranges from theoretical topics to applications in various fields. Invited Talks Routing and Scheduling with Incomplete Information 1 Burkhard Monien and Karsten Tiemann Time-Efficient Broadcasting in Radio Networks 3 David Peleg A Subjective Visit to Selected Topics in Distributed Computing 5 Michel Raynal Regular Papers Bounded Wait-Free Implementation of Optimally Resilient Byzantine Storage Without (Unproven) Cryptographic Assumptions 7 Amitanand S. Aiyer, Lorenzo Alvisi, and Rida A. Bazzi A Simple Population Protocol for Fast Robust Approximate Majority 20 Dana Angluin, James Aspnes, and David Eisenstat A Denial-of-Service Resistant DHT 33 Baruch Awerbuch and Christian Scheideler Mobility Versus the Cost of Geocasting in Mobile Ad-Hoc Networks 48 Roberto Baldoni, Kleoni Ioannidou, and Alessia Milani Self-stabilizing Counting in Mobile Sensor Networks with a Base Station 63 Joffroy Beauguier, Julien Clement, Stephane Messika, Laurent Rosaz, and Brigitte Rozoy Scalable Load-Distance Balancing 77 Edward Bortnikov, Israel Cidon, and Idit Keidar Time Optimal Asynchronous Self-stabilizing Spanning Tree 92 Janna Burman and Shay Kutten Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links 108 J mie Chalopin, Shantanu Das, and Nicola Santoro Weakening Failure Detectors for k-Set Agreement Via the Partition Approach 123 Wei Chen, Jialin Zhang, Ye Chen, and Xuezheng Liu Amnesic Distributed Storage 139 Gregory Chockler, Rachid Guerraoui, and Idit Keidar Distributed Approximations for Packing in Unit-Disk Graphs 152 Andrzej Czygrinow and Michal Hanckowiak From Crash-Stop to Permanent Omission: Automatic Transformation and Weakest Failure Detectors 165 Carole Delporte-Gallet, Hugues Fauconnier, Felix C. Freiling, Lucia Draque Penso, and Andreas Tielmann Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time 179 Bilel Derbel, Cyril Gavoille, and David Peleg On Self-stabilizing Synchronous Actions Despite Byzantine Attacks 193 Danny Dolev and Ezra N. Hoch Gossiping in a Multi-channel Radio Network: An Oblivious Approach to Coping with Malicious Interference (Extended Abstract) 208 Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport The Space Complexity of Unbounded Timestamps 223 Faith Ellen, Panagiota Fatourou, and Eric Ruppert Approximating Wardrop Equilibria with Finitely Many Agents 238 Simon Fischer, Lars Myrick and Berthold V cking Energy and Time Efficient Broadcasting in Known Topology Radio Networks 253 Leszek Gasieniec, Erez Kantor, Dariusz R. Kowalski, David Peleg, and Chang Su A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree 268 Beat Gfeller, Nicola Santoro, and Peter Widmayer On the Message Complexity of Indulgent Consensus 283 Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result 298 Taisuke Izumi, Yoshiaki Katayaina, Nobuhiro Inuzuka, and Koichi Wada Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes 313 Amos Korman and David Peleg On the Communication Surplus Incurred by Faulty Processors 328 Dariusz R. Kowalski and Michal Strojnowski Output Stability Versus Time Till Output (Extended Abstract) 343 Shay Kutten, and Toshimitsu Masuzawa A DistributedMaximal Scheduler for Strong Fairness 358 Matthew Lang and Paolo A.G. Sivilotti Cost-Aware Caching Algorithms for Distributed Storage Servers 373 Shuang Liang, Ke Chen, Song Jiang, and Xiaodong Zhang Push-to-Pull Peer-to-Peer Live Streaming 388 Thomas Locher, Remo Meier, Stefan Schmid, and Roger Wattenhofer Probabilistic Opaque Quorum Systems 403 Michael G. Merideth and Michael K. Reiter Detecting Temporal Logic Predicates on Distributed Computations 420 Vinit A. Ogale and Vijay K. Garg Optimal On-Line Colorings for Minimizing the Number of ADMs in Optical Networks (Extended Abstract) 435 Mordechai Shalom, Prudence W.H. Wong, and Shmuel Zaks Efficient Transformations of Obstruction-Free Algorithms into Non-blocking Algorithms 450 Gadi Taubenfeld Automatic Classification of Eventual Failure Detectors 465 Piotr Zielinski Brief Announcements When 3 + 1 Is Not Enough: Tradeoffs for Decentralized Asynchronous Byzantine Consensus 480 Alysson Neves Bessani, Miguel Correia, Henrique Moniz, Nuno Ferreira, Neves, and Paulo Verissimo On the Complexity of Distributed Greedy Coloring 482 Cyril Gavoille, Ralf Klasing, Adrian Kosowski, and Alfredo Navarra Fault-Tolerant Implementations of the Atomic-State Communication Model in Weaker Networks 485 Colette Johnen and Lisa Higham Transaction Safe Nonblocking Data Structures 488 Virendra J. Marathe, Michael F. Spear, and Michael L. Scott Long Live Continuous Consensus 490 Tal Mizrahi and Yoram Moses Fully Distributed Algorithms for Convex Optimization Problems 492 Damon Mosk-Aoyama, Tim Roughgarden, and Devavrat Shah On the Power of Impersonation Attacks 494 Michael Okun Perfectly Reliable and Secure Communication in Directed Networks Tolerating Mixed Adversary 496 Arpita Patra, Ashish Choudhary, Kannan Srinathan, and Chandrasekharan Pandu Rangan A Formal Analysis of the Deferred Update Technique 499 Rodrigo Schmidt and Fernando Pedone DISC 20th Anniversary DISC at Its 20th Anniversary (Stockholm, 2006) 501 Michel Raynal, Sam Toueg, and Shmuel Zaks Time, Clocks, and the Ordering of My Ideas About Distributed Systems (DISC 20th Anniversary: Invited Talk) 504 Leslie Lamport My Early Days in Distributed Computing Theory: 1979-1982 (DISC 20th Anniversary: Invited Talk) 505 Nancy Lynch Provably Unbreakable Hyper-Encryption Using Distributed Systems (DISC 20th Anniversary: Invited Talk) 506 Michael O. Rabin Author Index 509