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.

Coffee Break
Nov 10 @ 10:00 AM – 10:30 AM

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

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
Nov 10 @ 12:00 PM – 1:30 PM

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

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
Coffee Break
Nov 10 @ 3:00 PM – 3:30 PM

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

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