Nov 8 @ 9:00 AM – 9:10 AM

Amphitheater Charles Mérieux, Place de l’École

Keynote 1: Joseph Halpern
Nov 8 @ 9:10 AM – 10:10 AM

Amphitheater Charles Mérieux, Place de l’École

Halpern  Actual Causality: A Survey

Session 1: Autonomous Robots
Nov 8 @ 10:40 AM – 12:20 PM

Amphitheater Charles Mérieux, Place de l’École
Session ChairKoichi Wada

  • Plane Formation by Semi-synchronous Robots in the Three Dimensional Euclidean Space. Taichi Uehara, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita
  • Synchronous Gathering without Multiplicity Detection: A Certified Algorithm. Thibaut Balabonski, Amélie Delga, Lionel Rieg, Sébastien Tixeuil, and Xavier Urbain
  • Complete Visibility for Robots with Lights in O(1) Time. Gokarna Sharma, Ramachandran Vaidyanathan, Jerry Trahan, Costas Busch, and Suresh Rai
  • Global Versus Local Computations: Fast Computing with Identifiers (Short Paper). Mikaël Rabie
Session 2: Stabilization
Nov 8 @ 2:00 PM – 3:40 PM

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Sebastien Tixeuil

  • On the power of oracle Omega? for self-stabilizing leader election in population protocols. Joffroy Beauquier, Blanchard Peva, Janna Burman, and Oksana Denysiuk
  • Snap-Stabilizing Tasks in Anonymous Networks. Emmanuel Godard
  • Snap-Stabilizing PIF on Arbitrary Connected Networks In Message Passing Model. Florence Leve, Khaled Mohamed, and Vincent Villain
  • Leader Election in Rings with Bounded Multiplicity (Short Paper). Karine Altisen, Ajoy K. Datta, Stéphane Devismes, Anaïs Durand, and Lawrence Larmore
Session 3: Fault-Tolerance
Nov 8 @ 4:10 PM – 5:40 PM

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Sara Bouchenak

  • Packet Efficient Implementation of the Omega Failure Detector. Quentin Bramas, Dianne Foreback, Mikhail Nesterenko, and Sebastien Tixeuil
  • Perfect Failure Detection with Very Few Bits. Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers, Petr Kuznetsov, and Thibault Rieutord
  • Asynchronous Non-Bayesian Learning in the Presence of Crash Failures. Lili Su and Nitin Vaidya
Business Meeting
Nov 8 @ 6:00 PM – 7:00 PM

Amphitheater Charles Mérieux, Place de l’École

Session 4: Networking
Nov 9 @ 9:00 AM – 10:30 AM

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Maria Potop-Butucaru

  • On-Line Path Computation and Function Placement in SDNs. Guy Even, Moti Medina, and Boaz Patt-Shamir
  • DecTDMA: A Decentralized-TDMA with Link Quality Estimation for WSNs. Olaf Landsiedel, Thomas Petig, and Elad Michael Schiller
  • PSVR – Self-stabilizing Publish/Subscribe Communication for Ad-hoc Networks (Short Paper). Gerry Siegemund and Volker Turau
  • Towards Efficient and Robust BFT Protocols with ER-BFT (Short Paper). Lucas Perronne and Sara Bouchenak
  • Infinite Unlimited Churn (Short Paper). Dianne Foreback, Mikhail Nesterenko and Sebastien Tixeuil
Session 5: Foundations
Nov 9 @ 11:00 AM – 12:50 PM

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Joffroy Beauquier

  • Automatic Addition of Conflicting Properties. Mohammad Roohitavaf and Sandeep Kulkarni
  • Wait-Free Solvability of Colorless Tasks in Anonymous Shared-Memory Model. Nayuta Yanagisawa
  • Making Local Algorithms Wait-free: The Case of Ring Coloring. Armando Castaneda, Carole Delporte, Hugues Fauconnier, Sergio Rajsbaum, and Michel Raynal
  • Analysis of Computing Policies Using SAT Solvers (Short Paper). Marijn J. H. Heule, Rezwana Reaz, H. B. Acharya, and Mohamed G. Gouda
  • Meta-algorithm to choose a good on-line prediction (Short Paper). Alexandre Dambreville, Joanna Tomasik, and Johanne Cohen
