Preliminary Program of DISC 2004

Note to the speakers

Monday October 4 (morning), 2004

Sixth workshop on Geometric and Topological Methods in Concurrency and Distributed Computing (GETCO)

Monday October 4 (afternoon), 2004

14:00 - 16:00 Special Session: Topological Techniques in Asynchronous Computability (Chair: Hagit Attiya)

• Introduction to the Godel Prize Session (Sergio Rajsbaum, presentation)
• The Topological Structure of Asynchronous Computability (Nir Shavit, presentation)
• Read-Write Reductions (Eli Gafni, presentation)

16:00 - 16:30 Break

16:30 - 17:20 Session: Consensus (Chair: Alex Schvartsman)

• The Synchronous Condition-Based Consensus Hierarchy (Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal). Abstract.
• Synchronous Condition-based Consensus Adapting to Input-vector Legality (Taisuke Izumi, Toshimitsu Masuzawa). Abstract.

17:30 - 18:30 City Hall Reception

Tuesday October 5, 2004

8:30 - 9:15 Invited Talk

Matching Distributed System Models to Reality (David Powell, presentation)

9:15 - 10:05 Session: Solvability (Chair: Carole Delporte)

• Group Solvability (Eli Gafni). Abstract.
• The Notion of Veto Number and the Respective Power of <>P and <>S to Solve One-Shot Agreement Problems (Roy Friedman, Achour Mostefaoui, Michel Raynal). Abstract.

10:05 - 10:30 Break

10:30 - 11:20 Session: Mutual Exclusion (Chair: Achour Moustefaoui)

• The Black-White Bakery Algorithm (Gadi Taubenfeld). Abstract.
• Local-Spin Group Mutual Exclusion Algorithms (Robert Danek, Vassos Hadzilacos). Abstract.

11:20 - 12:15 Session: Quorums and Replication (Chair: Achour Moustefaoui)

• On Quorum Systems for Group Resources with Bounded Capacity (Yuh-Jzer Joung). Abstract.
• Bounded Version Vectors (Jose Bacelar Almeida, Paulo Sergio Almeida, Carlos Baquero). Abstract.
• Brief Announcement: A formalism for consistency and partial replication (Marc Shapiro, Karthik Bhargavan, Yek Chong and Youssef Hamadi). Abstract.

12:15 - 14:00 Lunch

14:00 - 15:40 Session: Shared Memory I (Chair: Maurice Herlihy)

• An Optimistic Approach to Lock-Free FIFO Queues (Edya Ladan-Mozes, Nir Shavit). Abstract.
• A Single-Enqueuer Wait-Free Queue Implementation (Matei David). Abstract.
• Practical Lock-Free and Wait-Free LL/SC/VL Implementations Using 64-Bit CAS (Maged Michael). Abstract.
• Efficient Adaptive Collect using Randomization (Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer, Roger Wattenhofer). Abstract.

15:40 - 16:10 Break

16:10 - 17:10 Session: Shared Memory II (Chair: Philippas Tsigas)

• Nonblocking Concurrent Data Structures with Condition Synchronization (William Scherer, Michael L.Scott). Abstract.
• Dynamic Memory ABP Work-Stealing (Danny Hendler, Yossi Lev, Nir Shavit). Abstract.
• Efficient Fully Adaptive Snapshots using Incremental Calculation (Hagit Attiya, Idan Zach). Abstract.

17:10 - 17:40 Beer Tasting

17:40 - 18:40 Business meeting (open to all)

Wednesday October 6, 2004

8:30 - 9:15 Invited Talk

Transitions in Programming Models - transitions caused by distributed computing - (Luca Cardelli, presentation)

9:15 - 10:05 Session: Self-Stabilization (Chair: Shlomi Dolev)

• Coupling and Self-Stabilization (Laurent Fribourg, Stephane Messika, Claudine Picaronny). Abstract.
• Optimal Randomized Self-stabilizing Mutual Exclusion on Synchronous Rings (Philippe Duchon, Nicolas Hanusse, Sebastien Tixeuil). Abstract.

10:05 - 10:35 Break

10:35 - 11:55 Session: Ad-Hoc Networks (Chair: Paul Attie)

• Virtual Mobile Nodes for Mobile Adhoc Networks (Shlomi Dolev, Seth Gilbert, Nancy Lynch, Elad Schiller, Alex Shvartsman, Jennifer Welch). Abstract.
• Contention-Free MAC protocols for Wireless Sensor Networks (Costas Busch, Malik Magdon-Ismail, Fikret Sivrikaya, Bulent Yener). Abstract.
• Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems (James Aspnes, Faith Fich, Eric Ruppert). Abstract.
• Brief Announcement: A Formalisation of Message-Complete Publish/Subscribe Systems (Gero Muehl, Andreas Tanner). Abstract.

11:55 - 13:30 Lunch

13:30 - 15:10 Session: Networking and Graph Theory I (Chair: Pierre Fraignaud)

• A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion (Yitzhak Birk, Liran Liss, Assaf Schuster, Ran Wolff). Abstract.
• Message-Optimal and Latency-Optimal Termination Detection Algorithms for Arbitrary Topologies (Neeraj Mittal, Sathya Peri, Subbarayan Venkatesan). Abstract.
• Routing with Improved Communication-Space Trade-Off (Ittai Abraham, Cyril Gavoille, Dahlia Malkhi). Abstract.
• Active and Concurrent Topology Maintenance (Xiaozhou Li, Jayadev Misra, Greg Plaxton). Abstract.

15:10 - 15:40 Break

15:40 - 16:55 Session: Networking and Graph Theory II (Chair: Roman Vitenberg)

• Distributed Weighted Matching (Mirjam Wattenhofer, Roger Wattenhofer). Abstract.
• Exploiting Content Localities for Efficient search in P2P Systems (Lei Guo, Song Jiang, Li Xiao, Xiaodong Zhang). Abstract.
• Compact Routing Schemes for Tree-Length Delta Graphs and for k-chordal Graphs (Yon Dourisboure). Abstract.

17:00 - 23:00 Boat trip and Banquet

Thursday October 7, 2004

9:00 - 9:45 Invited Talk

Towards a Theory of Consistency Primitives (Ueli Maurer)

9:45 - 10:35 Session: Computing with Malicious Processes I (Chair: Felix Gaertner)

• Fault-Tolerant Storage in a Dynamic Environment (Uri Nadav, Moni Naor). Abstract.
• Non-Skipping Timestamps for Byzantine Data Storage Systems (Rida Bazzi, Yin Ding). Abstract.

10:35 - 11:00 Break

11:00 - 12:20 Session: Computing with Malicious Processes II (Chair: Paul Vitanyi)

• Efficient Verification for Provably Secure Storage and Secret Sharing in Systems Where Half the Servers Are Faulty (Rida Bazzi, Goran Konjevod). Abstract.
• Optimal Dispersal of Certificate Chains (Ehab Elmallah, Mohamed Gouda, Eunjin Jung). Abstract.
• On Byzantine Agreement over (2,3)-Uniform Hypergraphs (Pandurangan Chandrashekaran, Ravikant D V S, Srinathan Kannan, Srikanth Venkateswaran, Muthuramakrishnan Venkitasubramaniam). Abstract.
• Brief Announcement: Consensus with Byzantine Failures and Little System Synchrony (Marcos Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg). Abstract.

Thursday October 7 (afternoon) and Friday Oct 8, 2004

Workshop on Secure Multi-party Protocols - SMP 2004