DISC 2011
the 25th International Symposium on DIStributed Computing - September 20-22

Conference Program [PDF]

LOCATION: Dipartimento di Informatica e Sistemistica - Via Ariosto 25
9:00-13:00 AlMoDEP workshop room:Aula Magna**
9:00-17:00 Teranet workshop room: B2**
14:00-17:30 TADDS workshop room:Aula Magna**
17:45-18:45 60th birthday celebration of Nicola Santoro

Pierre Fraigniaud,
David Peleg,
Giuseppe Prencipe,
Alex Shvartsman (MC),
Peter Widmayer,
Shmuel Zaks
room:Aula Magna**
18:45-21:30 welcome reception Court**
LOCATION: School of Engineering - Via Eudossiana 18
8.30 - 10.00 Session 1a: Invited Lecture and Best Student Paper
Session Chair: David Peleg
room:Aula del Chiostro*
8.30 - 8.35 Opening Remarks
8.35 - 9.35 Invited Lecture: Andrzej Pelc
"Deterministic Rendezvous in Networks: Survey of Models and Results"
9:35-10:00 Yehuda Afek, Michael Hakimi and Adam Morrison
"Fast and Scalable Rendezvousing"
10.00-10.30 Break
10:20-12:00 Session 1b: Distributed Graph Algorithms
Session Chair: Yuval Emek
room:Aula del Chiostro*
10:20- 10:45 Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler and Fabian Kuhn
"Beeping a Maximal Independent Set"
10:45-11:10 Johannes Schneider and Roger Wattenhofer
"Trading Bit, Message and Time Complexity of Distributed Algorithms"
11:10-11:35 Leonid Barenboim and Michael Elkin
"Combinatorial Algorithms for Distributed Graph Coloring"
11:35- 12:00 Taisuke Izumi, Maria Gradinariu Potop-Butucaru and Mathieu Valero
"Physical Expander in Virtual Tree Overlay"
12:00-13:30 Lunch
13:30-14:45 Session 1c: Shared Memory
Session Chair: Faith Ellen
room:Aula del Chiostro*
13:30-13:55 Dan Alistarh and James Aspnes.
"Sub-Logarithmic Test-and-Set Against a Weak Adversary"
13:55-14:20 Gadi Taubenfeld
"Tight Space Bounds for l-exclusion"
14:20-14:45 Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich and Idit Keidar
"SMV: Selective Multi-Versioning STM"
14:45-15:20 Session 1d: Brief Announcements I
Session Chair: Faith Ellen

Leslie Lamport
"Leaderless Byzantine Paxos"

Keith Marzullo, Hein Meling and Alessandro Mei
"When You Don’t Trust Clients: Byzantine Proposer Fast Paxos"

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni and Petr Kuznetsov
"On the Meaning of Solving a Task with a Failure Dectector"

Evgenia Christoforou, Antonio Fernandez Anta, Chryssis Georgiou and Miguel A. Mosteiro
"Algorithmic Mechanisms for Internet-based Computing under Unreliable Communication"
room:Aula del Chiostro*
15:20-15:40 Break
15:40-16:55 Session 1e: Fault-Tolerance and Security
Session Chair: Maria Potop-Butucaru
room:Aula del Chiostro*
15:40-16:05 Swan Dubois, Toshimitsu Masuzawa and Sebastien Tixeuil
"Maximum Metric Spanning Tree made Byzantine Tolerant"
16:05-16:30 Chryssis Georgiou and Dariusz Kowalski
"Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts"
15:30-16:55 Elette Boyle, Shafi Goldwasser and Yael Tauman Kalai
"Leakage-Resilient Coin Tossing"
16:55-17:30 Session 1f: Brief Announcements II
Session Chair: Maria Potop-Butucaru

Shay Kutten, Ron Lavi and Amitabh Trehan
"Composition Games for Distributed Systems: the EU Grant games"

Edyta Szymanska, Krzysztof Krzywdzinski, Andrzej Czygrinow, Michal Hanckowiak and Wojciech Wawrzyniak
"Distributed Approximation Algorithm for the Semi-Matching Problem"

Martin Farach-Colton, Antonio Fernandez Anta, Alessia Milani, Miguel A. Mosteiro and Shmuel Zaks
"Opportunistic Information Dissemination in  Mobile Ad-hoc Networks: Adaptiveness vs. Obliviousness and  Randomization vs. Determinism"

