Distributed Computing: 20th International Symposium, DISC 2006, Stockholm, Sweden, September 18-20, 2006, ProceedingsShlomi Dolev 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 |
Common terms and phrases
abcast agents assume atomic Atomic Broadcast Attiya Broadcast Byzantine Byzantine failures communication complexity Computer Science concurrent conflict consensus number consider contention manager convergence correct process crash data structure defined denote DISC distributed algorithm Distributed Computing Dolev edge encrypted file execution failure detector function GHS algorithm global graph G guarantees hard-core predicate Herlihy implementation initial input interval graphs Itanium labels Lemma linearizable LNCS lock logical clock lower bound neg,pt neighbors node O(log path perform phase polylogarithmic probabilistic problem Proc processors proof properties protocol queue quorum random random graph read operation reader red-black tree registers replica result robots round scheduler sequence servers skew software transactional memory solution step synchronization task task-PIOA Theorem timestamp tion transactional memory tree tuple update validation variable vertex vertices wait-free write operations writeback