This book consitutes the refereed proceedings of the 15th International Conference on Distributed Computing, DISC 2001, held in Lisbon, Portugal, in October 2001.
The 23 revised papers presented were carefully reviewed and selected from 70 submissions. Among the issues addressed are mutual exclusion, anonymous networks, distributed files systems, information diffusion, computation slicing, commit services, renaming, mobile search, randomized mutual search, message-passing networks, distributed queueing, leader election algorithms, Markov chains, network routing, ad-hoc mobile networks, and adding networks.
Author(s): Yong-Jik Kim, James H. Anderson (auth.), Jennifer Welch (eds.)
Series: Lecture Notes in Computer Science 2180
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2001
Language: English
Pages: 346
Tags: Special Purpose and Application-Based Systems; Algorithm Analysis and Problem Complexity; Programming Techniques; Computation by Abstract Devices; Operating Systems
A Time Complexity Bound for Adaptive Mutual Exclusion....Pages 1-15
Quorum-Based Algorithms for Group Mutual Exclusion....Pages 16-32
An Effective Characterization of Computability in Anonymous Networks....Pages 33-47
Competitive Hill-Climbing Strategies for Replica Placement in a Distributed File System....Pages 48-62
Optimal Unconditional Information Diffusion....Pages 63-77
Computation Slicing: Techniques and Theory....Pages 78-92
A Low-Latency Non-blocking Commit Service....Pages 93-107
Stable Leader Election....Pages 108-122
Adaptive Long-lived O ( k 2 )-Renaming with O ( k 2 ) Steps....Pages 123-135
A New Synchronous Lower Bound for Set Agreement....Pages 136-150
The Complexity of Synchronous Iterative Do-All with Crashes....Pages 151-165
Mobile Search for a Black Hole in an Anonymous Ring....Pages 166-179
Randomised Mutual Search for k > 2 Agents....Pages 180-193
Self-stabilizing Minimum Spanning Tree Construction on Message-Passing Networks....Pages 194-208
Self Stabilizing Distributed Queuing....Pages 209-223
A Space Optimal, Deterministic, Self-stabilizing, Leader Election Algorithm for Unidirectional Rings....Pages 224-239
Randomized Finite-state Distributed Algorithms As Markov Chains....Pages 240-254
The Average Hop Count Measure For Virtual Path Layouts....Pages 255-269
Efficient Routing in Networks with Long Range Contacts....Pages 270-284
An Efficient Communication Strategy for Ad-hoc Mobile Networks....Pages 285-299
A Pragmatic Implementation of Non-blocking Linked-lists....Pages 300-314
Stabilizing Replicated Search Trees....Pages 315-329
Adding Networks....Pages 330-341
