# Workshop ANR DESCARTES / ESTATE 1er et 2 avril 2019 - Roscoff  # Programme

## Lundi 1er avril

• 14h - Réunions privées DESCARTES / ESTATE -
• 15h40 - Pause
• 16h15 - (LaBRI)
Soyez Efficace, Rembobinez
Nous proposons un algorithme, appelé SDR, qui réinitialise de manière auto-stabilisante et totalement distribuée un réseau anonyme, lorsque c’est nécessaire, c’est-à-dire que chaque processus, détectant localement une anomalie, peut déclencher une réinitialisation.

SDR est coopératif au sens où il coordonne les réinitialisations concurrentes afin de gagner en efficacité. Nous utilisons SDR pour rendre auto-stabilisant des algorithmes distribués. Notre approche permet de résoudre efficacement à la fois les problèmes statiques et dynamiques, comme le montrent les deux exemples d’algorithme utilisant SDR que nous proposons.

En effet, nous avons, tout d’abord, conçu un algorithme auto-stabilisant silencieux calculant une $(f,g)$-alliance 1-minimale dans les réseaux identifiés. Aucun algorithme auto-stabilisant ne résolvait auparavant ce problème sans aucune restriction sur $f$ et $g$.

Nous avons ensuite proposé un algorithme auto-stabilisant d’unisson. Ce dernier stabilise en $O(n)$ rondes et $O(Dn^2)$ mouvements ($D$ est le diamètre et $n$ est le nombre de processus dans le réseau). Par rapport aux algorithmes précédents, notre algorithme améliore le temps de stabilisation en mouvements sans pénalité sur le temps de stabilisation en rondes, ni l’espace mémoire utilisé.

En collaboration avec Stéphane Devismes.
• 16h45 - (LIP6)
Deterministic Treasure Hunt in the Plane with Angular Hints
A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most $D>0$ from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than $2\pi$ whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent’s trajectory. It is well known that without any hint the optimal (worst case) cost is $\Theta(D^2)$. We show that if all angles given as hints are at most $\pi$, then the cost can be lowered to $O(D)$, which is optimal. If all angles are at most $\beta$, where $\beta>0$. For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than $2\pi$, then we show that cost $\Theta(D^2)$ cannot be beaten.

Joint work with Yoann Dieudonné, Andrzej Pelc, and Franck Petit.
• 17h15 - (IRISA)
Contention-related crash failures
A new notion of process failure explicitly related to contention has recently been introduced by Gadi Taubenfeld (NETYS 2018). More precisely, given a predefined contention threshold λ, this notion considers the execution in which process crashes are restricted to occur only when process contention is smaller than or equal to λ. If crashes occur after contention bypassed λ, there are no correctness guarantees. It was shown that, when λ $= n-1$, consensus can be solved in an $n$-process asynchronous read/write system despite the crash of one process, thereby circumventing the well-known FLP impossibility result.

In this talk, I will present $k$-set agreement and renaming algorithms that are resilient to two types of process crash failures: “λ-constrained” crash failures (as previously defined) and classical crash failures.

Joint work with with Michel Raynal and Gadi Taubenfeld.

## Mardi 2 avril

• 9h - (IRIF)
Local verification of global proofs
In distributed decision, a classic mechanism is to label every node of the network with a proof, to certify the current configuration. These proofs are local in the sense that every node is given its own proof. In this talk I will present our results on global proofs, that is, proofs that every node can access.

Joint work with Juho Irvonen.
• 9h30 - (Vérimag)
Formal proofs on Mobile Robots Swarms
Mobile robot networks emerged in the past few years as a promising distributed computing model ensuring more resiliency. Existing work in the literature typically ensures the correctness of mobile robot protocols via ad hoc handwritten proofs, which are both cumbersome and error-prone. Formal methods approaches, such as model-checking, program synthesis, and proof assistants, try to overcome these limitations.

In this talk, I will present our work on the third approach : the Pactole library for the Coq proof assistant. We designed it to accommodate all existing model variants, so that a unified framework may express all results and proofs, allowing to compare them. In particular, it can express both correctness and impossibility results. If proving requires expertise, specifying a protocol with Pactole is rather easy, thanks to familiar mathematical notations. Time permitting, I will illustrate this on several case studies.

