Distributed Computing

DISC, the International Symposium on DIStributed Computing, is an annual conference for the presentation of research on the theory, design, analysis, implementation,andapplicationofdistributedsystemsandnetworks.DISC2003 was held on October 1 3, 2003 in Sorrento, Italy. There were 91 regular papers submitted to DISC this year. These were read and evaluated by the program committee members, assisted by external reviewers. The quality of submissions was high and we were unable to accept many deserving papers. Twenty-?ve papers were selected by the program c- mittee to be included in these proceedings. It is expected that these papers will be submitted, in a more polished form, to fully refereed scienti?c journals. TheBestStudentPaperAwardwasselectedfromamongtheacceptedpapers that were not co-authored by any program committee members. This year, the award was given to Ittai Abraham for the paper Probabilistic Quorums for Dynamic Systems , co-authored with Dahlia Malkhi. The support of the University of Salerno, Italy and, in particular, its Dip- timento di Informatica ed Applicazioni is gratefully acknowledged. The review process and the preparation of this volume were done using CyberChair. I also thank Denise Lobo for her excellent help with these matters. October 2003 Faith Ellen Fich Organizing Committee Luigi Catuogno, University of Salerno, Italy Stelvio Cimato, University of Salerno, Italy Roberto De Prisco, University of Salerno, Italy and Akamai Technologies, USA (Chair) Barbara Masucci, University of Salerno, Italy DISC2003wassponsoredbytheUniversityof Salerno, Italy and, inparticular,itsDipartimentodiInformatica ed Applicazioni.

Inhalt
Resilient Consensus for Infinitely Many Processes.- Uniform Solvability with a Finite Number of MWMR Registers.- Timing-Based Mutual Exclusion with Local Spinning.- On the Uncontended Complexity of Consensus.- Probabilistic Quorums for Dynamic Systems.- Efficient Replication of Large Data Objects.- On the Locality of Consistency Conditions.- Multi-writer Consistency Conditions for Shared Memory Objects.- Booting Clock Synchronization in Partially Synchronous Systems.- Automatic Discovery of Mutual Exclusion Algorithms.- On the Implementation Complexity of Specifications of Concurrent Programs.- Competitive Management of Non-preemptive Queues with Multiple Values.- Constructing Disjoint Paths for Secure Communication.- Compact Routing for Flat Networks.- Lower Bounds for Oblivious Single-Packet End-to-End Communication.- Efficient Gossip and Robust Distributed Computation.- Condition-Based Consensus in Synchronous Systems.- Using Conditions to Expedite Consensus in Synchronous Distributed Systems.- Tight Bounds on Early Local Decisions in Uniform Consensus.- Tight Bounds for k-Set Agreement with Limited-Scope Failure Detectors.- On Failure Detectors and Type Boosters.- GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks.- Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks.- Maximizing Remote Work in Flooding-Based Peer-to-Peer Systems.- Overcoming the Majority Barrier in Large-Scale Systems.