Technical Program

DISC 2006 - PROGRAM

Stockholm, Sweden, September 18 - 20, 2006


Complement to the Proceeding

SUNDAY, 17 SEPTEMBER 2006
9:00 - 16:00 DYNAMO WORKSHOP
16:30 -18.00 DYNAMO MC MEETING

Print out the program

MONDAY, 18 SEPTEMBER 2006

    08:50 - 09.00
    		 DISC Welcome
    09:00 - 10:00
    		 DISC Invited Lecture Invited Talk I, Chair: Shlomi Dolev
    • Provable Unbreakable Hyper-Encryption Using Distributed Systems,
      Michael Rabin
    10:00 - 10:15
    		Coffee Break
    10:15 - 11.15

    DISC Invited Lecture Invited Talk II, Chair: Michel Raynal

    • Time, Clocks, and the Ordering of My Ideas about Distributed Systems,
      Leslie Lamport
    11:15 - 11:30
    		 Break
    11:30 - 12:30

    DISC Invited Lecture Invited Talk III, Chair: Alex Shvartsman

    • My Early Days in Distributed Computing Theory: 1979-1982,
      Nancy Lynch
    12:30 - 14:00
    		Lunch (Provided by DISC)
    14:00 - 15:40

    Session I, Chair: Maurice Herlihy

    14:00 - 14:25
    • Exploring Gafni's reduction land: from Ωk to wait-free adaptive (2p - [ p/k]) renaming via k-set agreement,
      Achour Mostefaoui, Michel Raynal, Corentin Travers
    14:25 - 14:50
    • Renaming in Message Passing Systems with Byzantine Failures,
      Michael Okun, Amnon Barak
    14:50 - 15:15
    • Built-in Coloring for Highly-Concurrent Doubly-Linked Lists,
      Hagit Attiya, Eshcar Hillel
    15:15 - 15:40
    • Fault-tolerant and Self-stabilizing Mobile Robots Gathering,
      Xavier Défago, Maria Gradinariu, Stéphane Messika, Philippe Raipin-Parvédy
    15:40 - 15:55 Coffee Break
    15:55 - 17:35 Session II, Chair: Marina Papatriantafiou
    15:55 - 16:20
    • Fast Computation by Population Protocols With a Leader,
      Dana Angluin, James Aspnes, David Eisenstat
    15:55 - 16:20
    • On Self-Stabilizing Search Trees,
      Doina Bein, Ajoy K. Datta, Lawrence L. Larmore
    16:45 - 17:10
    • Efficient Dynamic Aggregation,
      Yitzhak Birk, Idit Keidar, Liran Liss, Assaf Schuster
    17:10 - 17:35
    • Groupings and Pairings in Anonymous Networks,
      Jérémie Chalopin, Shantanu Das, Nicola Santoro
    17:35 - 17:50 Break
    17:50 - 18:26 Brief Announcements Session I, Chair: Sébastien Tixeuil
    17:50 - 17:56
    • Brief Announcement:
      Abortable Shared Objects,
      Marcos K. Aguilera, Svend Frolund, Vassos Hadzilacos, Stephanie Lorraine Horn, Sam Toueg
    17:56 - 18:02
    • Brief Announcement:
      Fault-tolerant SemiFast Implementations of Atomic Read/Write Registers,
      Chryssis Georgiou, Nicolas C. Nicolaou, Alexander A. Shvartsman
    18:02 - 18:08
    • Brief Announcement:
      Convergence Analysis of Sclable Gossip Protocols,
      Stacy Patterson, Bassam Bamieh, Amr El Abbadi
    18:08 - 18:14
    • Brief Announcement:
      Computing Automatically the Stabilization Time Against the Best and the Worst Schedules,
      Joffroy Beauquier, Colette Johnen, Stéphane Messsika
    18:14 - 18:20
    • Brief Announcement:
      Multislicing: Many Slices are Better than One,
      Vinit A. Ogale, Vijay K. Garg
    18:20 - 18:26
    • Brief Announcement:
      on Augmented Graph Navigability,
      Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker
    18:30 - 20:00 DISC Plenary Assembly / Rump Session

