DISC, the International Symposium on DIStributed Computing, is an annual forum for presentation of research on all facets of distributed computing, inc- ding the theory, design, analysis, implementation, and application of distributed systems and networks. The 20th anniversary edition of DISC was held on S- tember 18-20, 2006, in Stockholm, Sweden. There were 145 extended abstracts submitted to DISC this year, and this - lume contains the 35 contributions selected by the Program Committee and one invited paper among these 145 submissions. All submitted papers were read and evaluated by at least three Program Committee members, assisted by external reviewers. The ?nal decision regarding every paper was taken during the P- gram Committee meeting, which took place in Beer-Sheva, June 30 and July 1, 2006. The Best Student Award was split and given to two papers: the paper “- act Distance Labelings Yield Additive-Stretch Compact Routing Schemes,” by Arthur Bradly, and Lenore Cowen, and the paper “A Fast Distributed App- ximation Algorithm for Minimum Spanning Trees” co-authored by Maleq Khan and Gopal Pandurangan. The proceedings also include 13 three-page-long brief announcements (BA). TheseBAsarepresentationsofongoingworksforwhichfullpapersarenotready yet, or of recent results whose full description will soon be or has been recently presented in other conferences. Researchers use the BA track to quickly draw the attention of the community to their experiences, insights and results from ongoing distributed computing research and projects. The BAs included in this proceedings volume were selected among 26 BA submissions.
Author(s): Achour Mostefaoui, Michel Raynal, Corentin Travers (auth.), Shlomi Dolev (eds.)
Series: Lecture Notes in Computer Science 4167 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2006
Language: English
Pages: 580
Tags: Computer Communication Networks; Algorithm Analysis and Problem Complexity; Programming Techniques; Computation by Abstract Devices; Operating Systems
Front Matter....Pages -
Exploring Gafni’s Reduction Land: From Ω k to Wait-Free Adaptive $(2p-\lceil\frac{p}{k}\rceil)$ -Renaming Via k -Set Agreement....Pages 1-15
Renaming in Message Passing Systems with Byzantine Failures....Pages 16-30
Built-In Coloring for Highly-Concurrent Doubly-Linked Lists....Pages 31-45
Fault-Tolerant and Self-stabilizing Mobile Robots Gathering....Pages 46-60
Fast Computation by Population Protocols with a Leader....Pages 61-75
On Self-stabilizing Search Trees....Pages 76-89
Efficient Dynamic Aggregation....Pages 90-104
Groupings and Pairings in Anonymous Networks....Pages 105-119
A New Proof of the GHS Minimum Spanning Tree Algorithm....Pages 120-135
A Knowledge-Based Analysis of Global Function Computation....Pages 136-150
Checking a Multithreaded Algorithm with + CAL....Pages 151-163
Capturing Register and Control Dependence in Memory Consistency Models with Applications to the Itanium Architecture....Pages 164-178
Conflict Detection and Validation Strategies for Software Transactional Memory....Pages 179-193
Transactional Locking II....Pages 194-208
Less Is More: Consensus Gaps Between Restricted and Unrestricted Objects....Pages 209-223
One-Step Consensus Solvability....Pages 224-237
Time-Bounded Task-PIOAs: A Framework for Analyzing Security Protocols....Pages 238-253
On Consistency of Encrypted Files....Pages 254-268
Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data....Pages 269-283
A Lazy Snapshot Algorithm with Eager Validation....Pages 284-298
Bounded Wait-Free f -Resilient Atomic Byzantine Data Storage Systems for an Unbounded Number of Clients....Pages 299-313
Time and Communication Efficient Consensus for Crash Failures....Pages 314-328
Subconsensus Tasks: Renaming Is Weaker Than Set Agreement....Pages 329-338
Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes....Pages 339-354
A Fast Distributed Approximation Algorithm for Minimum Spanning Trees....Pages 355-369
On Randomized Broadcasting in Power Law Networks....Pages 370-384
Distributed Approximation Algorithms in Unit-Disk Graphs....Pages 385-398
The Weakest Failure Detectors to Boost Obstruction-Freedom....Pages 399-412
Fully-Adaptive Algorithms for Long-Lived Renaming....Pages 413-427
Constructing Shared Objects That Are Both Robust and High-Throughput....Pages 428-442
Byzantine and Multi-writer K-Quorums....Pages 443-458
On Minimizing the Number of ADMs in a General Topology Optical Network....Pages 459-473
Robust Network Supercomputing with Malicious Processes....Pages 474-488
Distributed Resource Allocation in Stream Processing Systems....Pages 489-504
Low-latency Atomic Broadcast in the presence of contention....Pages 505-519
Oblivious Gradient Clock Synchronization....Pages 520-533
Brief Announcement: Abortable and Query-Abortable Objects....Pages 534-536
Brief Announcement: Fault-Tolerant SemiFast Implementations of Atomic Read/Write Registers....Pages 537-539
Brief Announcement: Convergence Analysis of Scalable Gossip Protocols....Pages 540-542
Brief Announcement: Computing Automatically the Stabilization Time Against the Worst and the Best Schedules....Pages 543-547
Brief Announcement: Many Slices Are Better Than One....Pages 548-550
Brief Announcement: On Augmented Graph Navigability....Pages 551-553
Brief Announcement: Decoupled Quorum-Based Byzantine-Resilient Coordination in Open Distributed Systems....Pages 554-556
Brief Announcement: Optimistic Algorithms for Partial Database Replication....Pages 557-559
Brief Announcement: Performance Analysis of Cyclon, an Inexpensive Membership Management for Unstructured P2P Overlays....Pages 560-562
Brief Announcement: Decentralized, Connectivity-Preserving, and Cost-Effective Structured Overlay Maintenance....Pages 563-565
Brief Announcement Monitoring of Linear Distributed Computations....Pages 566-568
Brief Announcement: Communication-Optimal Implementation of Failure Detector Class $\diamond{\mathcal P}$ ....Pages 569-571
Brief Announcement: Synchronous Distributed Algorithms for Node Discovery and Configuration in Multi-channel Cognitive Radio Networks....Pages 572-574
Provably Unbreakable Hyper-encryption Using Distributed Systems....Pages 575-577
Time, Clocks, and the Ordering of My Ideas About Distributed Systems....Pages 578-578
My Early Days in Distributed Computing Theory: 1979–1982....Pages 579-579
Panel on the Contributions of the DISC Community to Distributed Computing: A Historical Perspective....Pages 580-580
DISC at Its 20th Anniversary:Past, Present and Future ....Pages 581-583
DISC at Its 20th Anniversary: Past, Present and Future....Pages E1-E1
Back Matter....Pages -
