Monday – Workshops
Monday – DISC Tutorial & Welcome
Tuesday – DISC day one
Wednesday – DISC day two
Thursday – DISC day three
Friday – Workshops
Monday, October 14, 2013 – Workshops I
1st Workshop on Biological Distributed Algorithms (BDA)
8:30-10:30 Session 1
Session Chair: Yuval Emek
8:35-9:05 Invited Talk: J. Fisher (Microsoft Research UK and Univ. of Cambridge)
Executable Biology: Successes and Challenges
9:05-9:30 D. Alistarh, A. Cornejo, M. Ghaffari and N. Lynch
Firefly Synchronization with Asynchronous Wake-up
9:30-10:00 Invited Talk: S. Navlakha (USA, CMU)
Synaptic Pruning: An Algorithmic Perspective
10:00-10:30 Invited Talk: A. Korman (France, CNRS and Univ. of Paris Diderot)
Integrating Theoretical Algorithmic Ideas in Empirical Biological Study
10:30-11:00 Coffee Break
11:00-12:55 Session 2
Session Chair: Amos Korman
11:00-11:30 Invited Talk: O. Feinerman (Israel, Weizmann Institute)
Fighting noise with limited resources: an ant colony perspective
11:30-12:00 Invited Talk: Z. Bar-Joseph (USA, CMU)
Robust computing over networks: Lessons from nature
12:00-12:25 C. Lenzen and T. Radeva
The Power of Pheromones in Ant Foraging
12:25-12:55 Invited Talk: Y. Emek (Zurich, ETH)
Distributed computing on the (fruit) fly
12:55-14:30 Lunch
14:30-15:50 Session 3
Session Chair: Ziv Bar-Joseph
14:30-15:20 Keynote: U. Alon (Israel, Weizmann Institute)
Evolutionary tradeoffs and the geometry of phenotype space
15:20-15:45 S. Dolev, R. Gmyr, A.W. Richa, and C. Scheideler
Ameba-inspired Self-organizing Particle Systems
15:45-15:50 Closing remarks
2nd Workshop on Advances on Distributed Graph Algorithms (ADGA)
8:30-9:30 Christoph Lenzen
Distributed Algorithms on a Congested Clique
9:30-10:30 Rotem Oshman
Communication Complexity and Graph Algorithms
10:30-11:00 Coffee Break
11:00-12:00 Michael Elkin
Distributed Algorithms for Graph Coloring
12:00-13:00 Thomas Sauerwald
Distributed Load Balancing on Graphs
13:00-14:30 Lunch
14:30-15:30 Danny Dolev
Distributed Graph Algorithms and Very Large Scale Integrated Circuits
15:30-16:00 Coffee Break
8:30am-5:00pm – 5th Workshop on the Theory of Transactional Memory TransForm/EuroTM (WTTM 2013)
09:05-9:10 Welcome
09:10-9:45 Keynote: Hagit Attiya
A Programming Language Perspective on Transactional Memory Consistency
Seesion: TM Semantics
9:45-10:00 Mohsen Lesani and Jens Palsberg
Write-observation and Read-preservation TM Correctness Invariants
10:00-10:15 Mohsen Lesani, Victor Luchangco and Mark Moir
Specifying Transactional Memories with Nontransactional Operations
10:15-10:30 Wenjia Ruan, Yujie Liu and Michael Spear
On the Relationship Between Delaying Operators and Language-Level Semantics
10:30-11:00 Coffee Break
11:00-11:35 Keynote: Danny Hendler
STM contention management: from multiprocessors to distributed systems
11:35-12:10 Keynote: Costas Busch
Transactional memory schedulers for diverse distributed computing environment
Session: Contention Management: From multiprocessor to distributed TMs
12:10-12:35 Christopher Rossbach and Jean-Philippe Martin
Distributed Optimistic Concurrency Considered Optimistic
12:35-13:00 Shlomi Dolev, Panagiota Fatourou and Eleftherios Kosmas
Abort Free SemanticTM by Dependency Aware Scheduling of Transactional Instructions
13:00-14:30 Lunch break
14:30-15:05 Keynote: Michel Raynal
Hybrid implementations of concurrent objects
Seesion: Hybrid TM
15:05-15:20 Alex Matveev and Nir Shavit
Reduced Hardware Transactions: A Hybrid NOREC
15:20-15:35 Lingxiang Xiang and Michael Scott
Composable Partitioned Transactions
15:35-16:00 Coffee Break
Session: Parallelism
16:00-16:15 Victor Bushkov, Dmytro Dziuma, Panagiota Fatourou and Rachid Guerraoui
Snapshot Isolation Does Not Scale Either
16:15-16:30 Faith Ellen. Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani and Corentin Travers
Wait-Free Universal Constructions that ensure Timestamp-Ignoring Disjoint-Access Parallelism
Session: Multiversion Transactional Memories
16:30-16:45 Nuno Diegues and Paolo Romano
Input Acceptance of Time-Warping Transactional Memory
16:45-17:00 Priyanka Kumar and Sathya Peri
Multiversion Conflict Notion
Monday, October 14, 2013 – DISC 13 Tutorial and Welcome
16:00- 18:00 The Evolution of SDN and How Your Network Is Changing
Teemu Koponen – Nicira/VMWare
18:00- 18:30 Uri Alon – “Love and Fear in the Lab” – a guitar and discussion session.
18:30- 20:30 DISC Welcome Reception
Tuesday, October 15, 2013 – DISC Day One
8:30-10:25 Session 1a: Invited Lecture and Graph Problems in Message Passing
Session Chair: Yehuda Afek
8:30-8:35 Opening remarks
8:35-9:35 Invited Lecture: Ravi Rajwar – Intel
Adventures in Parallel Dimensions
9:35-10:00 Mohsen Ghaffari and Fabian Kuhn. (Best Paper)
Distributed Minimum Cut Approximation
10:00-10:25 David Woodruff and Qin Zhang.
When Distributed Computation is Communication Expensive
10:25-10:45 Coffee Break
10:45-12:58 Session 1b: Topology, Leader Election, and Spanning Trees
Session Chair: Michael Elkin
10:45-11:10 Emanuele Guido Fusco, Andrzej Pelc and Rossella Petreschi
Use knowledge to learn faster: Topology recognition with advice
11:10-11:35 George Giakkoupis, Maryam Helmi, Lisa Higham and Philipp Woelfel
An O(sqrt n) Space Bound for Obstruction-Free Leader Election
11:35- 12:00 Ittai Abraham, Danny Dolev and Joseph Halpern
Distributed Protocols for Leader Election: a Game-Theoretic Perspective
12:00- 12:25 Lélia Blin and Sébastien Tixeuil
Compact Deterministic Self-Stabilizing Leader Election: The Exponential Advantage of Being Talkative
12:25- 12:50 Alex Kravchik and Shay Kutten
Time Optimal Synchronous Self Stabilizing Spanning Tree
12:50- 12:57 Brief Announcement: Chen Avin, Michael Borokhovich, Zvi Lotker and David Peleg.
Distributed MST in Core-Periphery Networks
13:00-14:15 Lunch
14:15- 16:10 Session 1c: Software Transactional Memory
Session Chair: Victor Luchangco
14:15- 14:40 Mohsen Lesani and Jens Palsberg
Proving Non-opacity
14:40- 15:05 Danny Hendler, Alex Naiman, Sebastiano Peluso, Francesco Quaglia, Paolo Romano and Adi Suissa
Exploiting Locality in Lease-Based Replicated Transactional Memory via Task Migration
15:05- 15:30 Li Lu and Michael L. Scott
Generic Multiversion STM
15:30- 15:55 Nuno Diegues and João Cachopo
Practical Parallel Nesting for Software Transactional Memory
15:55- 16:10 Brief Announcements:
- Nuno Diegues and Paolo Romano.
Time-warp: lightweight abort minimization in Transactional Memory
- Nhan Nguyen, Philippas Tsigas and Håkan Sundell.
ParMarkSplit: A Parallel Mark-Split Garbage Collector Based on a Lock-Free Skip-List
16:10- 16:30 Coffee Break
16:30- 17:41 Session 1d: Shared Memory Executions
Session Chair: Michel Raynal
16:30- 16:55 Sagar Chordia, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam and Kapil Vaswani
Asynchronous Resilient Linearizability
16:55- 17:20 Gadi Taubenfeld
Fair Synchronization
17:20- 17:41 Brief Announcements:
- Hammurabi Mendes, Maurice Herlihy and Christine Tasson
The Topology of Asynchronous Byzantine Colorless Tasks
- Carlos Gómez-Calzado, Alberto Lafuente, Mikel Larrea and Michel Raynal
Revisiting Dynamic Distributed Systems
- Sergio Rajsbaum, Michel Raynal and Julien Stainer
What Can Be Computed in the Presence of Concurrent Solo Executions
17:41-18:00 Happy hour
18:00-19:45 DISC 2013 Business Meeting
8:30-10:20 Session 2a: Dijkstra Prize Ceremony and Invited Lecture;
Session Chair: Gadi Taubenfeld
8:30-9:30 Invited Lecture: Nati Linial – The Hebrew University
Simplicial complexes – Much more than a trick for concurrent computation lower bounds
9:30- 9:55 George Giakkoupis, Anne-Marie Kermarrec and Philipp Woelfel
Gossip Protocols for Renaming and Sorting
9:55- 10:20 Chen Avin and Robert Elsässer
Faster Rumor Spreading: Breaking the log n Barrier
10:20- 10:40 Coffee Break
10:40-13:00 Session 2b: Shared Memory Tasks and Data Structures
Session Chair:Dan Alistarh
10:40- 11:05 Erez Petrank and Shahar Timnat. (Best Student Paper)
Lock-Free Data Structure Iterators
11:05- 11:30 Kunlong Zhang, Yujiao Zhao, Yajun Yang, Yujie Liu and Michael Spear.
Practical Non-blocking Unordered Lists
11:30- 11:55 James Aspnes and Keren Censor-Hillel.
Atomic snapshots in expected $O(\log^3 n)$ steps using randomized helping
11:55- 12:20 Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni and Leslie Lamport.
Adaptive Register-Allocation with a linear number of registers
12:20- 12:45 Faith Ellen and Philipp Woelfel.
An Optimal Implementation of Fetch-and-Increment
12:45- 13:00 Brief Announcements:
- Aravind Natarajan and Neeraj Mittal.
A Concurrent Lock-Free Red-Black Tree
- Trevor Brown, Faith Ellen and Eric Ruppert.
A General Technique for Non-blocking Trees
13:00- 14:20 Lunch
14:20- 15:05 Session 2c: Replication and Consensus
Session Chair: Rotem Oshman
14:20- 14:45 Flavio Junqueira and Marco Serafini
On barriers and the gap between active and passive replication
14:45- 15:05 Brief Announcements:
- Danny Dolev and Christoph Lenzen.
Silence is Golden: Communication-Efficient Consensus Without a Common Clock
- Gregory Chockler, Dan Dobre and Alexander Shraer
Consistency and Complexity Tradeoffs for Highly-Available Multi-Cloud Store
- Christian Cachin, Dan Dobre and Marko Vukolić.
BFT Storage with 2t+1 Data Replicas
15:05- 15:30 Coffee break
15:30- 19:30 Excursion: Old City of Jerusalem Sight Seeing
19:30-22:30 DISC 2013 Banquet and award ceremony
8:30-10:10 Session 3a: Wireless networks
Session Chair: Chen Avin
8:30- 8:55 Bojun Huang and Thomas Moscibroda
Conflict Resolution and Membership Problem in Beeping Channels
8:55- 9:20 Yuval Emek and Roger Wattenhofer
Frequency Hopping against a Powerful Adversary
9:20- 9:45 Johannes Dams, Martin Hoefer and Thomas Kesselheim
Sleeping Experts in Wireless Networks
9:45- 10:10 Sebastian Daum, Seth Gilbert, Tomasz Jurdzinski, Dariusz Kowalski, Fabian Kuhn, Calvin Newport, Grzegorz Stachowiak and Michal Rozanski
Distributed Broadcast in SINR Models
10:10- 10:30 Coffee Break
10:30- 12:56 Session 3b: Crypto, Trust and Influence
Session Chair: Dahlia Malkhi
10:30- 10:55 Ashish Choudhury, Martin Hirt and Arpita Patra
Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity
10:55- 11:20 Paul Bunn and Rafail Ostrovsky
Secure End-to-End Communication with Optimal Throughput and Resilient Against Malicious Adversary
11:20- 11:45 Cyril Gavoille, Christian Glacet, Nicolas Hanusse and David Ilcinkas
On the Communication Complexity of Distributed Name-Independent Routing Schemes
11:45- 12:10 Silvio Frischknecht, Barbara Keller and Roger Wattenhofer
Convergence in (Social) Influence Networks
12:10- 12:35 Olivier Bournez, Jonas Lefèvre and Mikael Rabie
On trustful population protocols
12:35- 12:56 Brief Announcements:
- Faith Ellen, Rotem Oshman, Toni Pitassi and Vinod Vaikuntanathan
Private-Channel Models in Multi-Party Communication Complexity
- Cédric Auger, Zohir Bouzid, Pierre Courtieu, Sébastien Tixeuil and Xavier Urbain
Certified impossibility results for Byzantine-tolerant mobile robots
- Yonina Eldar, Idit Keidar and Stacy Patterson
Distributed Compressed Sensing for Sensor Networks
12:56- 14:00 Lunch
14:00-15:40 Session 3c: Networking I
Session Chair: Dmitri Perelman
14:00- 14:25 Erez Kantor, Israel Cidon and Shay Kutten
Prudent Opportunistic Cognitive Radio Access Protocols
14:25- 14:50 Michael Dinitz and Merav Parter
Braess’s Paradox in Wireless Networks: The Danger of Improved Technology
14:50- 15:15 Mohsen Ghaffari and Bernhard Haeupler
Fast Structuring of Radio Networks for Multi-Message Communications
15:15- 15:40 Ittay Eyal, Idit Keidar, Stacy Patterson and Raphael Rom
In-Network Analytics for Ubiquitous Sensing
15:40- 16:00 Coffee Break
16:00- 17:05 Session 3d: Networking II
Session Chair: Yuval Emek
16:00- 16:25 James Hegeman and Sriram Pemmaraju
A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location
16:25- 16:50 Sebastian Kniesburges, Andreas Koutsopoulos and Christian Scheideler
CONE-DHT: A distributed self-stabilizing algorithm for a heterogeneous storage system
16:50- 17:05 Brief Announcements:
- Marco Canini, Petr Kuznetsov, Dan Levin and Stefan Schmid.
Towards Distributed and Reliable Software Defined Networking
- Marcin Bienkowski, Nadi Sarrar, Stefan Schmid and Steve Uhlig.
Dynamic Forwarding Table Aggregation without Update Churn: The Case of Dependent Prefixes
17:05- 17:30 Coffee break
17:30- 19:10 DISC Event on Networking
17:30-17:40: Welcome Remarks
17:40-18:10: Resource Placement Under Stochastic Demands in Networked Topologies
Hanoch Levy, Tel Aviv University
18:10-18:40: Efficient multi-pattern matching on Compressed HTTP traffic.
Yaron Koral, Tel Aviv University and the Hebrew University
18:40-19:10: Some Open Questions on the Borderline of Networking and Distributed Computing.
Michael Schapira, the Hebrew University
8:30- 13:00 9th International Workshop on Foundations of Mobile Computing (FOMC)
8:30: Invited Talk: Dealing with Uncertainty in Wireless Communication
Fabian Kuhn
9:30: Distributed Queuing in Dynamic Networks,
Gokarna Sharma and Costas Busch
9:55: Relative Throughput – Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies,
Antonio Fernandez Anta, Chryssis Georgiou, Dariusz R. Kowalski, Joerg Widmer and Elli Zavou
10:20: Coffee Break
10:35: Invited Talk: Reusable Teamwork for Multi-Robot Teams
Gal Kaminka
11:35: Message and time efficient multi-broadcast schemes,
Liron Levin, Dariusz R. Kowalski and Michael Segal
12:00: Robust Leader Election in a Fast-Changing World,
John Augustine, Tejas Kulkarni, Paresh Nakhe and Peter Robinson
12:25: Jamming-Resistant Learning in Wireless Networks,
Johannes Dams, Martin Hoefer and Thomas Kesselheim
12:50: short break
1:00-1:30: FOMC Business Meeting
8:30-13:00 5th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)
8:30-8:35 Welcome & Opening
8:35-9:20 Merav Parter
Computing on Anonymous Dynamic Networks
9:20-10:05 Sébastien Tixeuil
Quantitative evaluation of self-stabilizing algorithms using probabilist model-checking and simulation.
10:05-10:25 Coffee Break
10:25-11:10 Stefan Schmid
Self-stabilizing and self-optimizing distributed datastructures
11:10-11:55 Roberto Baldoni
Computing on Anonymous Dynamic Networks
12:55-12:15 Coffee Break
12:15-13:00 Shay Kutten
Title: To be announced
