DISC 2013

Full Program

Monday – Workshops
Monday – DISC Tutorial & Welcome
Tuesday – DISC day one
Wednesday – DISC day two
Thursday – DISC day three
Friday – Workshops

Full Program in pdf

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


Wednesday, October 16, 2013 – DISC Day Two

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


Thursday, October 17, 2013 – DISC Day Three

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

Friday, October 18, 2013  –  Workshops II

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

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

Disc 2013 Sponsors