in conjonction with Workshop Complexité et Algorithmes (GT CoA/GDR CNRS IM)
Roscoff Apr. 1st–2nd, 2019
Details / Abstracts of Talks
- Byzantine Gathering in Polynomial Time
Sébastien Bouchard, with Yoann Dieudonné and Anissa LamaniGathering 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).
- Deterministic Treasure Hunt in the Plane with Angular Hints
Sébastien Bouchard, with Yoann Dieudonné, Andrzej Pelc, and Franck PetitA 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 beta0. 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.
- Gracefully Degrading Gathering in Dynamic Rings
Marjorie Bournat, with Swan Dubois and Franck PetitGracefully 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.
- Acyclic Strategy for Silent Self-Stabilization in Spanning Forests
Stéphane Devismes, with Karine Altisen and Anaïs DurandWe 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.
- Contention-related crash failures
Anaïs Durand, with Michel Raynal and Gadi TaubenfeldA 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.
- Byzantine Reliable Broadcast in Dynamic Networks
Giovanni Farina, with Silvia Bonomi and Sébastien Tixeuil
- Local Verification of Global Proofs
Laurent Feuilloley, with Juho IrvonenIn 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.
- Soyez Efficace, Rembobinez
Colette Johnen, with Stéphane DevismesNous 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é.
- On restricted-use objects and beyond
Alessia Milani, with Corentin Travers, Danny Hendler, and Ahad Mirza Baig
- Decidability of distributed complexity of locally checkable problems on paths
Mickael Rabie, with Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, and Jukka SuomelaMore 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.
- Anonymous Shared-Memory Computability
Sergio Rajsbaum, with Carole Delporte, Hugues Fauconnier, and Nayuta YanagisawaI 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.
- Plus faible détecteur de défaillances pour l’exclusion mutuelle en mémoire partagée
Michel Raynal, with Carole Delporte and Hugues FauconnierFailure 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).
- Formal proofs on Mobile Robots Swarms
Lionel Rieg, with Thibault Balabonski, Pierre Courtieu, Sébastien Tixeuil, and Xavier UrbainMobile 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.
© 