Keynote 2: Maurice Herlihy
Nov 9 @ 2:30 PM – 3:30 PM

Amphitheater Charles Mérieux, Place de l’École

maurice_herlihyDistributed Computing and Blockchains

Cryptocurrencies such as Bitcoin are in the news, including lurid stories of drug trafficking, extortion, massive thefts, mysterious identities, and epic technical failures. Nevertheless, such sensationalism should not distract from the possibly transformative effects of the underlying blockchain data structures and algorithms. Many of the problems in this domain are classical problems of distributed computing, and yet our community has so far played little part in recent developments. We will discuss why the distributed computing community (and the SSS community in particular) should pay more attention.

Keynote 3: Hagit Attiya
Nov 10 @ 9:00 AM – 10:00 AM

Amphitheater Charles Mérieux, Place de l’École

SpecHagit-Attiyaification and complexity of replicated objects

Modern replicated data stores aim to provide high availability, by immediately responding to client requests, often by implementing objects that expose concurrency and do not have a sequential specification, like multi-valued registers (MVRs).
We explore a recent model for replicated data stores that can be used to precisely specify causal consistency for such objects, and liveness properties like eventual consistency, without revealing details of the underlying implementation.
The model is used to prove what is the stronger consistency model that can be supported by an eventually consistent data store implementing MVRs, for a large class of protocols. For the same class, we prove that an eventually consistent and causally consistent replicated data store must send messages of unbounded size.

We further specify the list object, modeling the core functionality of replicated data stores for collaborative text editing and allowing users to concurrently edit a shared document, inserting and deleting elements (e.g., characters or lines).
A major factor determining the efficiency and practical feasibility of a collaborative text editing protocol is the space overhead of its metadata.
We prove that for a large class of protocols implementing a list, this space overhead is at least linear in the number of elements deleted from the list. A protocol in this class almost matches the lower bound.

Session 6: Stabilization and Byzantine Agents
Nov 10 @ 10:30 AM – 12:00 PM

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Sandeep Kulkarni

  • Self-Stabilizing Byzantine-Tolerant Distributed Replicated State Machine. Alexander Binun, Thierry Coupaye, Shlomi Dolev, Mohammed Kassi Lahlou, Marc Lacoste, Alex Palesandro, Reuven Yagel, and Leonid Yankulin
  • Self-stabilizing Byzantine Clock Synchronization with Optimal Precision. Pankaj Khanchandani and Christoph Lenzen
  • Robust Multi-Agent Optimization: Coping with Byzantine Agents with Input Redundancy. Lili Su and Nitin Vaidya
Session 7: Graph Algorithms
Nov 10 @ 1:30 PM – 3:00 PM

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Janna Burman

  • Self-stabilizing Metric Graphs. Jonas Lefèvre, Robert Gmyr, and Christian Scheideler
  • Searching for an Evader in an Unknown Graph by an Optimal Number of Searchers. Takahiro Yakami, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita
  • An efficient silent self-stabilizing 1-maximal matching algorithm under distributed daemon without global identifiers. Michiko Inoue, Fukuhito Ooshita, and Sebastien Tixeuil
Session 8: Stabilization and Multi-Agent Networks
Nov 10 @ 3:30 PM – 5:20 PM

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Eddy Caron

  • Self-Stabilizing Robots in Highly Dynamic Environments. Marjorie Bournat, Ajoy Datta, and Swan Dubois
  • Near-Optimal Self-Stabilizing Counting and Firing Squads. Christoph Lenzen and Joel Rybicki
  • Flocking with Oblivious Robots. Davide Canepa, Xavier Défago, Taisuke Izumi, and Maria Potop-Butucaru
  • Probabilistic Asynchronous Arbitrary Pattern Formation (Short Paper).
    Quentin Bramas and Sebastien Tixeuil
  • Polynomial Silent Self-Stabilizing p-Star Decomposition (Short Paper). Mohammed Haddad, Colette Johnen, and Sven Köhler
Nov 10 @ 5:20 PM – 5:30 PM

Amphitheater Charles Mérieux, Place de l’École