@Proceedings{disc:2006, title = {Distributed algorithms}, editor = {Shlomi Dolev}, series = {Lecture Notes in Computer Science}, volume = {4167/2006}, publisher = {Springer-Verlag Heidelberg}, year = {2006}, ISBN = {3-540-44624-9}, } @InProceedings{disc:2006-1, author = {Anchour Mostefaoui and Michel Raynal and Corentin Travers}, title = {Exploring Gafni's reduction land: from $\Omega^k$ to wait-free adaptive $(wp - |\frac{p}{k}|) renaming via k-set agreement}, pages = {1--15}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-2, author = {Michael Okun and Amnon Barak}, title = {Renaming in Message Passing Systems with Byzantine Failures}, pages = {16--30}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-3, author = {Hagit Attiya and Eschar Hillel}, title = {Built-in Coloring for Highly-Concurrent Doubly-Linked Lists}, pages = {31--45}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-4, author = {Xavier Defago and Maria Gradinariu and Stephane Messika and Philippe Raipin-Parvedy}, title = {Fault-tolerant and Self-stabilizing Mobile Robots Gathering}, pages = {46--60}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-5, author = {Dana Angluin and James Aspnes and David Eisenstat}, title = {Fast Computation by Population Protocols With a Leader}, pages = {61--75}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-6, author = {Doina Bein and Ajoy K. Datta and Lawrence L. Larmore}, title = {On Self-stabilizing Search Trees}, pages = {76--89}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-7, author = {Yitzhak Birk and Idit Keidar and Liran Liss and Assaf Schuster}, title = {Efficient Dynamic Aggregation}, pages = {90--104}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-8, author = {J{\'{e}}r{\'{e}}mie Chalopin and Shantanu Das and Nicola Santoro}, title = {Groupings and Pairings in Anonymous Networks}, pages = {105--119}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-9, author = {Yoram Moses and Benny Shimony}, title = {A New Proof of the GHS Minimum Spanning Tree Algorithm}, pages = {120--136}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-10, author = {Joseph Y. Halpern and Sabina Petride}, title = {A Knowledge-Based Analysis of Global Function Computation}, pages = {136--150}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-11, author = {Leslie Lamport}, title = {Checking a Multithreaded Algorithm with +CAL}, pages = {151--163}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-12, author = {Lisa Higham and LillAnne Jackson and Jalal Kawash}, title = {Capturing Register and Control Dependence in Memory Consistency Models with Applications to the Itanium Architecture}, pages = {164--178}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-13, author = {Michael F. Spear and Virendra J. Marathe and William N. Scherer III and Michael L. Scott}, title = {Conflict Detection and Validation Strategies for Software Transactional Memory}, pages = {179--193}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-14, author = {David Dice and Ori Shalev and Nir Shavit}, title = {Transactional Locking II}, pages = {194--208}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-15, author = {Yehuda Afek and Eran Shalom}, title = {Less Is More: Consensus Gaps Between Restricted and Unrestricted Objects}, pages = {209--223}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-16, author = {Taisuke Izumi and Toshimitsu Masuzawa}, title = {One-Step Consensus Solvability}, pages = {224--237}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-17, author = {Ran Canetti and Ling Cheung and Dilsun Kirli Kaynar and Moses Liskov and Nancy A. Lynch and Olivier Pereira and Roberto Segala}, title = {Time-Bounded Task-PIOAs: A Framework for Analyzing Security Protocols}, pages = {238--253}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-18, author = {Alina Oprea and Michael K. Reiter}, title = {On Consistency of Encrypted Files}, pages = {254--268}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-19, author = {Michael B. Greenwald and Sanjeev Khanna and Keshav Kunal and Benjamin C. Pierce and Alan Schmitt}, title = {Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data}, pages = {269--283}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-20, author = {Torvald Riegel and Pascal Felber and Christof Fetzer}, title = {A Lazy Snapshot Algorithm with Eager Validation}, pages = {284--298}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-21, author = {Rida A. Bazzi and Yin Ding}, title = {Bounded Wait-Free f-Resilient Atomic Byzantine Data Storage Systems for an Unbounded Number of Clients}, pages = {299--313}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-22, author = {Bogdan S. Chlebus and Dariusz R. Kowalski}, title = {Time and Communication Efficient Consensus for Crash Failures}, pages = {314--328}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-23, author = {Eli Gafni and Sergio Rajsbaum and Maurice Herlihy}, title = {Subconsensus Tasks: Renaming Is Weaker Than Set Agreement}, pages = {329--338}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-24, author = {Arthur Brady and Lenore Cowen}, title = {Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes}, pages = {339--354}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-25, author = {Maleq Khan and Gopal Pandurangan}, title = {A Fast Distributed Approximation Algorithm for Minimum Spanning Trees}, pages = {355--369}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-26, author = {Robert Els{\"{a}}sser}, title = {On Randomized Broadcasting in Power Law Networks}, pages = {370--384}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-27, author = {Andrzej Czygrinow and Michal Hanckowiak}, title = {Distributed Approximation Algorithms in Unit-Disk Graphs}, pages = {385--398}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-28, author = {Rachid Guerraoui and Michal Kapalka and Petr Kouznetsov}, title = {The Weakest Failure Detectors to Boost Obstruction-Freedom}, pages = {399--412}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-29, author = {Alex Brodsky and Faith Ellen and Philipp Woelfel}, title = {Fully-Adaptive Algorithms for Long-Lived Renaming}, pages = {413--427}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-30, author = {Danny Hendler and Shay Kutten}, title = {Constructing Shared Objects That Are Both Robust and High-Throughput}, pages = {428--442}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-31, author = {Amitanand S. Aiyer and Lorenzo Alvisi and Rida A. Bazzi}, title = {Byzantine and Multi-writer K-Quorums}, pages = {443--458}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-32, author = {Michele Flammini and Mordechai Shalom and Shmuel Zaks}, title = {On Minimizing the Number of ADMs in a General Topology Optical Network}, pages = {459--473}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-33, author = {Kishori M. Konwar and Sanguthevar Rajasekaran and Alexander A. Shvartsman}, title = {Robust Network Supercomputing with Malicious Processes}, pages = {474--488}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-34, author = {Cathy H. Xia and James Broberg and Zhen Liu and Li Zhang}, title = {Distributed Resource Allocation in Stream Processing Systems}, pages = {489--504}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-35, author = {Piotr Zielinski}, title = {Low-latency Atomic Broadcast in the presence of contention}, pages = {505--519}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-36, author = {Thomas Locher and Roger Wattenhofer}, title = {Oblivious Gradient Clock Synchronization}, pages = {520--533}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-37, author = {Marcos Kawazoe Aguilera and Svend Fr{\o}lund and Vassos Hadzilacos and Stephanie Lorraine Horn and Sam Toueg}, title = {Abortable and Query-Abortable Objects}, pages = {534--536}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-38, author = {Nicolas C. Nicolaou and Alexander A. Shvartsman}, title = {Fault-Tolerant SemiFast Implementations of Atomic Read/Write Registers}, pages = {537--539}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-39, author = {Bassam Bamieh and Amr El Abbadi}, title = {Convergence Analysis of Scalable Gossip Protocols}, pages = {540--542}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-40, author = {Colette Johnen and St{\'{e}}phane Messika}, title = {Computing Automatically the Stabilization Time Against the Worst and the Best Schedules}, pages = {543--547}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-41, author = {A. Ogale and Vijay K. Garg}, title = {Many Slices Are Better Than One}, pages = {548--550}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-42, author = {Pierre Fraigniaud and Emmanuelle Lebhar and Zvi Lotker}, title = {On Augmented Graph Navigability}, pages = {551--553}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-43, author = {Alysson Neves Bessani and Miguel Correia and Joni da Silva Fraga and Lau Cheuk Lung}, title = {Decoupled Quorum-Based Byzantine-Resilient Coordination in Open Distributed Systems}, pages = {554--556}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-44, author = {Nicolas Schiper and Rodrigo Schmidt and Fernando Pedone}, title = {Optimistic Algorithms for Partial Database Replication}, pages = {557--559}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-45, author = {Frederic Tronel and Spyros Voulgari}, title = {Performance Analysis of Cyclon, an Inexpensive Membership Management for Unstructured P2P Overlays}, pages = {560--562}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-46, author = {Yu Chen and Wei Chen}, title = {Decentralized, Connectivity-Preserving, and Cost-Effective Structured Overlay Maintenance}, pages = {563--565}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-47, author = {Anton Esin and Rostislav Yavorskiy and Nikolay Zemtsov}, title = {Monitoring of Linear Distributed Computations}, pages = {563--565}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-48, author = {Mikel Larrea and Alberto Lafuenten and Joachim Wieland}, title = {Communication-Optimal Implementation of Failure Detector Class diamond-P}, pages = {569--571}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-49, author = {Srinivasan Krishnamurthy and R. Chandrasekaran and Neeraj Mittal and S. Venkatesan}, title = {Synchronous Distributed Algorithms for Node Discovery and Configuration in Multi-channel Cognitive Radio Networks}, pages = {572--574}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, } @InProceedings{disc:2006-50, author = {Maleq Khan and Gopal Pandurangan}, title = {A Fast Distributed Approximation Algorithm for Minimum Spanning Trees}, pages = {355--369}, booktitle = {Distributed algorithms}, editor = {Shlomi Dolev}, year = {2006}, month = {September}, volume = {4167/2006}, ISBN = {3-540-44624-9}, pubisher = {Springer-Verlag Heidelberg}, series = {Lecture Notes in Computer Science}, }