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"