[top]

THUESDAY , 19 SEPTEMBER 2006

    08:30 - 10:10

    Session III, Chair: Nancy Lynch
    08:30 - 08:55
    • A New Proof of the GHS Minimum-spanning Tree Algorithm,
      Yoram Moses, Benny Shimony
    08:55 - 09:20
    • A Knowledge-Based Analysis of Global Function Computation,
      Joseph Y. Halpren, Sabina Petride
    09:20 - 09:45
    • Checking a Multithreaded Algorithm with +CAL,
      Leslie Lamport
    09:45 - 10:10
    • Capturing Register and Control Dependence in Memory Consistency Models with Applications to the Itanium Architecture
      Lisa Higham, LillAnne Jackson, Jalal Kawash
    10:10 - 10:25
    		 Coffee Break
    10:25 - 12:05

    Session IV, Chair: Gadi Taubenfeld
    10:25 - 10:50
    • Conflict Detection and Validation Strategies for Software Transactional Memory,
      Michael F. Spear, Virendra J. Marathe, William N. Scherer III, Michael L. Scott
    10:50 - 11:15
    • Transactional Locking II,
      Dave Dice, Ori Shalev, Nir Shavit
    11:15 - 11:40
    • Less is More: Consensus Gaps Between Restricted and Unrestricted Objects,
      Yehuda Afek, Eran Shalom
    11:40 - 12:05
    • One-Step Consensus Solvability,
      Taisuke Izumi, Toshimitsu Masuzawa
    12:05 - 13:30
    		 Lunch (Provided by DISC)
    13:30 - 15:10

    Session V, Chair: André Schiper
    13:30 - 13:55
    • Time-Bounded Task-PIOAs: A Framework for Analyzing Security Protocols (Invited Paper)
      Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala
    13:55 - 14:20
    • On Consistency of Encrypted Files,
      Alina Oprea, Michael K. Reiter
    14:20 - 14:45
    • Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data,
      Michael B. Greenwald, Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, Alan Schmitt
    14:45 - 15:10
    • A Lazy Snapshot Algorithm with Eager Validation,
      Torvald Riegel, Pascal Felber, Christof Fetzer
    15:10 - 15:25
    		Break
    15:25 - 16:07

    Brief Announcements Session II, Chair: Dariusz Kowalski
    15:25 - 15:31
    • Brief Announcement:
      Decoupled Quorum-based Byzantine-Resilient Coordination in Open Distributed Systems,
      Alysson Neves Bassani, Miguel Correia, Joni da Silva Fraga, Lau Cheuk Lung
    15:31 - 15:37
    • Brief Announcement:
      Optimistic Algorithms for Partial Database Replication,
      Nicolas Schiper, Rodrigo Schmidt, Fernando Pedone
    15:37 - 15:43
    • Brief Announcement:
      Performance Analysis of Cyclon an Inexpensive Membership Management for Unstructured P2P Overlays,
      Francqis Bonnet, Frédéric Tronel, Spyros Voulgaris
    15:43 - 15:49
    • Brief Announcement:
      Decentralized, Conectivity-Preserving, and Cost-Effective Structured Overlay Maintenance,
      Yu Chen and Wei Chen
    15:49 - 15:55
    • Brief Announcement:
      Monitoring of Distributed Linear Computations,
      Anton Esin, Rostislav Yavorskiy, Nikolay Zemtsov
    15:55 - 16:01
    • Brief Announcement:
      Communications-optimal Implemaentation of Failure Detector Class,
      Mikel Larrea, Alberto Lafuente and Joachim Wieland
    16:01 - 16:07
    • Brief Announcement:
      Syncronous Distributed algorithms for Node Discovery and Configuration in Multi-channel Cognitive Radio Networks,
      Srinivasan Krishnamurthy, R. Chandrasekaran, Neeraj Mittal and S. Venkatesan
    16:15
    		20th Anniversary Celebration Panel,
    Eli Gafni, Michel Raynal, Nicola Santoro, Jan van Leeuwen, Shmuel Zaks
    18:00 - 23:15

    Conference Banquet

    DISC Boat Tour with Conference Dinner

    The Boat leaves from Allmänna Gränd ( 10 minutes walk from Hasselbacken) at 18.00 and arrives at Vaxholms Kastell 19.00.

    Three course dinner will be served at Vaxholms Kastell in the Pansarbatteriet room.

    The boat takes you back at 22.00 and stops at Allmänna Gränd 23.00, for those who are staying at Hasselbacken Hotel and then the boat continues to Slussen for you who are staying at other hotels.


