Technical Program

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

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

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

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

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

  Actual Causality: A Survey

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

Amphitheater Charles Mérieux, Place de l’École
Session Chair: Koichi 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

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

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

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

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

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

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

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

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

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

Visit of the famous “traboules” of Lyon.

Meeting Points:

• 3:30pm in front of Amphitheater Charles Mérieux, Place de l’École
  We will go together to Metro stop “Vieux Lyon” where the visit will begin

• Or if you go by yourself:
  4:15pm at Metro Stop “Vieux Lyon“

Metro itinerary from Debourg (closest station to SSS) to Vieux Lyon:

– Take Metro B at “Debourg” towards « Charpennes »
– Get off at Saxe-Gambetta
– Take Metro D towards « Gare de Vaise »
– Get off at « Vieux Lyon »

Transfer from ENS Lyon to Musée des Confluences.

Group departure at 6:30pm.

– By foot (approx. 1km)
– Or by tramway:
Take Tram T1 at « ENS de Lyon » towards « Perrache »,
get off at « Musée des Confluences ».

Musée des Confluences, 86 Quai Perrache, 69002 Lyon

Don’t forget to bring your SSS badge!

Group will leave SSS at 6:30pm.

– By foot (approx. 1km)
– Or by tramway:
Take Tram T1 at « ENS de Lyon » towards « Perrache »,
get off at « Musée des Confluences ».

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

Specification 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.

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

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

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

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

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

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