Joint work with Thibault Balabonski, Pierre Courtieu, Sébastien Tixeuil, and Xavier Urbain.
• 10h - (UNAM, Mexico)
Anonymous Shared-Memory Computability
I describe some of the history and our results on computability in the anonymous shared-memory model, and its relation to the combinatorial topology approach to distributed computability.

Joint work with Carole Delporte, Hugues Fauconnier, and Nayuta Yanagisawa.
• 10h40 - Pause
• 11h15 - (LIP6)
Byzantine Gathering in Polynomial Time
Gathering a group of mobile agents is a fundamental task in the field of distributed and mobile systems. This can be made drastically more difficult to achieve when some agents are subject to faults, especially the Byzantine ones that are known as being the worst faults to handle. In this paper we study, from a deterministic point of view, the task of Byzantine gathering in a network modeled as a graph. In other words, despite the presence of Byzantine agents, all the other (good) agents, starting from (possibly) different nodes and applying the same deterministic algorithm, have to meet at the same node in finite time and stop moving. An adversary chooses the initial nodes of the agents (the number of agents may be larger than the number of nodes) and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label. The agents move in synchronous rounds and can communicate with each other only when located at the same node. Within the team, $f$ of the agents are Byzantine. A Byzantine agent acts in an unpredictable and arbitrary way. For example, it can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. Besides its label, which corresponds to a local knowledge, an agent is assigned some global knowledge denoted by $GK$ that is common to all agents. In literature, the Byzantine gathering problem has been analyzed in arbitrary $n$-node graphs by considering the scenario when $GK = (n,f)$ and the scenario when $GK=f$. In the first (resp. second) scenario, it has been shown that the minimum number of good agents guaranteeing deterministic gathering of all of them is $f+1$ (resp. $f+2$). However, for both these scenarios, all the existing deterministic algorithms, whether or not they are optimal in terms of required number of good agents, have the major disadvantage of having a time complexity that is exponential in $n$ and $L$, where $L$ is the value of the largest label belonging to a good agent. In this paper, we seek to design a deterministic solution for Byzantine gathering that makes a concession on the proportion of Byzantine agents within the team, but that offers a significantly lower complexity. We also seek to use a global knowledge whose the length of the binary representation (that we also call size) is small. In this respect, assuming that the agents are in a strong team i.e., a team in which the number of good agents is at least some prescribed value that is quadratic in $f$, we give positive and negative results. On the positive side, we show an algorithm that solves Byzantine gathering with all strong teams in all graphs of size at most $n$, for any integers $n$ and $f$, in a time polynomial in $n$ and the length $|l_{min}|$ of the binary representation of the smallest label of a good agent. The algorithm works using a global knowledge of size $O(\log\log\log n)$, which is of optimal order of magnitude in our context to reach a time complexity that is polynomial in $n$ and $|l_{min}|$. Indeed, on the negative side, we show that there is no deterministic algorithm solving Byzantine gathering with all strong teams, in all graphs of size at most $n$, in a time polynomial in $n$ and $|l_{min}|$ and using a global knowledge of size $o(\log\log\log n)$.

Joint work with Yoann Dieudonné and Anissa Lamani.
• 11h45 - (LaBRI)
On restricted-use objects and beyond
A shared-memory counter is a well-studied and widely-used concurrent object. It supports two operations: An Increment operation that increases its value by 1 and a Read operation that returns its current value. Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of concurrent objects that includes counters.

Later Aspnes, Attiya and Censor observed that the lower bound holds only when numerous operations are applied to the object and does not rule out the possibility of obtaining algorithms whose step complexity is sub-linear when the number of operations is bounded. Leveraging this observation, they presented a counter for which operations’ step complexity is polylogarithmic in $n$, the number of processes, as long as the object’s value is polynomial in $n$.

In this talk, I will explain the algorithmic ideas of their construction and discuss other directions to circumvent the lower bound by Jayanti et al.

