Accepted Papers DISC 2004


Regular Papers

Coupling and Self-Stabilization

Laurent Fribourg, Stephane Messika, Claudine Picaronny

Efficient Adaptive Collect using Randomization

Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, Roger Wattenhofer


Eli Gafni

Dynamic Memory ABP Work-Stealing

Danny Hendler, Yossi Lev, Nir Shavit

Bounded Version Vectors

Jose Bacelar Almeida, Paulo Sergio Almeida, Carlos Baquero

Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems

James Aspnes, Faith Fich, Eric Ruppert

Non-Skipping Timestamps for Byzantine Data Storage Systems

Rida Bazzi, Yin Ding

Fault-Tolerant Storage in a Dynamic Environment

Uri Nadav, Moni Naor

Nonblocking Concurrent Data Structures with Condition Synchronization

William N.Scherer III, Michael L.Scott

Message-Optimal and Latency-Optimal Termination Detection Algorithms for Arbitrary Topologies

Neeraj Mittal, Sathya Peri, Subbarayan Venkatesan

Active and Concurrent Topology Maintenance

Xiaozhou Li, Jayadev Misra, Greg Plaxton

A Single-Enqueuer Wait-Free Queue Implementation

Matei David

Routing with Improved Communication-Space Trade-Off

Ittai Abraham, Cyril Gavoille, Dahlia Malkhi

Optimal Self-stabilizing Mutual Exclusion on Synchronous Rings

Philippe Duchon, Nicolas Hanusse, Sebastien Tixeuil

The Black-White Bakery Algorithm

Gadi Taubenfeld

An Optimistic Approach to Lock-Free FIFO Queues

Edya Ladan-Mozes, Nir Shavit

Distributed Weighted Matching

Mirjam Wattenhofer, Roger Wattenhofer

Synchronous Condition-based Consensus Adapting to Input-vector Legality

Taisuke Izumi, Toshimitsu Masuzawa

Optimal Dispersal of Certificate Chains

Ehab Elmallah, Mohamed Gouda, Eunjin Jung

Fast and Low Cost P2P Searching by Exploiting Localities in Peer Community and Individual Peers

Lei Guo, Song Jiang, Li Xiao, Xiaodong Zhang

Local-Spin Group Mutual Exclusion Algorithms

Robert Danek, Vassos Hadzilacos

Compact Routing Schemes for Tree-Length $\delta$ Graphs and for $k$-chordal Graphs

Yon Dourisboure

Efficient Verification for Provably Secure Storage and Secret Sharing in Systems Where Half the Servers Are Faulty

Rida Bazzi, Goran Konjevod

Contention-Free MAC protocols for Wireless Sensor Networks

Costas Busch, Malik Magdon-Ismail, Fikret Sivrikaya, Bulent Yener

On Byzantine Agreement over (2,3)-Uniform Hypergraphs

Pandurangan Chandrashekaran, Ravikant D V S, Srinathan Kannan, Srikanth Venkateswaran, Muthuramakrishnan Venkitasubramaniam

On Quorum Systems for Group Resources with Bounded Capacity

Yuh-Jzer Joung

Practical Lock-Free and Wait-Free LL/SC/VL Implementations Using 64-Bit CAS

Maged Michael

A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion

Yitzhak Birk, Liran Liss, Assaf Schuster, Ran Wolff

The Synchronous Condition-Based Consensus Hierarchy

Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal

Virtual Mobile Nodes for Mobile \Adhoc Networks

Shlomi Dolev, Seth Gilbert, Nancy Lynch, Elad Schiller, Alex Shvartsman, Jennifer Welch

On the Respective Power of <>P and <>S to Solve One-Shot Agreement Problems

Roy Friedman, Achour Mostefaoui, Michel Raynal

Brief Announcements

A Formalisation of Message-Complete Publish/Subscribe Systems

Gero Muehl, Andreas Tanner

A formalism for consistency and partial replication

Karthikeyan Bhargavan, Marc Shapiro

Generalized Snapshot Isolation and a Prefix-Consistent Implementation

Sameh Elnikety, Fernando Pedone, Willy Zwaenepoel

Optimal Asynchronous Garbage Collection for Checkpointing Protocols with Rollback-Dependency Trackability

Islene C. Garcia, LuizE. Buzato, Fernando Pedone, Rodrigo Schmidt

Efficient Fully Adaptive Snapshots using Incremental Calculation

Hagit Attiya, Idan Zach

Consensus with Byzantine Failures and Little System Synchrony

Marcos Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg