Distributed Computing: 20th International Symposium, DISC 2006, Stockholm, Sweden, September 18-20, 2006, Proceedings

Front Cover
Shlomi Dolev
Springer Science & Business Media, Sep 18, 2006 - Computers - 576 pages
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.
 

Contents

From Ωk to WaitFree Adaptive
1
1
16
Efficient Dynamic
90
Groupings and Pairings in Anonymous Networks Jérémie Chalopin Shantanu Das Nicola Santoro
105
Yoram Moses Benny Shimony
120
Capturing Register and Control Dependence in Memory Consistency
164
Conflict Detection and Validation Strategies for Software Transactional
179
Transactional Locking II
194
On Randomized Broadcasting in Power Law Networks Robert Elsässer
370
Distributed Approximation Algorithms in UnitDisk Graphs A Czygrinow M Hanckowiak
385
The Weakest Failure Detectors to Boost ObstructionFreedom Rachid Guerraoui Michal Kapalka Petr Kouznetsov
399
FullyAdaptive Algorithms for LongLived Renaming Alex Brodsky Faith Ellen Philipp Woelfel
413
Constructing Shared Objects That Are Both Robust
428
Byzantine and Multiwriter KQuorums
443
On Minimizing the Number of ADMs in a General Topology Optical
459
Robust Network Supercomputing with Malicious Processes
474

Consensus Gaps Between Restricted and Unrestricted
209
OneStep Consensus Solvability
224
A Framework for Analyzing Security
238
On Consistency of Encrypted Files
254
Conflict Resolution for Optimistically Replicated
269
A Lazy Snapshot Algorithm with Eager Validation Torvald Riegel Pascal Felber Christof Fetzer
284
Bounded WaitFree fResilient Atomic Byzantine Data Storage
299
Time and Communication Efficient Consensus for Crash Failures Bogdan S Chlebus Dariusz R Kowalski
314
Renaming Is Weaker Than Set Agreement
329
A Fast Distributed Approximation Algorithm for Minimum Spanning
355
Distributed Resource Allocation in Stream Processing
489
LowLatency Atomic Broadcast in the Presence of Contention
505
Oblivious Gradient Clock Thomas Locher Roger Wattenhofer Synchronization
520
Abortable and QueryAbortable Objects Marcos K Aguilera Svend Frolund Vassos Hadzilacos
534
FaultTolerant SemiFast Implementations
537
On Augmented Graph Navigability
551
Monitoring of Linear Distributed
566
Synchronous Distributed Algorithms for Node
572
Copyright

Common terms and phrases