Joint work with Corentin Travers, Danny Hendler, and Ahad Mirza Baig.
• 12h15 - Déjeuner
• 14h - (IRISA)
Plus faible détecteur de défaillances pour l’exclusion mutuelle en mémoire partagée
Failure detectors are devices that provides the processes with information on failures. They were introduced to enrich asynchronous systems so that it becomes possible to solve problems (or implement concurrent objects) that are otherwise impossible to solve in pure asynchronous systems where processes are prone to crash failures. The most famous failure detector (which is called “eventual leader” and denoted $\Omega$) is the weakest failure detector which allows consensus to be solved in $n$-process asynchronous systems where up to $t = n-1$ processes may crash in the read/write communication model, and up to $t < n/2$ processes may crash in the message-passing communication model. When looking at the mutual exclusion problem (or equivalently the construction of a lock object), while the weakest failure detectors are known for both asynchronous message-passing systems and read/write systems in which up to $t < n$ processes may crash, for the starvation-freedom progress condition, it is not yet known for weaker deadlock-freedom progress condition in read/write systems. This paper extends the previous results, namely, it presents the weakest failure detector that allows mutual exclusion to be solved in asynchronous $n$-process read/write systems where any number of processes may crash, whathever the progress condition (deadlock-freedom or starvation-freedom).

Joint work with with Carole Delporte and Hugues Fauconnier.
• 14h30 - (Vérimag)
Acyclic Strategy for Silent Self-Stabilization in Spanning Forests
We formalize design patterns, commonly used in self-stabilization, to obtain general statements regarding both correctness and time complexity. Precisely, we study a class of algorithms devoted to networks endowed with a sense of direction describing a spanning forest whose characterization is a simple (i.e., quasi-syntactic) condition. We show that any algorithm of this class is (1) silent and self-stabilizing under the distributed unfair daemon, and (2) has a stabilization time polynomial in moves and asymptotically optimal in rounds. To illustrate the versatility of our method, we review several works where our results apply.

Joint work with with Karine Altisen and Anaïs Durand.
• 15h - (LIP6)
Tractable Reliable Broadcast with honest dealer in Multihop Networks
The reliable broadcast is one of the fundamental primitive deployable on top of a distributed system that guarantees the correct message exchange between processes even in case of failures. While considering quite strong assumptions, like a fully connected network, digitally signed messages or the knowledge about the network topology given to the processes, the problem can be efficiently solved (especially under the message complexity point of view), under weaker assumptions and thus more general scenarios where the network is incomplete and only authenticated channels are provided, the reliable broadcast problem may become untractable. We analyze and optimize the solutions available for the reliable broadcast problem with honest dealer for multi hop networks, assuming that the network topology is unknown to the processes and that only authenticated links are provided. We define optimizations for the state of art algorithms that aim to reduce the number of messages exchanged solving the problem and we show their efficiency while simulated on several kind of network topologies. We finally discuss the possible employment of such protocols on dynamic networks. Joint work with with Silvia Bonomi and Sébastien Tixeuil.
• 15h40 - Pause
• 16h15 - (LIP6)
Gracefully Degrading Gathering in Dynamic Rings
Gracefully degrading algorithms [Biely et al., TCS 2018] are designed to circumvent impossibility results in dynamic systems by adapting themselves to the dynamics. Indeed, such an algorithm solves a given problem under some dynamics and, moreover, guarantees that a weaker (but related) problem is solved under a higher dynamics under which the original problem is impossible to solve. The underlying intuition is to solve the problem whenever possible but to provide some kind of quality of service if the dynamics become (unpredictably) higher.In this paper, we apply for the first time this approach to robot networks. We focus on the fundamental problem of gathering a squad of autonomous robots on an unknown location of a dynamic ring. In this goal, we introduce a set of weaker variants of this problem. Motivated by a set of impossibility results related to the dynamics of the ring, we propose a gracefully degrading gathering algorithm.

Joint work with with Swan Dubois and Franck Petit.
• 16h45 - (IRIF)
Decidability of distributed complexity of locally checkable problems on paths
More than 20 years ago, Naor and Stockmeyer introduced the Locally Checkable problems (LCL). On a bounded degree graph, nodes need to find an output such as each node can check locally that it is coherent. If no node disagree, then the output is good. Such problems can be about coloring, maximal independent set… In their original paper, they prove that such problems on paths and cycles have 3 possible complexities: constant, log* and linear. Moreover, they prove that, given the acceptable outputs, the complexity can be decided in polynomial time. However, they only considered the case where the nodes do not have inputs.

In this talk, I will first introduce those results, and then present recent results about what happens when the nodes are given some input. In the latter case, the complexities remain the same, and it is still decidable to figure it out. However, it is more complicated, as in it at least PSPACE hard to decide it.

Joint work with with Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, and Jukka Suomela.
• 17h15 - ANR DESCARTES / ESTATE: Business Meeting -
• 18h - Fin du workshop