A PDF version of the program is available. Tuesday September 22nd8:00-8:30 Registration8:30-10:30 Workshops (WTTM and WRSWN) and Cloud Tutorial Session 1 10:30-11:00 Coffee break 11:00-13:00 Workshops (WTTM, BFTW3, and WRSWN) and Cloud Tutorial Session 2 13:00-15:00 Lunch (on your own) 15:00-17:00 Workshops (WTTM, BFTW3, and WRSWN) Session 3 17:00-18:00 Coffee break and registration 18:00-20:00 Birthday Celebration Session 20:00-22:00 Reception Dinner Wednesday September 23rd8:00-8:30 Registration8:30 - 10:32 Session 1A: Transactional Memory Chair: Idit Keidar 8:30 Opening Remarks 8:35 Keynote Lecture: Nir Shavit Title: Software Transactional Memory: Where do we come from? What are we? Where are we going? 9:35 Interrupting Snapshots and the Java Size() Method Yehuda Afek, Nir Shavit and Moran Tzafrir 10:00 Elastic Transactions Pascal Felber, Vincent Gramoli and Rachid Guerraoui 10:25 Brief Announcement: Transactional Scheduling for Read-Dominated Workloads Hagit Attiya and Alessia Milani 10:32-10:55 Coffee break 10:55-12:50 Session 1B: Shared Memory Chair: Eric Ruppert 10:55 Tight group renaming on groups of size g is equivalent to g-consensus Yehuda Afek, Eli Gafni and Opher Lieber 11:20 The RedBlue algorithm: An Adaptive Universal Construction Panagiota Fatourou and Nikolaos Kallimanis 11:45 Help when needed, but no more: Efficient Read/Write Partial Snapshot Damien Imbs and Michel Raynal 12:10 Contention-sensitive Data Structures and Algorithms Gadi Taubenfeld 12:35 Brief Announcement: Acceleration by Contention for Shared Memory Mutual Exclusion Algorithms Michiko Inoue, Tsuyoshi Suzuki and Hideo Fujiwara 12:42 Brief Announcement: Incremental Component-Based Specification, Verification, and Performance Evaluation of Distributed Reset Ananda Basu, Borzoo Bonakdarpour, Marius Bozga and Joseph Sifakis 12:50-14:10 Lunch (provided by DISC) 14:10-16:05 Session 1C: Distributed and Local Graph Algorithms Chair: Fabian Kuhn 14:10 Local Computation of Nearly Additive Spanners Bilel Derbel, Cyril Gavoille, David Peleg and Laurent Viennot 14:35 A local 2-approximation algorithm for the vertex cover problem Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela and Jara Uitto 15:00 Distributed Discovery of Large Near-Cliques Zvika Brakerski and Boaz Patt-Shamir 15:25 Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality Christos Koufogiannakis and Neal Young 15:50 Brief Announcement: Decidable Graph Languages by Mediated Population Protocols Ioannis Chatzigiannakis, Othon Michail and Paul Spirakis 15:57 Brief Announcement: Towards Secured Distributed Polling in Social Networks Rachid Guerraoui, Kevin Huguenin, Anne-Marie Kermarrec and Maxime Monod 16:05-16:25 Coffee break 16:25-17:55 Session 1D: Modeling Issues Chair: Pascal Felber 16:25 What Can be Observed Locally? Round-based Models for Quantum Distributed Computing Cyril Gavoille, Adrian Kosowski and Marcin Markiewicz 16:50 At-Most-Once Semantics in Asynchronous Shared Memory Sotirios Kentros, Aggelos Kiayias, Nicolas Nicolaou and Alexander Shvartsman 17:15 Nonblocking Algorithms and Backward Simulation Simon Doherty and Mark Moir 17:40 Brief Announcement: Efficient Model Checking of Fault-tolerant Distributed Protocols Using Symmetry Reduction Peter Bokor, Marco Serafini, Neeraj Suri and Helmut Veith 17:47 Brief Announcement: Dynamic FTSS in Asynchronous Systems: the Case of Unison Swan Dubois, Maria Gradinariu Potop-Butucaru and Sébastien Tixeuil 18:10-19:30 Business meeting Thursday September 24th8:30-10:02 Session 2A: Game TheoryChair: Idit Keidar 8:30 Keynote Lecture: Lorenzo Alvisi Title: BFT we can believe in 9:30 Dynamics in Network Interaction Games Martin Hoefer and Siddharth Suri 9:55 Brief Announcement: Cloud Computing Games: Pricing Services of Large Data Centers Ashraf Al Daoud, Sachin Agarwal and Tansu Alpcan 10:02-10:25 Coffee break 10:25-13:00 Session 2B: Award Nominees Chair: Yehuda Afek 10:25 Introduction 10:30 The Disagreement Power of an Adversary Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui and Andreas Tielmann 11:00 New Bounds for the Controller Problem Yuval Emek and Amos Korman 11:30 On Set Consensus Numbers Eli Gafni and Petr Kuznetsov 12:00 The Abstract MAC Layer Fabian Kuhn, Nancy Lynch and Calvin Newport 12:30 Randomization Can Be a Healer: Consensus with Dynamic Omission Failures Henrique Moniz, Nuno Neves, Miguel Correia and Paulo Verissimo 13:00-14:20 Lunch (provided by DISC) 14:20-15:57 Session 2C: Failure Detectors Chair: Carole Delporte-Gallet 14:20 On the Existence of Weakest Failure Detectors for Mutual Exclusion and k-Exclusion Vibhor Bhatt and Prasad Jayanti 14:45 Crash Quiescent Failure Detection Srikanth Sastry, Scott Pike and Jennifer Welch 15:10 The Price of Anonymity: Optimal Consensus despite Asynchrony, Crash and Anonymity François Bonnet and Michel Raynal 15:35 Brief Announcement: On Implementing Omega Efficiently in the Crash-Recovery Model Mikel Larrea and Cristian Martín 15:42 Brief Announcement: The minimum failure detector for non-local tasks in message-passing systems Carole Delporte-Gallet, Hugues Fauconnier and Sam Toueg 15:50 Brief Announcement: Weak synchrony models and failure detectors for message passing (k-) set agreement Martin Biely, Peter Robinson and Ulrich Schmid 15:57-16:15 Coffee break 16:45-19:30 Excursion - Tour of Elche 20:00-23:00 Banquet dinner and award ceremony Friday September 25th9:00-10:07 Session 3A: From Theory to PracticeChair: Idit Keidar 9:00 Keynote Lecture: Willy Zwaenepoel Title: P2P, DSM, and Other Products of the Complexity Factory 10:00 Brief Announcement: Zab: A practical totally ordered broadcast protocol Benjamin Reed and Flavio Junqueira 10:07-10:25 Coffee break 10:25-12:30 Session 3B: Graph Algorithms and Routing Chair: Antonio Fernández 10:25 Compact Multicast Routing Ittai Abraham, Dahlia Malkhi and David Ratajczak 10:50 Compact Routing in Power-Law Graphs Wei Chen, Christian Sommer, Shang-Hua Teng and Yajun Wang 11:15 Virtual Ring Routing Trends Dahlia Malkhi, Sid Sen, Kunal Talwar, Renato Werneck and Udi Wieder 11:40 A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property Lélia Blin, Maria Potop-Butucaru, Stéphane Rovedakis and Sébastien Tixeuil 12:05 Euler Tour Lock-in Problem in the Rotor-Router Model Evangelos Bampas, Leszek Gasieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing and Adrian Kosowski 12:30-13:50 Lunch (provided by DISC) 13:50-15:12 Session 3C: Consensus and Byzantine Agreement Chair: Christian Cachin 13:50 Optimum simultaneous consensus for general omissions is equivalent to an NP Oracle Yoram Moses 14:15 On the Number of Synchronous Rounds Required for Byzantine Agreement Matthias Fitzi and Jesper Nielsen 14:40 Fast, scalable Byzantine agreement in the full information model with a nonadaptive adversary Valerie King and Jared Saia 15:05 Brief Announcement: A Leader-free Byzantine Consensus Algorithm Fatemeh Borran and André Schiper 15:12-15:30 Coffee break 15:30-17:00 Session 3D: Radio Networks Chair: Seth Gilbert 15:30 Efficient k-shot Broadcasting in Radio Networks Erez Kantor and David Peleg 15:55 Keeping Mobile Robot Swarms Connected Alejandro Cornejo, Ruy Ley-Wild, Fabian Kuhn and Nancy Lynch 16:20 Consensus and mutual exclusion in a multiple access channel Jurek Czyzowicz, Leszek Gasieniec, Dariusz Kowalski and Andrzej Pelc 16:45 Brief Announcement: Efficient Utilization of Multiple Interfaces in Wireless Ad Hoc Networks Roy Friedman and Alex Kogan 16:52 Brief Announcement: The Speed of Broadcasting in Random Networks: Density Does Not Matter Nikolaos Fountoulakis, Konstantinos Panagiotou and Anna Huber Saturday September 26th8:30-10:15 TADDS Workshop Session 110:15-10:45 Coffee break 10:45-12:45 2 Workshops (TADDS and GT) Session 2 12:45-14:45 Lunch (on your own) 14:45-16:45 GT Workshop Session 3 |