PROGRAM [pdf]

 

Sunday, September 23

 

20:00 22:00 Welcoming Reception (sponsored by CYTA)

 

[A registration desk will operate from 18:00 to 22:00]

 

Monday, September 24

 

8:00 8:50 Registration

 

8:55 Welcome address

 

9:00 David Peleg: Joint DISC-DYNAMO Invited talk (supported by Cost Action 295 DYNAMO)

"Time-Efficient Broadcasting in Radio Networks"

 

10:00 Coffee break (supported by Microsoft)

 

10:30 - 12:35 Session 1 : Graph algorithms

 

10:30 A. Czygrinow, M. Hanckowiak:

"Distributed approximations for packing in unit-disk graphs"

 

10:55 Amos Korman and David Peleg:

"Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes"

 

11:20 Bilel Derbel, Cyril Gavoille and David Peleg:

"Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time."

 

11:45 Beat Gfeller, Nicola Santoro, Peter Widmayer :

"A Distributed Algorithm for All Best Swap Edges of a Minimum Diameter Spanning Tree"

 

12:10 Mordechai Shalom, Prudence W.H. Wong, Shmuel Zaks:

"Optimal on-line colorings for minimizing the number of ADMs in optical networks"

 

12:40 - 14:00 Lunch

 

14:00 - 15:40 Session 2: Distributed data

 

14:00 Amitanand Aiyer, Lorenzo Alvisi, and Rida Bazzi:

"Bounded Wait-Free Implementation of Optimally resilient Byzantine Storage

without (Unproven) Cryptographic assumptions"

 

14:25 Gregory Chockler, Rachid Guerraoui, Idit Keidar:

"Amnesic Distributed Storage"

 

14:50 Shuang Liang, Xiaodong Zhang, Song Jiang, Ke Chen:

"Cost-Aware Caching Algorithms for Distributed Storage Servers"

 

15:15 Thomas Locher, Remo Meier, Stefan Schmid, Roger Wattenhofer:

"Push-to-Pull Peer-to-Peer Live Streaming"

 

15:40 - 16:00 Coffee break (supported by Microsoft)

 

16:00 - 18:05 Session 3: Consensus and failure detectors

 

16:00 Dana Angluin, James Aspnes, David Eisenstat:

"Fast Robust Approximate Majority"

 

16:25 Seth Gilbert, Rachid Guerraoui, Dariusz Kowalski:

"On the Message Complexity of Indulgent Consensus"

 

16:50 Carole Delporte-Gallet, Hugues Fauconnier, Felix Freiling, Lucia Draque Penso, Andreas Tielmann:

"From Crash-Stop to Permanent Omission: Automatic Transformation and Weakest Failure Detectors"

17:15 Wei Chen, Jialin Zhang, Yu Chen, Xuezheng Liu:

"Weakening Failure Detectors for k-Set Agreement via the Partition"

 

17:40 Piotr Zielinski:

"Automatic classification of eventual failure detectors"

 

18:30 Business meeting

 

20:00 Dijkstra Prize presentation

 

Tuesday, September 25

 

9:00 Michel Raynal: Invited talk

"A Subjective Visit to Selected Topics in Distributed Computing"

 

10:00 Coffee break

 

10:30 - 12:35 Session 4: Communication algorithms and mobile robots

 

10:30 Leszek Gasieniec, Erez Kantor, Dariusz R. Kowalski, David Peleg, Chang Su:

"Energy and Time Efficient Broadcasting in Known Topology Radio Networks"

 

10:55 Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Calvin Newport:

"Gossiping in a Multi-Channel Radio Network"

 

11:20 Roberto Baldoni, Kleoni Ioannidou, Alessia Milani:

"Mobility versus the Cost of Geocasting in Mobile Ad-Hoc Networks"

 

11:45 Jeremie Chalopin, Shantanu Das, Nicola Santoro:

"Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links"

 

12:10 Taisuke izumi, Yoshiaki Katayama, Nobuhiro Inuzuka, Koichi Wada:

"Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result"

 

12:40 - 14:00 Lunch (supported by the University of Cyprus)

 

14:00 - 15:03 Brief Announcements Session

 

14:00 Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Alfredo Navarra:

"On the Complexity of Distributed Greedy Coloring"

14:07 Tal Mizrahi and Yoram Moses:

"Long Live Continuous Consensus"

 

14:14 Virendra J. Marathe, Michael F. Spear, Michael L. Scott:

"Transaction Safe Nonblocking Data Structures"

 

14:21 Colette Johnen and Lisa Higham:

"Fault-tolerant Implementations of Atomic Registers by Weaker Registers in Networks Models"

 

14:28 Arpita Patra, Ashish Choudhary, Kannan Srinathan, Chandrasekharan Pandu Rangan:

"Perfectly Reliable and Secure Communication in Directed Networks Tolerating Mixed Adversary"

 

14:35 Alysson Neves Bessani, Miguel Correia, Henrique Moniz, Nuno Ferreira Neves, Paulo Verissimo:

"When 3f+1 is not Enough: Tradeoffs for Decentralized Asynchronous Byzantine Consensus"

 

14:42 Rodrigo Schmidt, Fernando Pedone:

"A Formal Analysis of the Deferred Update Technique"

 

14:49 Michael Okun:

"On Impersonation vs. Asynchrony"

 

14:56 Damon Mosk-Aoyama, Tim Roughgarden, Devavrat Shah:

"Fully Distributed Algorithms for Convex Optimization Problems"

 

15:30 20:00 Excursion (partially supported by CTO): Visit the ancient city-kingdom Kourion, traditional Cypriot village Anogyra and Olive oil Park and museum Oleastro

 

20:00 Banquet and Awards

 

Wednesday, September 26

 

9:00 Burkhard Monien: Invited talk

"Routing and Scheduling with Incomplete Information"

 

10:00 Coffee break

 

10:30 - 12:35 Session 5: Networks

 

10:30 Shay Kutten and Toshimitsu Masuzawa:

"Output stability versus time till output"

 

10:55 Janna Burman and Shay Kutten:

"Time Optimal Asynchronous Self-Stabilizing Spanning Tree"

 

11:20 Joffroy Beauquier, Julien Clement, Stephane Messika, Laurent Rosaz, Brigitte Rozoy:

"Self-Stabilizing Counting in Mobile Sensor Networks"

 

11:45 Edward Bortnikov, Israel Cidon, Idit Keidar:

"Scalable Load-Distance Balancing"

 

12:10 Simon Fischer, Lars Olbrich, Berthold Vöcking:

"Approximating Wardrop Equilibria with Finitely Many Agents"

 

12:40 - 14:00 Lunch

 

14:00 - 15:40 Session 6 : Asynchronous processes

 

14:00 Faith Ellen, Panagiota Fatourou, Eric Ruppert:

"The Space Complexity of Unbounded Timestamps"

 

14:25 Gadi Taubenfeld:

"Efficient Transformations of Obstruction-free Algorithms into Non-blocking Algorithms"

 

14:50 Matthew Lang and Paolo A.G. Sivilotti:

"A Distributed Maximal Scheduler for Strong Fairness"

 

15:15 Vinit A. Ogale and Vijay K. Garg:

"Detecting Temporal Logic Predicates on Distributed Computations"

 

15:40 - 16:00 Coffee break

 

16:00 - 17:40 Session 7: Fault tolerance

 

16:00 Baruch Awerbuch and Christian Scheideler:

"A Denial-of-Service Resistant DHT"

 

16:25 Danny Dolev and Ezra Hoch:

"On Self-stabilizing Synchronous Actions Despite Byzantine Attacks"

 

16:50 Michael G. Merideth and Michael K. Reiter:

"Probabilistic Opaque Quorum Systems"

 

17:15 Dariusz R. Kowalski, Michal Strojnowski:

"On the communication surplus incurred by faulty processors"

 

END OF DISC 2007