WEDNESDAY , 20 SEPTEMBER 2006
    08:30 - 10:10
    		Session VI, Chair: Michel Raynal
    08:30 - 08:55
    • Bounded Wait-Free f-resilient Atomic Byzantine Data Storage Systems for an Unbounded Number of Clients
      Rida A. Bazzi, Yin Ding
    8:55 - 09:20
    • Time and Communication Efficient Consensus for Crash Failures,
      Bogdan S. Chlebus, Dariusz R. Kowalski
    09:20 - 09:45
    • Minimizing the Number of ADMs in a General Topology Optical Network,
      Michele Flammini, Mordechai Shalom, Shmuel Zaks
    09:46 - 10:10
    • Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes,
      Arthur Brady, Lenore Cowen
    10:10 - 10:25
    		 Coffee Break
    10:25 - 12:05
    		 Session VII, Chair: Lenka Carr-Motyckova
    10:25 - 10:50
    • A Fast Distributed Approximation Algorithm for Minimum Spanning Trees,
      Maleq Khan, Gopal Pandurangan
    10:50 - 11:15
    • On Randomized Broadcasting in Power Law Networks,
      Robert Elsässer
    11:15 - 11:40
    • Distributed Approximation Algorithms in Unit-disk Graphs,
      A. Czygrinow, M. Hancoviak
    11:40 - 12:05
    • The Weakest Failure Detectors to Boost Obstruction-Freedom,
      Rachid Guerraoui, Michal Kapalka, Petr Kouznetsov
    12:05 - 13:30
    		Lunch (Provided by DISC)
    13:30 - 15:10
    		 Session IIX, Chair: Alex Shvartsman
    13:30 - 13:55
    • Fully Adaptive Algorithms for Long-Lived Renaming,
      Alex Brodsky, Faith Ellen, Philipp Woelfel
    13:55 - 14:20
    • Bounded-Wait Combining: Constructing Robust and High-Throughput Shared Objects,
      Hendler, Shay Kutten
    14:20 - 14:45
    • Byzantine and Multi-writer K-quorums,
      Amitanand S. Aiyer, Lorenzo Alvisi, Rida A. Bazzi
    14:45 - 15:10
    • Subconsensus Tasks: Renaming is Weaker than Set Agreement,
      Eli Gafni, Sergio Rajsbaum, Maurice Herlihy
    15:10 - 15:25
    		 Coffee Break
    15:25 - 17:05
    		 Session IX, Chair: Shlomi Dolev
    15:25 - 15:50
    • Robust Network Supercomputing with Malicious Processes,
      Kishori M. Konwar, Sanguthevar Rajasekaran, Alexander A. Shvartsman
    15:50 - 16:15
    • Distributed Resource Allocation in Stream Processing,
      Cathy H. Xia, James A. Broberg, Zhen Liu, Li Zhang
    16:15 - 16:40
    • Low-latency Atomic Broadcast in the Presence of Contention,
      Piotr Zielinski
    16:40 - 17:05
    • Oblivious Gradient Clock Synchronization,
      Thomas Locher, Roger Wattenhofer

    		End of DISC 2006

[top]