Seminar
Talks are scheduled on Wednesdays from 11am to noon in room 178 (LaBRI), and sometimes also at https://webconf.u-bordeaux.fr/b/arn-4tr-7gp (you can also find some of the recordings there)
Subscription: send an email to sympa@diff.u-bordeaux.fr with subject "subscribe labri.algodist-gt your_name your_firstname".
Upcoming talks :
Mercredi 2024-11-20: «L’algorithmique distribuée et les graphes dynamiques», David Ilcinkas (LaBRI)
Nous verrons les liens entre algorithmique distribuée et graphes dynamiques. En particulier, nous verrons comment les méthodes et raisonnements classiques du distribué peuvent permettre de trouver des solutions élégantes à des probl
mes même centralisés de graphes dynamiques.
Mercredi 2024-12-04: Robin Vacus (Bocconi University of Milan)
Archives
2024
Mercredi 2024-11-06: «Verification of Population Protocols with Unordered Data», Corto Mascle (LaBRI)
Population protocols are a well-studied model of distributed computation in which a crowd of anonymous finite-state agents communicate via pairwise interactions. Together they decide whether their initial configuration, i.e., the initial distribution of agents in each state, satisfies a property. We will start with a reminder on Population protocols.
Population protocols with unordered data (PPUD) is an extension introduced by Blondin and Ladouceur (ICALP'23) where processes carry a piece of data from an infinite data domain. We consider the decidability and complexity of formally verifying these protocols. We show that checking if a PPUD is well-specified, i.e., whether it correctly computes some function, is undecidable in general. By contrast, we consider a subclass of PPUD, called Immediate-Observation, on which the problem is decidable. Moreover, we exhibit a large yet natural class of problems on IOPPUD, which are all decidable in EXPSPACE. We will also see some intriguing open problems on this model.
Mercredi 2024-10-23: «Giant Components in Random Temporal Graphs», Michael Raskin (LaBRI)
A temporal graph is a graph whose edges appear only at certain points in time. Recently, a natural temporal analog of the Erdős-Rényi random graph model has been introduced. The proposed model is obtained by randomly permuting the edges of an Erdős-Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erdős-Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting.
In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at p = log n/n the size of the largest temporally connected component increases from o(n) to n-o(n). This threshold holds for both open and closed connected components, i.e. components that allow, respectively forbid, their connecting paths to use external nodes.
Mercredi 2024-10-09: «Modular population protocols», Michael Raskin (LaBRI)
Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication opportunities occur nondeterministically, allowing the agents involved to change their states based on each other's states. Population protocols are often studied in terms of reaching a consensus on whether the input configuration satisfied some predicate.
A desirable property of a computation model is modularity, the ability to combine existing simpler computations in a straightforward way. In the present paper we present a more general notion of functionality implemented by a population protocol in terms of multisets of inputs and outputs. This notion allows to design multiphase protocols as combinations of independently defined phases. The additional generality also increases the range of behaviours that can be captured in applications (e.g. maintaining the role distribution in a fleet of servers).
We show that composition of protocols can be performed in a uniform mechanical way, and that the expressive power is essentially semilinear, similar to the predicate expressive power in the original population protocol setting.
Mercredi 2024-09-25: «Space Optimal Self-Stabilizing Token Circulation in the Local Broadcast Model», Gabriel Le Bouder (LaBRI)
One specificity of wireless networks is that any message sent by some device is received identically by all the neighbors of the emitter. In other words, it is impossible to send any information to one specific neighbor and not to the other. This model is therefore more challenging that communication models assuming identified communication channels, or even simply port-known communication.
Token Circulation is a problem in which a unique token must circulate indefinitely in all the nodes of the network. The passing of the token from the current token holder to one neighbor requires that this neighbor of the token holder receives the token, and be the only neighbor to do so. Up to today, this problem has been essentially tackled under the port-known state-model, in which sending a message to a unique neighbor is trivial. In the Local Broadcast State Model, the simple sending of a token to a neighbor is a whole challenge.
We address this problem under the paradigm of Self-Stabilization, i.e. transient-fault-robustness. We propose an algorithm that is optimal in terms of use of memory, i.e. Θ(log log n) bits per node.
Mercredi 2024-09-11: «Efficient Wait-Free Linearizable Implementations of Approximate Bounded Counters Using Read-Write Registers», Colette Johnen (LaBRI)
Relaxing the sequential specification of a shared object is a way to obtain an implementation with better performance compared to implementing the original specification. We apply this approach to the Counter object, under the assumption that the number of times the Counter is incremented in any execution is at most a known bound m. We consider the k-multiplicative-accurate Counter object, where each read operation returns an approximate value that is within a multiplicative factor k of the accurate value. More specifically, a read is allowed to return an approximate value x of the number v of increments previously applied to the counter such that v/k≤x≤vk. We present three algorithms to implement this object in a wait-free linearizable manner in the shared memory model using read-write registers. All the algorithms have read operations whose worst-case step complexity improves exponentially on that for an exact m-bounded counter (which in turn improves exponentially on that for an exact unbounded counter). Two of the algorithms have read step complexity that is asymptotically optimal. The algorithms differ in their requirements on k, step complexity of the increment operation, and space complexity.
(This talk contains the technical details after the previous overview talk)
Mercredi 2024-06-26: «Efficient Wait-Free Linearizable Implementations of Approximate Bounded Counters Using Read-Write Registers», Colette Johnen (LaBRI)
Relaxing the sequential specification of a shared object is a way to obtain an implementation with better performance compared to implementing the original specification. We apply this approach to the Counter object, under the assumption that the number of times the Counter is incremented in any execution is at most a known bound.
Mercredi 2024-06-12: «Some new results with k-set agreement», Mouna Safir (IRIF)
In this talk, I will present our investigation of the solvability of k-set agreement among n processes in distributed systems prone to different types of process failures. k-set agreement allows each process to propose a value and decide a value such that at most k different values are decided by the correct processes, in such a way that, if all the correct processes propose the same value v, they will decide v. We specially explore two scenarios: synchronous message-passing systems prone to up to t Byzantine failures of processes, and asynchronous shared memory systems prone to up to t crash failures. Our goal is to address the gaps left by previous works in these areas. In the message passing system with Byzantine failures we enrished the system with authentication, we present an algorithm that ensures k-set agreement in only two rounds, with no constraints on the number of faults t, with k determined as k≥⌊n/(n−t)⌋+1, and an optimal algorihtm ensuring k-set agreement in t+1 rounds for k≥⌊n/(n−t)⌋. While in the crash asynchronous shared memory systems, we introduce an algorithm that ensure k-set agreement when n>2t for k≥⌊ (n−t)/(n−2t)⌋+1, and an impossibility result for k≤⌊(n−t)/(n−2t)⌋+1.
Mercredi 2024-05-29: «Is maze-solving parallelizable?», Romain Cosson (INRIA Paris)
Can you find a short path, without a map? Is maze-solving parallelizable? These questions can be cast formally using the toolbox of competitive analysis, a toolkit that was developed since the 1990s to study online algorithms. In this talk, I will present these problems, that are known as « layered graph traversal » (introduced by the literature on online algorithms) and « collective tree exploration » (introduced by the literature on distributed algorithms). We will focus on the connexions between these problems and use them as a case study of the connections between online an distributed algorithms.
Mercredi 2024-05-15: «(Online) Continual Learning», Akka Zemari (LaBRI)
In real-world supervised learning, training data is often unavailable simultaneously, requiring models to adapt to incoming information. Sequential or naive training of pre-trained models on new tasks can lead to «forgetting» of prior knowledge. Incremental learning methods aim to adapt models to new data while retaining past knowledge. Focusing on the streaming scenario, where data arrives one sample at a time, our «Move-to-Data» method selectively adjusts network weights without systematic gradient descent. Compared to the state-of-the-art methods, our approach outperforms and learns significantly faster, presenting a promising solution for efficient and effective continual learning.
N.B. : No prerequisites are required to attend the presentation; we will provide the necessary reminders to make the presentation self-contained.
Mercredi 2024-04-10: «In Search of the Lost Tree: Hardness and relaxation of spanning trees in temporal graphs, Timothée Corsini
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). These graphs are temporally connected if all ordered pairs of vertices are connected by a path that traverses edges in chronological order (a temporal path). Reachability in temporal graphs departs significantly from standard reachability; in particular, it is not transitive, with structural and algorithmic consequences. For instance, temporally connected graphs do not always admit spanning trees, i.e., subsets of edges that form a tree and preserve temporal connectivity among the nodes.
In this talk, we revisit fundamental questions about the loss of universality of spanning trees. We show that deciding if a spanning tree exists in a given temporal graph is NP-complete. What could be appropriate replacement for the concept? Beyond having minimum size, spanning trees enjoy the feature of enabling reachability along the same underlying paths in both directions, a pretty uncommon feature in temporal graphs. We explore relaxations in this direction and show that testing the existence of bidirectional spanning structures (bi-spanners) is tractable in general. On the down side, finding minimum such structures is NP-hard even in simple temporal graphs. Still, the fact that bidirectionality can be tested efficiently may find applications, e.g. for routing and security, and the corresponding primitive that we introduce in the algorithm may be of independent interest.
Mercredi 2024-03-27: «Universal Exploration Sequences and Undirected s-t Connectivity (continued)», Sébastien Bouchard
Undirected s-t connectivity (USTCON) is a SL-complete problem (SL stands for Symmetric Log-space). During decades, researchers tried to propose a log-space algorithm for this problem. It would prove that SL=L. This was achieved in 2005 by Omer Reingold. His USTCON algorithm can also be used to construct sequences of integers called universal exploration sequences (UXS) which, given the number of vertices of a graph, can guide a deterministic walk, of polynomial length, allowing to visit all its nodes.
The talk will provide a high-level view of Reingold's algorithm use to construct UXS, as a continuation of the previous talk.
Mercredi 2024-03-20: «Universal Exploration Sequences and Undirected s-t Connectivity», Sébastien Bouchard
Undirected s-t connectivity (USTCON) is a SL-complete problem (SL stands for Symmetric Log-space). During decades, researchers tried to propose a log-space algorithm for this problem. It would prove that SL=L. This was achieved in 2005 by Omer Reingold. His USTCON algorithm can also be used to construct sequences of integers called universal exploration sequences (UXS) which, given the number of vertices of a graph, can guide a deterministic walk, of polynomial length, allowing to visit all its nodes.
The talk will present USTCON, UXS, and provide a high-level view of Reingold's algorithm and its use to construct UXS.
Mercredi 2024-03-06: «Characterizing consensus in the Heard-Of model», Igor Walukiewicz
The Heard-Of model is a simple and relatively expressive model of distributed computation. Because of this, it has gained a considerable attention of the verification community. We give a characterization of all algorithms solving consensus in a fragment of this model. The fragment is big enough to cover many prominent consensus algorithms. The characterization is purely syntactic: it is expressed in terms of some conditions on the text of the algorithm.
Mercredi 2024-02-14: «FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems», Colette Johnen (LaBRI)
FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks.
A round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity is presented. Initially, processes only know the number of processes N in the system and their identifier. Due to the dynamics of the network links, messages can be lost. The size of any message is bounded to 2N+msgSize+O(log(N)) bits where msgSize is the bound size in bits of the broadcast data.
We also present an FIFO atomic broadcast algorithm that uses the proposed FIFO broadcast and deliver primitives.
Mercredi 2024-01-31: «A fully polynomial self-stabilizing unisson algorithm and its consequences», Frédéric Mazoit (LaBRI)
A follow up from the previous talks in which we present an efficient unisson algorithm, and we show that it can be used to simulate certain algorithms without too much memory.
Mercredi 2024-01-24: «Hardness and Approximation for the Star p-Hub Routing Cost Problem in Metric Graphs», Ling-Ju Hung (National Taipei University of Business, Taiwan)
Given a metric graph G = (V, E, w), a specific vertex c ∈ V , and an integer p, let T be a depth-2 spanning tree of G rooted at c such that c is adjacent to p vertices called hubs and each of the remaining vertices is adjacent to a hub. The Star p-Hub Routing Cost Problem is to find a spanning tree T of G satisfying the conditions stated above such that the sum of distances between all pairs of vertices in T is minimized. In this paper, we prove that the Star p-Hub Routing Cost Problem is NP-hard. A 3-approximation algorithm running in time O(n²) is given for solving the same problem where n is the number of vertices in the input graph. Moreover, we give an example to show that the analysis of the approximation ratio cannot be better than 2 − ϵ for any ϵ > 0.
Mercredi 2024-01-17: «Protocols with constant local storage and unreliable communication», Michael Raskin (LaBRI)
Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication occurs nondeterministically, allowing the involved agents to change their states based on each other's states.
In the present paper we study unreliable models based on population protocols and their variations from the point of view of expressive power. We model the effects of message loss. We show that for a general definition of protocols with unreliable communication with constant-storage agents such protocols can only compute predicates computable by immediate observation (IO) population protocols (sometimes also called one-way protocols). Immediate observation population protocols are inherently tolerant to unreliable communication and keep their expressive power under a wide range of fairness conditions. We also prove that a large class of message-based models that are generally more expressive than IO becomes strictly less expressive than IO in the unreliable case.
2023
Mercredi 13 decembre: Introduction to the continuous distributed monitoring model and application to the countdown problem, Nicolas Hanusse (LaBRI)
In the distributed monitoring model, we assume that every node takes as input streams of data. A coordinator aims at computing function over the union of streams. The goal is limit the amount de communications between the coordinator and the other nodes but providing garantees on the function computed at any time. In this presentation, we focus on the problem of counting.
Mercredi 06 decembre: Kernelizing Temporal Exploration Problems, Petra Wolf (LaBRI)
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs G = (G1, G2, …, GL) that share a common vertex set but might have different edge sets. The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the k-arb NS-TEXP problem, where the agent’s task is to visit at least k vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor k-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices n, lifetime L, number of vertices to visit k, and maximal number of connected components per time step γ; as well as in the combined parameters L + k, L + γ, and k + γ. On the way to establishing these lower bounds, we answer a couple of questions left open by Erlebach and Spooner. We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph Informally, this parameter measures how dynamic thetemporal graph is. Our main algorithmic result is the construction of a polynomial (in p(G)) kernel for the more general Weighted k-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least k.
Mercredi 29 novembre: Byzantine gathering in polynomial time, Sébastien Bouchard (LaBRI)
Gathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary graph: despite the presence of Byzantine agents, the goal is to ensure that all the other (good) agents, executing the same algorithm, eventually meet at the same node and stop. Initially, each agent gets as input a different label and some global knowledge that is common to all agents. The agents move in synchronous rounds and communicate with each other only when located at the same node. There are f Byzantine agents. These agents act in an unpredictable way, e.g., they may convey arbitrary information or forge any label. In the literature, the gathering algorithms working in such a context all have an exponential time complexity in the number n of nodes and the labels of the good agents. In this paper, we design a deterministic algorithm to solve Byzantine gathering in time polynomial in n and the logarithm l of the smallest label of a good agent, provided the agents are a strong team i.e., a team where the number of good agents is at least some quadratic polynomial in f. Our algorithm requires global knowledge that can be coded in O(log log log n) bits: we prove this size is of optimal order of magnitude to obtain a polynomial time complexity in n and l with strong teams.
Mercredi 15 novembre: Continued: «Making synchronous algorithms efficiently self-stabilizing in arbitrary asynchronous environments», Frédéric Mazoit (LaBRI)
This paper deals with the trade-off between time, workload, and versatility in self-stabilization, a general and lightweight fault-tolerant concept in distributed computing. In this context, we propose a transformer that provides an asynchronous silent self-stabilizing version Trans(AlgI) of any terminating synchronous algorithm AlgI. The transformed algorithm Trans(AlgI) works under the distributed unfair daemon and is efficient both in moves and rounds.Our transformer allows to easily obtain fully-polynomial silent self-stabilizing solutions that are also asymptotically optimal in rounds.We illustrate the efficiency and versatility of our transformer with several efficient (i.e., fully-polynomial) silent self-stabilizing instances solving major distributed computing problems, namely vertex coloring, Breadth-First Search (BFS) spanning tree construction, k-clustering, and leader election.
This will be a whiteboard talk with the technical details omitted in the first (overview) talk.
Mercredi 08 novembre: «Words fixing the kernel network and maximal independent sets in graphs», Maximilien Gadouleau (Durham University, UK)
The simple greedy algorithm to find a maximal independent set of a graph can be viewed as a sequential update of a Boolean network, where the update function at each vertex is the conjunction of all the negated variables in its neighbourhood. In general, the convergence of the so-called kernel network is complex. A word (sequence of vertices) fixes the kernel network if applying the updates sequentially according to that word. We prove that determining whether a word fixes the kernel network is coNP-complete. We also consider the so-called permis, which are permutation words that fix the kernel network. We exhibit large classes of graphs that have a permis, but we also construct many graphs without a permis.
Mercredi 25 octobre: «Making Self-Stabilizing algorithms for any Locally Greedy Problem», Jonas Sénizergues (LaBRI)
Mendable graph problems are a generalization of greedy problems where any partial solution may be transformed -instead of completed- into a global solution: every time we extend the partial solution, we are allowed to change the previous partial solution up to a given distance. "Locally" here means that to extend a solution for a node, we need to look at a constant distance from it.
We propose a self-stabilizing algorithm computing a (k,k-1)-ruling set (i.e. a "maximal independent set at distance $k$"). By combining this technique multiple times, we compute a distance-$K$ coloring of the graph. With this coloring we can finally simulate \local~model algorithms running in a constant number of rounds (which exists for mendable problems), using the colors as "unique" identifiers.
Mercredi 18 octobre: «Making synchronous algorithms efficiently self-stabilizing in arbitrary asynchronous environments», Frédéric Mazoit (LaBRI)
This paper deals with the trade-off between time, workload, and versatility in self-stabilization, a general and lightweight fault-tolerant concept in distributed computing. In this context, we propose a transformer that provides an asynchronous silent self-stabilizing version Trans(AlgI) of any terminating synchronous algorithm AlgI. The transformed algorithm Trans(AlgI) works under the distributed unfair daemon and is efficient both in moves and rounds.Our transformer allows to easily obtain fully-polynomial silent self-stabilizing solutions that are also asymptotically optimal in rounds.We illustrate the efficiency and versatility of our transformer with several efficient (i.e., fully-polynomial) silent self-stabilizing instances solving major distributed computing problems, namely vertex coloring, Breadth-First Search (BFS) spanning tree construction, k-clustering, and leader election.
Mercredi 04 octobre: «Distributed Derandomisation Revisited», Timothé Picavet (LaBRI)
One of the cornerstones of the distributed complexity theory is the derandomiza- tion result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves a locally checkable labeling problem (LCL) can be derandomized with at most ex- ponential overhead. The original proof assumes that the number of random bits is bounded by some function of the input size. We give a new, simple proof that does not make any such assumptions—it holds even if the randomized algorithm uses infinitely many bits. While at it, we also broaden the scope of the result so that it is directly applicable far beyond LCL problems.
Mercredi 27 septembre: «Coordination games on graphs», Michael Raskin (LaBRI)
The version of coordination games on oriented graphs that I will be talking about has been introduced (as far as I know) by Krzysztof Apt (also under the name of «Social Network Games»). The setting contains multiple agents with asymmetric influence between them. There are the options available (e.g. in which format to write the documents), not everyone has access to all the options available (e.g. if there are some Windows-only, macOS-only, and GNU/Linux-only options), and for every player and every option there is an intrinsic pleasantness, but also convenience of using the same format as people who influence you.
There are all the natural questions about games (equilibrium, uniqueness of equilibrium, behaviour of series of local improvements, paradox of choice etc.), and even if the topic has not become popular, some people have answered some of these questions (I have also done a bit). I will give a relaxed overview.
Lundi 19 juin : Self-stabilizing clock synchronization in dynamic networks Louis de Monterno (LIX)
We consider networked systems in which each agent holds a certain variable,
called clock, and study the synchronization problem:
all clocks must eventually reach equal values modulo some given positive integer P,
despite the arbitrary values of the clocks. We present some scenarios in which this problem is useful.
Agents communicate by exchanging messages and dynamic graphs are used to describe the time-varying communication graph. The connectivity in the networks captured by an integer, called "dynamic diameter". We introduce the SAP algorithm, and prove that it solves the synchronization problem under the sole condition of a finite dynamic diameter. We examine its behavior when a bound on the dynamic diameter is known by the agents, and show that it still works when no bound is known by using an adaptive mechanism for clock periods, with a limited stabilization time overhead compared to the previous case.
We then stretch the class of networks in which the synchronization problem is solvable as much as possible: We introduce the class of strongly centered networks, and show that SAP also solves the synchronization problem in this class of dynamic networks. Then we exhibit scenarios suggesting that no further relaxation is possible.
In the last part, we introduce our latest work, that is, a probabilistic proof of correctness of SAP, which covers a large range of probabilistic models, such that the PUSH and PULL models.
Lundi 15 mai : Intéropérabilité des technologies de communication dans les réseaux véhiculaires Dorine Tabary (DISC, Université de Franche-Comté)
Un réseau véhiculaire est un réseau sans fil dynamique. Les véhicules partagent des données
via différentes technologies de communication telles le BlueTooth, le LTE (cellulaire) ou le WiFi.
Le choix de la technologie de communication influe sur le débit disponible,
surtout quand la technologie de communication est partagée entre plusieurs utilisateurs.
La présentation répond à la question : Comment maximiser le débit applicatif à travers le choix des technologies de communication dans les réseaux véhiculaires ?
De précédents travaux ont montré que dans le cadre de systèmes centralisés, le problème est No-Apx. Il ne peut exister de résolution rapide (en temps polynomial par rapport à la taille de l'entrée d'une machine de Turing), même approchée. Dès lors, le cadre est distribué et porte sur les systèmes multi-agents. Le problème est d'abord modélisé, formalisé et classé comme étant PLS-difficile. L'objectif d'atteindre un optimum local n'admet donc pas de résolution à la fois rapide et optimale. Cependant, il est possible d'avoir un résultat rapide et approché.
Une résolution algorithmique notée SARE est proposée. L'algorithme maximise le débit en tenant compte de la stabilité des liens grâce à l'utilisation de l'apprentissage par renforcement. Des garanties de performance sont fournies grâce à la théorie des jeux. L'efficacité est ainsi prouvée grâce à l'optimal de Pareto, qui garantit l'utilisation optimale des ressources disponibles. La stabilité est également garantie avec l'équilibre de Nash. Par la suite, cette approche est soumise à des tests logiciels grâce à l'outil JBotSim. SARE est comparée dans des scénarios basiques avec deux approches algorithmiques : l'algorithme de Dijkstra distribué qui fournit des arbres de plus courts chemins et à un algorithme de choix des technologies qui sélectionne toujours selon le débit maximal.
Lundi 24 avril : Temporally connected components Jason Schoeters (University of Cambridge)
Temporal graphs are graphs in which edges can appear and disappear over time.
We answer the question ``What does a connected component correspond to in temporal graphs?'' Indeed, many forms of connectivity exist in temporal graphs, some of which are defined with journeys, i.e composed of successive edges in time. We present some results concerning components defined with journeys.
After a general introduction presenting among other things the hierarchy of temporal connectivity and its implications, we study S components, where there is a source vertex which can reach all the other vertices of the component with journeys. Structural and algorithmic results are given. We generalize by considering sliding time windows, closed components (journeys remain inside the component), and/or allowing the source to change between windows.
Finally, we complete results concerning TC components, where each node must reach each other node, and its variations. We more finely study corresponding decision problems concerning fixed parameters.
Lundi 3 avril : Recovering disrupted airline operations through matching augmentations Julien Bensmail (I3S/INRIA, Université Côte d'Azur)
In a graph, it is well known that a non-maximum matching can be made larger by applying a so-called augmentation operation. Due to a classical result of Berge, by repeatedly applying this operation, we actually necessarily end up with a maximum matching.
In connection with practical motivations, Nisse, Salch, and Weber considered the influence on this fact of restricting the length~$k$ of the paths we are allowed to augment. In particular, they proved that reaching, via augmentations of $(\leq k)$-paths, a maximum matching from an initial matching can be done in polynomial time for any graph when $k=3$, while the same problem is \textsf{NP}-complete for any $k \geq 5$. The latter result remains true for bipartite graphs, while we still have no clue for trees. Still, Nisse, Salch, and Weber exhibited a polynomial-time algorithm solving this problem for any path.
In a work with Garnero and Nisse, we made some progress towards understanding this problem for general trees. In particular, we have exhibited polynomial-time solving algorithms for a few more classes of trees, including bounded-degree trees, caterpillars, subdivided stars, and trees where the vertices with degree at least~$3$ are sufficiently far apart. We have also obtained some negative results for modified versions of the problem.
During this talk, we will present the proofs of some of these results, and mention some remaining open questions.
Lundi 27 mars : Structures de données pour environnements distribués à grande échelle : Étude des systèmes ouverts Grégoire Bonin (Université de Nantes)
Dans les systèmes multi-thread modernes, de nouveaux processus peuvent arriver au cours de l’exécution : nous appelons cela les systèmes ouverts. Cela nous amène à étudier la puissance de synchronisation des objets distribués, et plus particulièrement la faisabilité des constructions universelles, sous cette nouvelle hypothèse. Nous présenterons les résultats obtenus sur l’universalité du consensus et l’extension de la hiérarchie wait-free de Herlihy dans les systèmes ouverts, ainsi qu’une étude de complexité et une solution sur les constructions universelles faiblement cohérentes.
Lundi 20 mars : Introduction to tree-independence number Clément Dallard (LIFO, University of Orléans)
Tree decompositions are a common and useful data structure for designing dynamic programming algorithms for graph problems. In order to obtain efficient algorithms, one looks for a tree decomposition of the input graph that minimizes some measure on the subgraphs induced by the bags. For instance, when this measure is the number of vertices, we obtain the well-known notion of treewidth. In this talk, the considered measure is the independence number.
The independence number of a tree decomposition of a graph G is the smallest integer k such that each bag induces a subgraph with independence number at most k. The tree-independence number of G is defined as the minimum independence number over all tree decompositions of G. Given a tree decomposition with bounded independence number, the Maximum Weight Independent Set and several related NP-hard problems can be solved in polynomial time.
We will discuss how to compute tree decompositions with bounded independence number efficiently (when they exist), the algorithmic use of such tree decompositions, and the strong relationship with the notion of (tw,ω)-boundedness.
Lundi 13 mars : Calculating invariants of concurrent programs via persistence Cameron Calk (LIS, Université Aix-Marseille)
In this talk, I will discuss links between natural homology and persistent homology. The former is an algebraic invariant of directed spaces, which constitute a semantic model of concurrent programs. The latter was developed in the context of topological data analysis, and extracts topological properties of point-cloud data sets while eliminating noise. In both approaches, the evolution homological properties are tracked through a sequence of inclusions of usual topological spaces. Exploiting this similarity, I will show that natural homology may be considered a persistence object, and may be calculated as a colimit of uni-dimensional persistent homologies along traces. Finally, I will suggest further links and avenues of future work in this direction.
Lundi 6 mars : Memory-Optimization for Self-Stabilizing Distributed Algorithms Gabriel Le Bouder (LIP6, Sorbonne Université)
Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it will return a normal behavior in finite time. Several constraints concern algorithms designed for distributed systems. Asynchrony is one emblematic example. With the development of networks of connected, autonomous devices, it also becomes crucial to design algorithms with a low energy consumption, and not requiring much in terms of resources.
One way to address these problems is to aim at reducing the size of the messages exchanged between the nodes of the network. This thesis focuses on the memory optimization of the communication for self-stabilizing distributed algorithms. We will present a negative results, proving the impossibility to solve some problems under a certain limit on the size of the exchanged messages, and a particularly efficient algorithms in terms of memory for one fundamental problem in distributed systems: the token circulation.
Lundi 27 février : Improving blockchain performance by removing bottlenecks in system design Kadir Korkmaz (LaBRI, Université de Bordeaux)
The first blockchain, Bitcoin, was proposed in 2008 as a mechanism to implement a digital currency without trusted parties: prior to the bitcoin protocol, digital currencies
were implemented using trusted intermediaries such as banks, and the bitcoin protocol eliminated the need for trusted parties.
The Bitcoin protocol has several inherent performance problems - low throughput and high latency - due to design choices. Since 2008,
researchers have been designing blockchain protocols to overcome the inherent problems of the Bitcoin protocol. After Bitcoin,
blockchain technology has found numerous applications beyond digital currencies, but today the biggest obstacle to the global adoption of blockchain technology is poor performance.
In this work, we aim to improve the performance of existing blockchains by removing bottlenecks in the system design. To this end, we investigate bottlenecks in the system design of existing blockchains and propose mechanisms to mitigate them. Specifically, we target consensus-level bottlenecks arising from a single leader and network-level bottlenecks arising from the store-validate-forward gossip dissemination mechanism.
Our contribution is twofold: first, we designed ALDER, a generic construction to improve the performance of leader-based blockchains. ALDER extends the consensus algorithm of an existing leader-based blockchain to enrich it with multiple leaders that cooperate to handle user requests. The ALDER design increases the throughput and latency of existing blockchains by eliminating bottlenecks at the consensus and network levels. We provide a detailed evaluation of ALDER through large-scale experiments. Second, we provide an in-depth analysis of the IDA-Gossip protocol: a chunk-based gossip dissemination protocol. IDA-Gossip is an important primitive for blockchains to remove the bottleneck stem from the store-validate-forward gossip dissemination mechanism, but its properties have not been extensively studied. Our work quantifies the performance of IDA-Gossip with different protocol parameters using experiments and simulations. The goal of our investigation is to help researchers understand the properties of IDA-Gossip by revealing its behavior under different conditions.
Lundi 20 février : Distributed Certification for Classes of Dense Graphs Frédéric Mazoit (LaBRI, Université de Bordeaux)
A proof-labeling scheme (PLS) is a mechanism used for distributively certifying a boolean predicate on graphs. In a PLS, a certificate is assigned to each node. By exchanging the certificates once, between neighbors only, the nodes check that the system is in a correct state. The goal is to minimize the size of the certificates. Many PLSs have been designed for certifying specific predicates, such as cycle-freeness, minimum-weight spanning tree, planarity, etc.
In 2021, a breakthrough has been obtained by proving that a large set of properties (expressible in MSO2 logic) have compact PLSs in a large class of networks (the graphs of bounded tree-depth). This result has been extended to the larger class of graphs with bounded tree-width, using certificates on O(log^2 n) bits.
In this talk, I will present a joint work with Fraigniaud, Montealegre, Rapaport and Todinca in which we obtain a similar result for a slightly weaker class of properties (expressible in MSO1 logic) but on a larger class of graphs (with bounded clique-width), which, contrary to the previous results, includes dense graphs.
Lundi 6 février : Byzantine gathering in polynomial time Sebastien Bouchard (LIP6, Sorbonne Université)
Gathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary graph: despite the presence of Byzantine agents, the goal is to ensure that all the other (good) agents, executing the same algorithm, eventually meet at the same node and stop. Initially, each agent gets as input a different label and some global knowledge that is common to all agents. The agents move in synchronous rounds and communicate with each other only when located at the same node. There are f Byzantine agents. These agents act in an unpredictable way, e.g., they may convey arbitrary informations or forge any label. In the literature, the gathering algorithms working in such a context all have an exponential time complexity in the number n of nodes and the labels of the good agents. In this paper, we design a deterministic algorithm to solve Byzantine gathering in time polynomial in n and the logarithm l of the smallest label of a good agent, provided the agents are a strong team i.e., a team where the number of good agents is at least some quadratic polynomial in f. Our algorithm requires global knowledge that can be coded in O(log log log n) bits: we prove this size is of optimal order of magnitude to obtain a polynomial time complexity in n and l with strong teams.
Lundi 23 janvier : Cryptographie en boîte blanche Agathe Houzelot (LaBRI, U. Bordeaux)
La cryptographie a au départ été conçue pour protéger des informations confidentielles transmises à travers un canal non sécurisé. Dans ce cas d'usage, l'émetteur et le destinataire chiffrent et déchiffrent le message dans un environnement sécurisé. Seuls les messages chiffrés peuvent éventuellement être interceptés par un attaquant. La confidentialité des clés doit donc être assurée lorsque l'attaquant a un accès en boîte noire à l'algorithme: il ne peut en voir que les entrées et les sorties.
Cependant, dans de nombreux cas d'usage actuels, l'attaquant a en fait accès à des données supplémentaires, notamment via des canaux auxiliaires. C'est le contexte de la boîte grise. Imaginez par exemple un attaquant ayant volé votre carte bancaire. Il pourrait sans problème mesurer le temps d'exécution de l'algorithme de chiffrement ou la consommation de courant de la puce pendant l'exécution. Si l'implémentation n'est pas protégée, ces informations pourraient lui permettre de retrouver la clé secrète utilisée.
Pire encore, dans le contexte des applications mobiles (paiement sans contact, services de streaming, ...) ou des objets connectés, les dispositifs manquent souvent de hardware sécurisé et leur environnement d'exécution, souvent entièrement contrôlé par l'utilisateur, expose une surface d'attaque très large. Dans le modèle de la boîte blanche, on considère que l'attaquant a un accès total à l'exécutable, qu'il peut lire et modifier à sa guise, et un contrôle total de l'environnement d'exécution. Il peut donc notamment voir toutes les valeurs stockées en mémoire. L'implémentation elle-même est alors la dernière ligne de défense contre l'extraction de clé.
Dans cette présentation, j'expliciterai plus en détail ce contexte de la boîte blanche et montrerai certaines attaques et contremesures pratiques. J'évoquerai également certains résultats théoriques ayant été démontrés ces dernières années.
Lundi 9 janvier : SASA, a SimulAtor of Self-stabilizing Algorithms Erwan Jahier (Université Grenoble Alpes)
In this presentation, I will present SASA, an open-source SimulAtor of Self-stabilizing Algorithms. Self-stabilization defines the ability of a distributed algorithm to recover after transient failures.
SASA is implemented as a faithful representation of the atomic-state model (also called the locally shared memory model with composite atomicity). This model is the most commonly used one in the self-stabilizing area to prove both the correct operation of self-stabilizing algorithms and complexity bounds on them.
SASA encompasses all features necessary to debug, test, verify and analyze self-stabilizing algorithms.
All these facilities are programmable to enable users to accommodate to their particular needs. For example, asynchrony is modeled by programmable stochastic daemons playing the role of input sequence generators; properties of algorithms can be checked using formal test oracles. It is also possible to perform automated verification via model-checking (on small topologies).
The SASA distribution provides several facilities to easily achieve (batch-mode) simulation campaigns. We show that the lightweight design of SASA allows to efficiently perform huge such campaigns.
Following a modular approach, we have aimed at relying as much as possible the design of SASA on existing tools, including Ocaml, Dot, and several tools developed in the Verimag laboratory.
---
2022
Lundi 12 décembre : Reliable Broadcast and Consensus made Self-stabilizing and Byzantine Fault-tolerant Romaric Duvignau (University of Gothenburg)
We study a well-known communication abstraction called Byzantine Reliable Broadcast (BRB). This abstraction is central in the design and implementation of fault-tolerant distributed systems, as many fault-tolerant distributed applications require communication with provable guarantees on message deliveries. Our study focuses on fault-tolerant implementations for message-passing systems that are prone to process- failures, such as crashes and malicious behaviors. At PODC 1983, Bracha and Toueg, in short, BT, solved the BRB problem. BT has optimal resilience since it can deal with up to t < n/3 Byzantine processes, where n is the number of processes. We'll show here how we can adapt BT's algorithm to make it self-stabilizing in order to solve asynchronous single-instance BRB. We also consider the problem of recycling instances of single-instance BRB. Our self-stabilizing Byzantine fault-tolerant (SSBFT) recycling for time-free systems facilitates the concurrent handling of a predefined number of BRB invocations and, by this way, can serve as the basis for SSBFT consensus.
Lundi 5 décembre Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity Fabien Dufoulon (Université de Houston)
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best-known (randomized) MIS algorithms have O(log n) round complexity on general graphs [Luby, STOC 1986] (where n is the number of nodes), while the best-known lower bound is Ω(√(log(n)/log(log n))) [Kuhn, Moscibroda, and Wattenhofer, JACM 2016]. Breaking past the O(log n) bound or showing stronger lower bounds have been longstanding open problems.
Energy is a premium resource in battery-powered wireless and sensor networks, and the bulk of it is used by nodes when they are awake, i.e., when they are sending, receiving, and even just listening for messages. On the other hand, when a node is sleeping, it does not perform any communication and thus spends very little energy. Several recent works have addressed the problem of designing energy-efficient distributed algorithms for various fundamental problems. These algorithms operate by minimizing the number of rounds in which any node is awake, also called the awake complexity. An intriguing question is whether one can design a distributed MIS algorithm that is significantly more energy-efficient (having very small awake complexity) compared to existing algorithms.
Our main contribution is to show that MIS can be computed in awake complexity that is exponentially better compared to the best known round complexity of O(log n) and also bypassing its fundamental Ω(√(log(n)/log(log n))) round complexity lower bound (almost) exponentially. Specifically, we show that MIS can be computed by a randomized distributed (Monte Carlo) algorithm in O(log log n) awake complexity with high probability. Since a node spends significant energy only in its awake rounds, our result shows that MIS can be computed in a highly energy-efficient way compared to the existing MIS algorithms.
Lundi 21 novembre : An introduction to Boolean networks Loïc Paulevé (LaBRI, U. Bordeaux)
Boolean (automata) networks (BNs) are fundamental models of dynamical systems, which are closely related to cellular automata and 1-bounded Petri nets. One of the core features of BNs is the parametrization of the synchronization of updates of automata with the so-called *update mode* (parallel, asynchronous, etc.).
I'll give an overview of approaches and theorems related to the analysis of their dynamical properties depending on the update mode and from different perspectives: combinatorics, model checking, abstract interpretation, control, and applications to biology.
Lundi 7 novembre : Towards finite automata inside (Zooming through whatever is distributed) Michael Raskin (LaBRI, U. Bordeaux)
I will talk about some of the work I have done where distributed systems are restricted to be simple enough for description via finite automata (and also what happens if you slightly generalise or further restrict them…). This will include population protocols and regular transition systems. To make those two look relatively similar, I will start with an overview of some other fields where I have also worked from a (partially) distributed system point of view.
Lundi 24 octobre : A study of reachability in temporal graphs Timothée Corsini (LaBRI, U. Bordeaux)
Dynamic networks are a complex topic. Not only do they inherit the complexity of static networks (as a particular case) while making obsolete many techniques for these networks; they also happen to be deeply sensitive to specific definitional subtleties, such as strictness (can consecutive edges of a same path be used at the same time instant?), properness (can adjacent edges be present at the same time?) and simpleness (can an edge be present more than once?). These features, it turns out, have a significant impact on the answers to various questions, which is a frequent source of confusion and incomparability among results. In this paper, we explore the impact of these notions, and of their interactions, in a systematic way. Our conclusions show that these aspects really matter. In particular, most of the combinations of the above properties lead to distinct levels of expressivity of a temporal graph in terms of reachability. Then, we advocate the study of an extremely simple model -- happy graphs -- where these distinctions vanish.
Lundi 10 octobre 2022: An introduction to Petri Nets Thibault Hilaire (LaBRI, U. Bordeaux)
Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modeling and analysis of hardware, software, and database systems, as well as chemical, biological, and business processes. In this talk, I will explain what is a Petri Net and some of their variants and I will speak of the two main questions on Petri Nets that are the Reachability Problem and the Coverability Problem for which I will present the the reasoning behind the algorithm of Karp-Miller that solve the problem.
Lundi 12 septembre (14h, Amphi du LaBRI): Requêtes de distance et de proximité pour des entités mobiles distribuées (Soutenance de thèse) Tobias Castanet (LaBRI, U. Bordeaux)
Avec le développement des technologies de l'information, les ordinateurs deviennent plus accessibles et mieux connectés, et sont de plus en plus utilisés dans des contextes où la mobilité joue un rôle important. Des jeux vidéos permettent à un grand nombre de joueurs d'interagir dans un même monde virtuel, et des réseaux de véhicules connectés sont envisagés pour améliorer la sécurité routière. Dans de tels contextes distribués, on ne peut partir du principe que les entités peuvent partager leur position avec tous les participants. Il y a donc un besoin fort d'algorithmes capables de maintenir des propriétés en relation avec la distance entre les entités, tout en nécessitant un nombre minimal de messages et de temps de calcul. Dans cette thèse, deux problèmes sont étudiés : permettre à deux entités d'estimer efficacement la distances qui les sépare, et leur permettre de répondre à la requête suivante : « Quelles entités sont situées dans un certain rayon autour de moi ? ».
Lundi 27 juin : Local routing algorithms on Euclidean spanners with small diameter Yan Garito (ENS Rennes)
Given a set of n points in the plane, we present two
constructions of geometric r-spanners with r >= 1 based on a
hierarchical decomposition. These graphs have O(n) edges and
diameter O(log n). We then design online routing algorithms on
these graphs.
The first construction is based on Theta_k-graphs (with k > 6
and k = 2 mod 4). The routing algorithm is memoryless and local
(i.e. it uses information about the closed neighborhood of the current
vertex and the destination). It has routing ratio 1/(1- 2sin(pi/k))
and finds a path with O(log^2 n) edges.
The second construction uses a TD-Delaunay triangulation, which is
a Delaunay triangulation where the empty regions are homothets of an
equilateral triangle. The associated routing algorithm is local and
memoryless, has a routing ratio of 5/(sqrt 3), finds a path
consisting of $O(log^2 n) edges and requires the pre-computation
of vertex labels of O(log^2 n) bits (assuming the nodes are
placed on a grid of polynomial size).
We have examples that show when using either of our routing
algorithms, in the worst case, the paths returned by the algorithm can
consist of Omega(log^2 n) edges.
Lundi 17, 24 et 31 janvier : Proving in Coq: A user perspective David ILCINKAS (LaBRI, Bordeaux)
Several frameworks for verification of distributed computing results via
proof assistants exist. These frameworks are developed by proof
assistant experts, usually with the help of distributed computing
experts. Sébastien Bouchard and I wanted to know how much these
frameworks could be used without relying on coq experts, or at the very
least without relying on the coq experts that designed such frameworks.
For this purpose, Sebastien and I tried to verify in Coq a not-so-hard
but also not-completely-trivial result about graph exploration by mobile
robots. This talk is a feedback about this (eventually successful)
experiment.