Siddhartha Sen, Sunghwan Ihm, Kay Ousterhout and Michael Freedman
"Bridging the Theory-Practice Gap in Multi-Commodity Flow Routing"
room:Aula del Chiostro*
17:45-18:15 Dijkstra Prize room:Aula del Chiostro*
18:15-20:00 Business Meeting room:Aula del Chiostro*
LOCATION: School of Engineering - Via Eudossiana 18
8:30-10:00 Session 2a: Invited Lecture; Paxos Plus
Session Chair: Roberto Baldoni
room:Aula del Chiostro*
8:30-8:35 Opening Remarks
8:35-9:35 Invited Lecture:  Dahlia Malkhi
"Going Beyond Paxos"
9:35-10:00 Leslie Lamport
"Byzantizing Paxos by Refinement"
10:00- 10:20 Break
10:20-12:00 Session 2b: Wireless
Session Chair: David Ilcinkas
room:Aula del Chiostro*
10:20-10:45 Antonio Fernandez Anta, Miguel A. Mosteiro and Jorge R. Muñoz
"Unbounded Contention Resolution in  Multiple-Access Channels"
10:45-11:10 Leonid Barenboim, Shlomi Dolev and Rafail Ostrovsky
"Deterministic and Energy-Optimal Wireless Synchronization"
11:10-11:35 Shlomi Dolev, Seth Gilbert, Majid Khabbazian and Calvin Newport
"Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast"
11:35-12:00 Mohsen Ghaffari, Nancy Lynch and Srikanth Sastry
"Leader Election Using Loneliness Detection"
12:00-13:30 Lunch
13:30-14:45 Session 2c: Network algorithms I
Session Chair: Anne-Marie Kermarrec
room:Aula del Chiostro*
13:30-13:55 Srikanta Tirthapura and David Woodruff
"Optimal Random Sampling from Distributed Streams Revisited"
13:55-14:20 Andrea Clementi and Riccardo Silvestri
"Parsimonious Flooding in Geometric Random-Walks"
14:20-14:45 Yvonne Anne Pignolet, Stefan Schmid and Gilles Tredan.
"Misleading Stars: What Cannot Be Measured in the Internet?"
14:45-15:10 Session 2d: Brief Announcements III
Session Chair: Anne-Marie Kermarrec

Meg Walraed-Sullivan, Radhika Niranjan Mysore, Keith Marzullo and Amin Vahdat
"A Randomized Algorithm for Label Assignment in Dynamic Networks"

Mikel Larrea and Michel Raynal
"Delta Omega: Specifying an Eventual Leader Service for Dynamic Systems"

Taisuke Izumi, Zohir Bouzid, Sebastien Tixeuil and Koichi Wada
"The BG-simulation for Byzantine Mobile Robots"
room:Aula del Chiostro*
15:30-19.30 Excursion: Etruscan Necropolis "La Banditaccia" room:Aula del Chiostro*
19:30-22:30 DISC 2011 Banquet, Cerveteri
LOCATION: School of Engineering - Via Eudossiana 18
IMPORTANT NOTE: Transform WTTM Workshop is located in Dipartimento di Informatica e Sistemistica - Via Ariosto 25
8:30-10:00 Session 3a: Invited Lecture & Best Paper; Aspects of Locality
Session Chair: Maurice Herlihy
room:Aula del Chiostro*
8:30-8:35 Opening remarks
8:35-9:35 Invited Lecture:  Peter Widmayer.
"Polygon Reconstruction with Little Information: An Example for the Power of Simple Micro-robots"
9:35-10:00 Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers
" Locality and Checkability in Wait-free Computing"
10:00-10:20 Break
10:20-12:00 Session 3b: Consensus
Session Chair: Luisa Gargano
room:Aula del Chiostro*
10:20-10:45 Allison Lewko
"The Contest Between Simplicity and Efficiency in Asynchronous Byzantine Agreement"
10:45-11:10 James Aspnes
"Randomized Consensus in Expected O(n2) Total Work using Single-Writer Registers"
11:10-11:35 Hagit Attiya, Fatemeh Borran, Martin Hutle, Zarko Milosevic and Andre Schiper
"Structured Derivation of Semi-Synchronous Algorithms"
11:35-12:00 Piyush Bansal, Prasant Gopal, Anuj Gupta, Kannan Srinathan and Pranav Kumar Vasishta
"Byzantine Agreement using Partial Authentication"
12:00-13:30 Lunch
13:30-15:10 Session 3c: Network Algorithms II
Session Chair: Luisa Gargano
room:Aula del Chiostro*
13:30-13:55 Ittai Abraham and Cyril Gavoille.
"On Approximate Distance Labels and Routing Schemes with Affine Stretch"
13:55-14:20 Fabian Kuhn and Rotem Oshman
"The Complexity of Data Aggregation in Directed Networks"
14:20- 14:45 Jérémie Chalopin, Shantanu Das, Arnaud Labourel and Euripides Markou
"Black Hole Search with Finite Automata Scattered in a Synchronous Torus"
14:45-15:10 Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski and Russell Martin
"Synchronous Rendezvous for Location-aware Agents"
15:10-15:30 Break
15:30-16:50 Session 3d: Concurrency
Session Chair: Adrian Kosowski
15:30-15:55 Li Lu and Michael L. Scott
"Toward a Formal Semantic Framework for Deterministic Parallel Programming"
15:55-16:20 Dmitri Perelman, Dmitry Basin, Idit Keidar, Ofer Kiselov and Rui Fan
"CAFÉ: Scalable Task Pools with Adjustable Fairness and Contention"
16:20-16:45 Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial and Benny Sudakov
"Oblivious Collaboration"
16:45-16:50 DISC symposium closing
17:00-19.00 Transform WTTM workshop room:B2**
17:00-19.10 Tutorial: Knowledge Strikes Again - Yoram Moses room:Aula del Chiostro*
17:00-18:00 Session 1
18:00-18:10 Break
18:10-19:10 Session 2
09:00-11.40 Tutorial: From Reliable to Secure Distributed Programming - Christian Cachin room: A7**
09:00-10:30 Session 1
10:30-10:40 Break
10:40-11:40 Session 2
9:00-17:00 Transform WTTM workshop room:B2**
9:00-17:00 DISC's SON workshop room:Aula Magna**

*located in School of Engineering - Via Eudossiana 18
**located in Dipartimento di Informatica e Sistemistica - Via Ariosto 25

sponsored by:
logo sapienza         logo microsoft research        logo cini consorzio interuniversitario per l'informatica