Seminars

4/2/205 at salle REU 04.05 (LIS Luminy)

’‘TBA’‘
by Pascal Felber

TBA
10/12/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Seminar cybersecurity : TBA’‘
by Dhekra Mahmou, LIMOS, Clermont-Ferrand

TBA
12/11/2024, 9h00 at Amphi TBA (Luminy)

’‘Seminar cybersecurity : soutenances UE Veille Sécurité’‘
by Étudiants du M2FSI

TBA
22/10/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Seminar cybersecurity: Secure Computation - Protecting the privacy of data used in distributed computation’‘
by Geoffroy Couteau, (IRIF Paris)

The importance of privacy over networks is well-acknowledged: more than 85% of our Internet communications are encrypted, and end-to-end encryption is becoming a standard in messaging apps. Yet, with the explosive growth of social networks and machine learning applications, our private data is also routinely revealed to third parties when it is used in distributed computations (in Cloud storage, social networks, apps, recommendation systems, ads, and more). Secure computation addresses this issue by providing a means to execute distributed computations without compromising private data. This talk will cover the old and recent developments in this area and discuss the remaining barriers to be lifted before deploying secure computation on the large scale.
08/10/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory’‘
by Maria Kokkou (LIS)

he problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (Gouda fairness [Gouda 2001]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require Ω(log n) bits of memory per node, even for ring topologies [Dolev et al. 1999]. This is joint work with Jérémie Chalopin and Shantanu Das, arXiv 2408.08775
1/10/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘ Distributed Computability on colorless task for sub-IIS mod’‘
by Yannis Coutouly (LIS)

This talk present a new theorem of colorless computability for general adversary of the IIS-model. It starts to recall the usual encoding of distributed system into simplicial complexes. This type of encoding are already used to provide some computability result for some specific shared memory model of communication (IIS). We enrich this model with an adversary that can model any failures pattern on such communication. Such adversary where proven to be challenging to tackle, especially the non-compact type. Using a new topology on the set of execution, from an article presented at DISC23, we extend a well-know result on distributed colorless task (such as consensus, k-set Agreement…) which state (roughly) : The computability of a distributed system can be reduced to a problem of existence of a continuous function between a topological space and a simplicial complexe. More formally : A task (I,O,Delta) is solvable on M a general adversary of the IIS model if and only if there is a continuous function from geo(I imes M) to |O|. Depending on the time, I may talk about some application of such theorem on some task such as the set-agreement.
24/09/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Seminar Cybersecurity: Distributed Identity Management with Minimal Synchronization’‘
by Mathieu Gestin (IRISA Rennes)

Distributed Identity Management System (DIMS) is a new paradigm in Identity Management Systems (IMS). It allows the user to control authentication and authorization mechanisms relative to its identity elements. This paradigm is particularly interesting because it increases privacy guarantees while being more resilient to faults. This talk will explain why distribution is an interesting property for IMS. We will also see how this distribution can be attained through anonymous credentials and distributed ledgers. Finally, we will study the synchronization requirements of such systems. As we will see, and unlike a common belief, consensus, synchronization, or Blockchain are unnecessary when it comes to building a DIMS. A careful analysis of the synchronization requirements coupled with new distributed cooperation tools can, therefore, lead to significant efficiency gains.
17/9/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Is maze-solving parallelizable?’‘
by 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.
10/9/2024, 9h30 at Amphi 9 et 12, Campus de Luminy

’‘Soutenances de stages de fin d’études’‘
by M2 students FSI
9/7/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Non-Negotiating Distributed Computing’‘
by Corentin Travers (LIS)

In the non-negotiating model, a process decides a priori what it is going to communicate to the other processes, before the computation starts, and proceeds regardless of what the process hears from others during an execution. We consider non-negotiating distributed computing in the read/write shared memory model in which processes are asynchronous and subject to crash failures. We show that non-negotiating distributed computing is universal, i.e., capable of solving any colorless task solvable by an unrestricted full-information algorithm in which processes can remember all their history, and send it to the other processes at any point in time. To prove this universality result, we present a non-negotiating algorithm for solving multidimensional approximate agreement, with arbitrary precision ϵ > 0. Joint work with Carole Delporte-Gallet, Hugues Fauconnier, Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers
2/7/2024, 10h30 at CIRM

’‘Journée équipe Dalgo’‘
by Stagiaires/Post-Doc/Doctorants

Chaque année, notre équipe organise des journées afin que tous les stagiaires puissent présenter leurs travaux. Cette année cette journée aura lieu dans la salle A2 du CIRM (sur le site de Luminy). Vous trouverez le planning des exposés ci-dessous :

- 9h30-9h50: Manal CHABANE, Schéma de signature numérique avec l’algorithme de cryptographie asymétrique RSA
- 9h50-10h10: Abanoub ABDELSHAHID, Simulateur pour l’algorithme distribué de consensus Raft
- 10h10-10h30: Dang Dinh NGUYEN, Sécurité des méta-données dans les applications de messagerie instantanée
- 11h00-11h30: Anatole GROSDOY, Énumération lexicographique d’ensembles indépendants maximaux
- 11h30-12h: Pierre DURIEUX, Énumération d’objets métriques dans les graphes
- 14h00-14h30: Baksi SOUMIL, Wait-free implementation of 2-window-register object with swap objects
- 14h30-15h: Yao David KOLEGAIN, Lattice agreement problem in asynchronous systems with Byzantine failures
25/6/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Des CRDTs aux PCDOs pour aborder la cohérence dans les systèmes distribués asynchrones.’‘
by Amaury Joly (LIS)

Les Process-Commutative Data Objects (PCDO) sont une avancée innovante en gestion de données distribuées, situés entre les CRDTs (Commutative Replicated Data Type) et les registres distribués totalement ordonnés. Ils nécessitent uniquement un ordre local des opérations pour chaque processus individuel. Cette présentation introduira dans un premier temps les CRDTs, puis explore comment les PCDO combinent Cohérence Éventuelle Forte (SEC) et Cohérence Pipeline (PC) pour augmenter le champ d’usage des CRDTs. Un algorithme générique pour implémenter les PCDO sera présenté, illustré par des exemples concrets tels que le transfert d’argent ou l’édition collaborative. Sera ensuite abordée la manière dont se type de donnée se comporte dans un contexte byzantin en comparaison à des approches plus classique de cohérence forte.
18/4/2024, 10h45 at salle REU 04.05 (LIS Luminy)

’‘Self-Stabilizing Algorithms’‘
by Lélia Blin (IRIF)

Dans le contexte des réseaux à grande échelle, la tolérance aux pannes est une nécessité. L’auto-stabilisation est une approche algorithmique de la tolérance aux pannes dans les systèmes distribués. Son objectif est de gérer la corruption de la mémoire des processeurs due à des défaillances transitoires. L’efficacité d’un algorithme d’auto-stabilisation est caractérisée par plusieurs paramètres, notamment (1) le temps nécessaire au système pour revenir à une configuration légale après une corruption arbitraire de la mémoire de ses processeurs, et (2) l’espace mémoire utilisé par les processeurs pour exécuter l’algorithme. La minimisation de l’espace mémoire est motivée par de nombreux aspects, tels que les réseaux (par exemple les réseaux de capteurs) avec un espace mémoire limité, la minimisation des échanges de données entre les processeurs, et la limitation du stockage de l’information pour utiliser des techniques de redondance. Ce séminaire présentera l’auto-stabilisation à travers deux problèmes classiques principaux : la construction d’arbres couvrants, en particulier ceux de poids minimum, et l’élection d’un leader. Il couvrira les liens entre l’auto-stabilisation et les techniques de décision distribuées, y compris le calcul des bornes inférieures de l’espace mémoire nécessaire pour résoudre les problèmes susmentionnés à l’aide d’algorithmes auto-stabilisants.
26/3/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Building a Nest by an Automaton’‘
by Dariusz Dereniowski, Gdansk University of Technology

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid ZxZ. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the shape, is initially connected. The (Manhattan) distance between the furthest cells of the shape is called its span. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest. That is, the robot has to move all bricks in such a way that the span of the resulting shape be the smallest. In this talk we discuss how to do it.
12/3/2024, 10h30 at salle REU 04.05 (LIS Luminy)

’‘Bacterial Consensus’‘
by Thomas Nowak (ENS Paris-Saclay & IUF)

Computing via synthetically engineered bacteria is a vibrant and active field with numerous applications in bio-production, bio-sensing, and medicine. Motivated by the lack of robustness and by resource limitation inside single cells, distributed approaches with communication among bacteria have recently gained in interest. In this talk, we focus on the problem of population growth happening concurrently, and possibly interfering, with the desired bio-computation. Specifically, we present a fast protocol in systems with continuous population growth for the majority consensus problem and prove that it correctly identifies the initial majority among two inputs with high probability. We also present a fast protocol that correctly computes the NAND of two inputs with high probability. By combining NAND gates with the majority consensus protocol as an amplifier, it is possible to compute arbitrary Boolean functions. The proposed protocols help set the stage for bio-engineered distributed computation that directly addresses continuous stochastic population growth.
16/1/2024 : 10h30 at salle REU 04.05 (LIS Luminy)

’‘Introduction aux méthodes et problématiques d’optimisations rencontrées en apprentissage automatique’‘
by Francois-Xavier Dupé, QARMA, LIS

Cet exposé présentera une partie des problématiques rencontrées en apprentissage automatique. Chaque problématique implique une modélisation conduisant à un problème d’optimisation souvent simplifié via des hypothèses assez fortes. L’augmentation de la taille des modèles (nombre de paramètres) et de la quantité de données demande l’utilisation d’algorithmes de résolution capable de passer à l’échelle, d’où l’utilisation de méthodes stochastiques et de questions de distributions des calculs. Autour de ces méthodes d’autres questions se posent comme la borne en erreur de généralisation ou la correction des biais connus ou non. L’exposé sera l’occasion de présenter ces questions et leurs implications.
19/12/2023 : 10h30 at salle REU 04.05 (LIS Luminy)

’‘Using Indirect Surveys to Monitor Society’‘
by Antonio Fernadez-Anta, Imdea Networks Institute

The Network Scale-up Method (NSUM) is a method to estimate the size of unknown populations in a social network. It is based on data collected with indirect surveys in which participants report information of their contacts, which increase the reach and privacy versus direct surveys. In this seminar I will describe how NSUM and indirect surveys have been used to track the prevalence of COVID-19 in several countries with the CoronaSurveys project (https://coronasurveys.org/). Then, I will present some analytical results and limitations of this technique. Finally, I will show how other aspects of society can be monitored with indirect surveys and NSUM.
28/11/2023 : 10h30 at salle REU 04.05 (LIS Luminy)

’‘Distributed search on graphs using discrete time quantum walk’‘
by Mathieu Roget, CANA, LIS

Searching with coined quantum walk is a problem that has interested the community since a long time. While most results consider spatial searches on regular lattices, some work have introduced several models of coined quantum walks on graphs. This work introduces a distributed searching quantum walk on graphs. Our contribution is in two parts: (i) we introduce a new mathematical model of a coined quantum walk on graphs designed to search both nodes or edges; (ii) we provide an anonymous distributed scheme to implement such a model. Lien : https://arxiv.org/abs/2310.10451.pdf
14/11/2023 : 10h30 at salle REU 04.05 (LIS Luminy)

’‘Distributed Computability with topological model : an extension to non-compact models’‘
by Yannis Coutouly, DALGO, LIS

Iterated Immediate Snapshot (IIS) is a shared memory model in a wait-free context that has a nice topological representation. The encoding of this distributed system uses simplicial complex for the uncertainty of a process, and chromatic subdivision as step of computation. This encoding is central in the Asynchronous Computability Theorem (ACT), which makes a connection between topological object and distributed computability. A generalization of this theorem is to apply it to submodel of IIS (sub-IIS). In this setting, the previously mentioned encoding can produce more complex topological space for some distributed system. In the case of non-compact model, the question was not solved. In this talk I aim to give you some understanding of the previously mentioned encoding, present a Generalized ACT (GACT) to sub-models of computation, and present a topology on the set of sub-IIS close to the Euclidian topology. The goal is to apply those results to get a characterization of the solvability of set-agreement in sub-IIS and provide an explicit algorithm.
17/10/2023 : 9h30 at salle REU 04.05 (LIS Luminy)

’‘Stationary and Deterministic Leader Election for Programmable Matter in the Presence of Obstacles’‘
by Maria Kokkou, DALGO, LIS

Programmable Matter refers to simple computational entities (here called particles) that are able to change their physical properties such as their shape, colour or texture in order to collaboratively accomplish a given task. In this talk, we consider the Leader Election problem which is often an intermediate step for the solution of more complex problems in the context of programmable matter. We consider the problem in the previously studied Amoebot model on a triangular grid, when the configuration is connected but contains obstacles (i.e., nodes the particles cannot move to) and holes (i.e., empty nodes, not occupied by particles or obstacles). We assume that particles only agree on one direction (i.e., the horizontal axis) but do not have chirality (i.e., they do not agree on the other two directions of the triangular grid). We prove that an election algorithm with explicit termination is not possible in this case, but we provide an implicitly terminating algorithm that elects a unique leader without requiring any movement. These results are in contrast to those in the more common model with chirality but no agreement on directions, where explicit termination is always possible but the number of elected leaders depends on the symmetry of the initial configuration. Solving the problem under the assumption of one common direction allows for a unique leader to be elected in a stationary and deterministic way, which until now was only possible under a sequential scheduler or assuming strongly connected configurations. In this talk, I will first show why an explicitly terminating leader election algorithm is not possible and then I will present our algorithm for deterministically electing a unique leader by stationary particles with constant memory. This is joint work with Jérémie Chalopin and Shantanu Das.
19/06/2023 : 11h00 at salle REU 04.05 (LIS Luminy)

’‘Belenios: a simple private and verifiable electronic voting system (part 3/3)’‘
by Arnaud Labourel, DALGO, LIS

Slides: PDF

In this talk, I will present Belenios which is an electronic voting system designed in 2012 by Véronique Cortier, Pierrick Gaudry and Stéphane Glondu from Inria. An implementation of this voting system is available under open source license. Belenios guarantees the vote privacy and full verifiability even against a compromised voting server. Each voter can check that her vote has been properly counted (this is the individual verifiability). Everyone can check that the result of the election corresponds to the ballots on the public bulletin board (universal verifiability) and that ballots comes from legitimate voters (eligibility verifiability). In order to guarantee all those properties, the authors of Belenios use severalf cryptographic tools: partially homomorphic asymmetric El Gamal encryption, Schnorr signatures, zero-knowledge proofs, cryptographic hash functions, … During the talk, I will explain how all these tools are combined to produce a verifiable and secure voting protocol.
31/05/2023 : 10h00 at salle REU 04.05 (LIS Luminy)

’‘Belenios: a simple private and verifiable electronic voting system (part 2/3)’‘
by Arnaud Labourel, DALGO, LIS

Slides: PDF

In this talk, I will present Belenios which is an electronic voting system designed in 2012 by Véronique Cortier, Pierrick Gaudry and Stéphane Glondu from Inria. An implementation of this voting system is available under open source license. Belenios guarantees the vote privacy and full verifiability even against a compromised voting server. Each voter can check that her vote has been properly counted (this is the individual verifiability). Everyone can check that the result of the election corresponds to the ballots on the public bulletin board (universal verifiability) and that ballots comes from legitimate voters (eligibility verifiability). In order to guarantee all those properties, the authors of Belenios use severalf cryptographic tools: partially homomorphic asymmetric El Gamal encryption, Schnorr signatures, zero-knowledge proofs, cryptographic hash functions, … During the talk, I will explain how all these tools are combined to produce a verifiable and secure voting protocol.
24/05/2023 : 10h00 at salle REU 04.05 (LIS Luminy)

’‘Belenios: a simple private and verifiable electronic voting system (part 1/3)’‘
by Arnaud Labourel, DALGO, LIS

Slides: PDF

In this talk, I will present Belenios which is an electronic voting system designed in 2012 by Véronique Cortier, Pierrick Gaudry and Stéphane Glondu from Inria. An implementation of this voting system is available under open source license. Belenios guarantees the vote privacy and full verifiability even against a compromised voting server. Each voter can check that her vote has been properly counted (this is the individual verifiability). Everyone can check that the result of the election corresponds to the ballots on the public bulletin board (universal verifiability) and that ballots comes from legitimate voters (eligibility verifiability). In order to guarantee all those properties, the authors of Belenios use severalf cryptographic tools: partially homomorphic asymmetric El Gamal encryption, Schnorr signatures, zero-knowledge proofs, cryptographic hash functions, … During the talk, I will explain how all these tools are combined to produce a verifiable and secure voting protocol.
04/05/2023 : 14h00 at salle REU 04.03 (LIS Luminy)

’‘Semi-simplicial set models for distributed knowledge (and beyond)’‘
by Roman Kniazev, LIX École Polytechique

In this talk, I will present an approach to the semantics of multi-agent epistemic logic based on simplicial sets. Contrary to simplicial complexes, simplicial sets allow for several simplices to exist for the same set of vertices. This allows us to express semantically situations when the knowledge of a group is greater than the sum of the knowledge of individual agents. I will discuss the link with simplicial complexes and completeness results. Finally, I will discuss further generalization based on hypergraphs, time permitting. This talk is based on joint work with Eric Goubault, Jérémy Ledent, and Sergio Rajsbaum (available at https://arxiv.org/abs/2303.14976).
03/05/2023 : 10h00 at salle REU 04.05 (LIS Luminy)

’‘Distributed Decision Problems: Concurrent Specifications beyond Binary Relations’‘
by Sergio Rajsbaum, Instituto de Matematicas, Universidad Nacional Autonoma de Mexico (UNAM)

Much discussion exists about what is computation, but less about what is a computational problem. In the sequential setting, Turing’s definition of computational problem was based on functions. In a concurrent setting, various notions of distributed problems have been used, under different models of computation, ranging from models equivalent to a Turing machine, to models where much heated discussion has taken place about whether interactive computation is fundamentally different from sequential computing. Often distributed problems for non-terminating interaction are considered. It is argued here that there is no need to go all the way to non-terminating computation, to appreciate how different distributed computation is from sequential computation. In a \{\em decision problem}\ each process of a distributed system starts with an initial private input value, and after communicating with other processes in the system, produces a local output value. An input/output relation is needed, to specify which output values are legal for a particular assignment of input values to the processes. An overview is provided of some results that show how rich the topic of distributed decision problems can be, when asynchronous processes can fail. We are in a world very different from that of the functions of sequential computation; moving away from graphs representing binary relations, to the world of simplicial complexes.
29/03/2023 : 09h30 at salle REU 04.03 (LIS Luminy)

’‘Space optimal self-stabilizing token circulation algorithm’‘
by 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. In particular, with the development of networks of connected, autonomous devices, it 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. We will present a particularly efficient algorithm in terms of memory for one fundamental problem in distributed systems: the token circulation.
08/02/2023 : 9h30 at salle REU 04.05 (LIS Luminy)

’‘Recoverable Data Structures in Settings with Non-Volatile Main Memory’‘
by Panagiota Fatourou, Professor at the Department of Computer Science of the University of Crete

This talk will present generic approaches for deriving recoverable synchronization algorithms, as well as recoverable implementations of widely-used concurrent data structures on top of them. Such implementations are appealing for emerging systems featuring byte-addressable non-volatile main memory (NVMM), whose persistence allows to efficiently resurrect failed processes after crashes. Recovery ensures that after a crash, every executed operation is able to recover and return a correct response, and that the state of the data structure is not corrupted.
18/01/2023 : 10h40 at amphi 12, bâtiment B, Luminy

’‘Leader election in blockchains’‘
by Sara Tucci Piergiovanni, CEA LIST Paris

Leader election is a fundamental problem in distributed systems, where a set of distributed nodes must elect one of them as leader to carry out some specific task. This old problem has recently found renewed interest in the context of blockchains. A blockchain is a chain of blocks containing user transactions held collectively by a set of miners. Among the available miners only those who solve a computational challenge, called proof-of-work, have the right to add a new block to the blockchain. Indeed, the proof-of-work mechanism can be seen as a leader election mechanism to designate who will add the next block. Interestingly, thanks to the proof-of-work, the election is unpredictable, random and fair: a miner has more chances of being elected in proportion to his computing power. More recently, due to the enormous energy consumption of proof-of-work, a new class of blockchain has emerged based on proof-of-stake, where the stake is an amount of money invested in the blockchain. In these blockchains, the leaders are chosen from those who have invested the most. The move to proof-of-stake, however, poses new challenges to mimic the security properties offered by proof-of-work, so that finding a good leader election method for proof-of-stake blockchains is still subject of active research. In this talk I will introduce the problem of leader election for blockchains, highlighting the differences with the classic leader election in distributed systems. I will present recent work on secure leader election for proof-of-stake blockchains focusing on methods to achieve unpredictability and secrecy such as verifiable random functions and homomorphic encryption.
18/01/2023 : 9h30 at amphi 12, bâtiment B, Luminy

’‘Blockchain vs State Machine Replication’‘
by Antonella Del Pozzo, CEA LIST Paris

In this seminar we first recall what is BFT-Consensus and the role it plays in two similar abstractions, the BFT-Consensus based Blockchain and the State Machine Replication (SMR). Even if those might seem very similar, they are not. Indeed, Blockchain do not guarantee any liveness in serving users requests. Hereafter we discuss under which conditions a Blockchain is also a SMR and if not, how to transform a BFT-Consensus based Blockchain into a SMR.
30/11/2022 : 10h at salle 04.03 (LIS Luminy)

’‘Deterministic leader election in the Ameobot model of programmable matter’‘
by Shantanu Das, DALGO, LIS

Continuing with the last presentation on Programmable Matter by Maria Kokkou, I will talk about deterministic leader election in the Ameobot model of programmable matter - where particles (modeled as finite state automata) are located in a hexagonal grid (represented by a triangular lattice) and they can move from cell to cell using a sequence of contractions and expansions. Starting from an existing deterministic algorithm for election, we show how to remove some of the strong assumptions in the original model, to obtain a weaker and more realistic model for programmable matter. In particular, in our model, the particles can achieve leader election without any synchronization mechanisms and no explicit communication between particles. The algorithm performs leader election in O(n) rounds starting from any simply connected configuration. When the initial configuration admits holes, it is impossible to achieve leader election while preserving connectivity - in this case we show how to achieve compaction of the holes and simultaneously achieve leader election, if we empower the particles with an additional capability called exterior awareness. (Joint work with G. D’ANGELO, M. D’EMIDIO, A. NAVARRA, AND G. PRENCIPE)
19/10/2022 : 10h at salle 04.03 (LIS Luminy)

’‘Introduction to Programmable Matter’‘
by Maria Kokkou, DALGO, LIS

The concept of programmable matter is to develop intelligent objects that are able to collaboratively change their form in order to complete tasks based on the perception of their surroundings. Those objects, called particles, are given a global task, have local information and the goal is to organise so that the task is either accomplished or proven to be impossible. From a computer science perspective, multiple models have been proposed in which programmable matter is conceptualised as numerous tiny robots that are able to move and compute. In this talk, we briefly discuss some of those models and concentrate on one of the more popular models, called the Amoebot model. We focus on algorithmic primitives and well-known problems. The algorithmic primitives we discuss are Leader Election and Spanning Forest Construction and generally refer to procedures that are commonly used as part of solving more complicated problems. Then we consider known distributed algorithms about two of those problems called Shape Formation and Coating.
13/09/2022 : 14h at visio-conférence

’‘Byzantine Auditable Atomic Register with Optimal Resilience’‘
by Alexandre Rapetti, CEA LIST Paris

An auditable register extends the classical register with an audit operation that returns information on the read operations performed on the register. In this paper, we study Byzantine resilient auditable registers implementations in an asynchronous message-passing system. Existing solutions implement the auditable register on top of at least 4f+1 servers, where at most f can be Byzantine. We show that 4f+1 servers are necessary to implement auditability without communication between servers. Then, we pursue the study by relaxing the constraint on the servers communication, letting them interact with each other. In this setting, we prove that 3f+1 servers are sufficient. This result establishes that with communication between servers, auditability does not come with an additional cost in terms of the number of servers.
17/06/2022 : 11h00 at salle REU 04.05 (LIS Luminy)

’‘Using Linearizable Objects in Randomized Concurrent Programs’‘
by Jennifer L. Welch, Texas A&M University, USA

Leader election is a fundamental problem in distributed systems, where a set of distributed nodes must elect one of them as leader to carry out some specific task. This old problem has recently found renewed interest in the context of blockchains. A blockchain is a chain of blocks containing user transactions held collectively by a set of miners. Among the available miners only those who solve a computational challenge, called proof-of-work, have the right to add a new block to the blockchain. Indeed, the proof-of-work mechanism can be seen as a leader election mechanism to designate who will add the next block. Interestingly, thanks to the proof-of-work, the election is unpredictable, random and fair, a miner has more chances of being elected in proportion to his computing power. More recently, due to the enormous energy consumption of proof-of-work, a new class of blockchain has emerged based on proof-of-stake, where the stake is an amount of money invested in the blockchain. In these blockchains, the leaders are chosen from those who have invested the most. The move to proof-of-stake, however, poses new challenges to mimic the security properties offered by proof-of-work, so that finding a good leader election method for proof-of-stake blockchains is still subject of active research. In this talk I will introduce the problem of leader election for blockchains, highlighting the differences with the classic leader election in distributed systems. I will present recent work on secure leader election for proof-of-stake blockchains focusing on methods to achieve unpredictability and secrecy such as verifiable random functions and homomorphic encryption.
31/05/2022 : 10h30 at salle 04.03 (LIS Luminy)

’‘Universal Graphs for Bounded Pathwidth Graphs’‘
by Arnaud Labourel, DALGO, LIS

In this talk, I will give an explicit construction of a graph $U_n$ with at most 8n vertices with the property that every n-vertex caterpillar graph is isomorphic to some induced-subgraph of $U_n$. Previous constructions of so-called induced-universal graph for caterpillars used 256n vertices in the best (Bonichon et al. SIROCCO’06 and Alstrup et al. FOCS’15). I will also give a generalization of this result to path-width-p graphs with an induced-universal graph of $n.2^{O(p)}$ vertices. The extended result is obtained from an algorithmic approach by designing an adjacency labeling scheme for these graphs using $\log(n) + O(p)$ bit vertex labels and with a constant time adjacency test.
26/04/2022 : 14h00 at salle 04.03 (LIS Luminy)

’‘Distributed Algorithms through the Lens of Algebraic Topology’‘
by Emmanuel Godard, DALGO, LIS

The goal of the talk is to discuss the situation regarding the use of Algebraic Topology tools in Distributed Computing. We will start by a quick reminder of the basic techniques then we present a series of three recent techniques that have advanced the use of such tools : graphical subdivisions, geometrization and pseudo-distances induced topology.
22/03/2022 : 14h00 at salle 04.03 (LIS Luminy)

’‘Crime and Punishment in Distributed Systems’‘
by Pierre Civit, LIP6, Sorbonne Université

Consider a non-synchronous distributed protocol whose n processes ensure both safety and liveness properties despite t arbitrary (Byzantine) failures. Unfortunately, it always exists a bound $t_0$ s. t. such distributed protocols cannot ensure (i) safety and liveness as long as $t \leq t_0$ and (ii) only safety when $t>t_0$. By contrast, only recently did the community discover that some of these distributed protocols can be made \emph{accountable} by ensuring that correct processes irrevocably detect at least $t_0 + 1$ faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity. In this paper, we propose a generic transformation, called \tau_{src}, of any distributed protocol into its accountable version. To this end, we first demonstrate that accountability in non-synchronous distributed protocols implies the ability to detect \emph{commission faults}. Specifically, we show that (1) detections \emph{not} based on committed commission faults can be wrong (i.e., false positives''), and (2) (luckily!) whenever safety is violated,enough’’ processes have committed commission faults. Then, we illustrate why some of these faults, called \emph{equivocation faults}, are easier to detect than some others, called \emph{evasion faults}, thus concluding that equivocation faults are preferable causes of safety violations.Finally, we observe that the approach exploited by the well-studied simulation of crash failures on top of Byzantine ones can be slightly modified in order to ensure that the safety of a protocol could \emph{only} be violated due to equivocation faults. Hence, we base the \tau_{src} transformation on the aforementioned approach. Our transformation increases the communication and message complexities of the original distributed protocol by a quadratic multiplicative factor.
22/02/2022 : 14h00 at salle 04.02 (LIS Luminy)

’‘Causal total order broadcast algorithms with bounded message size for dynamic systems’‘
by Colette Johnen, LaBRI et Université de Bordeaux

We consider a synchronous system with fixed constant number N of processes communicating through a dynamic network that ensures recurrent connectivity. These systems are model with a class of Time Varying Graph formalism. Initially, processes only know the number of processes N in the system and their own identifier. The processes discover the membership of the system during the executing the algorithm. Due to the dynamics of the network links, messages can be lost.
01/02/2022 : 14h00 at Zoom

’‘Local certification of graph classes’‘
by Laurent Feuilloley, LIRIS, Université de Lyon 1

Many distributed graph algorithms have been designed for specific graph classes, such as regular or planar graphs. In some cases, e.g. regular graphs, the nodes of the network can check locally that the network indeed has the right structure, before running the algorithm. Unfortunately, in some cases, e.g. planar graphs, it is not possible to locally check the structure, and this can be problematic. In this talk, I will review the recent results on the local certification of graph classes, which consists in certifying that the network belongs to a given class, using short labels on the nodes, and a local verification.
02/12/2021: 14h00 at TPR2/04.03 (Luminy)

’‘Scheduling and Graph Exploration with deadlines’‘
by Euripides Markou, University of Thessaly (Greece)

Consider a graph with weights on its edges and nodes. A node weight represents a deadline for this node and an edge weight represents the time a robot needs to traverse this edge. A robot needs to visit each node of the graph before its deadline. Can we decide within polynomial time whether such a `successful’ exploration can be achieved? We survey this area of research focusing on a clique topology where each node must be visited not just once but periodically and the maximum allowed time-period between any two consecutive visits of the same node should not exceed its deadline. This case has been introduced as a scheduling problem known as ‘Pinwheel’ and quite a few questions remain open for more than 30 years. We compare the computational complexity of this case with the complexity of the case where each node must be visited at least once before its deadline (and not periodically). The above exploration-scheduling problems find applications in diverse areas like mobile monitoring and facility service and maintenance but even digital-signal processing.
13/07/2021: 14h-15h

’‘All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier’‘
by Przemysław Uznański (University of Wrocław, Pologne)

Let G=(V,E) be an n-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices u and v is a common ancestor w of u and v such that no descendant of w has the same property. In this paper, we consider the problem of computing an LCA, if any, for all pairs of vertices in a DAG. The fastest known algorithms for this problem exploit fast matrix multiplication subroutines and have running times ranging from O(n^2.687) [Bender et al. SODA’01] down to O(n^2.615) [Kowaluk and Lingas ICALP’05] and O(n^2.569) [Czumaj et al. TCS’07]. Somewhat surprisingly, all those bounds would still be Ω(n^2.5) even if matrix multiplication could be solved optimally (i.e., ω=2). This appears to be an inherent barrier for all the currently known approaches, which raises the natural question on whether one could break through the O(n^2.5) barrier for this problem. In this paper, we answer this question affirmatively: in particular, we present an Õ(n^2.447) (Õ(n^7/3) for ω=2) algorithm for finding an LCA for all pairs of vertices in a DAG, which represents the first improvement on the running times for this problem in the last 13 years. A key tool in our approach is a fast algorithm to partition the vertex set of the transitive closure of G into a collection of O(ℓ) chains and O(n/ℓ) antichains, for a given parameter ℓ. As usual, a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a candidate LCA among the chain and antichain vertices, separately. The first set is obtained via a reduction to min-max matrix multiplication. The computation of the second set can be reduced to Boolean matrix multiplication similarly to previous results on this problem. We finally combine the two solutions together in a careful (non-obvious) manner. (Joint work with F. Grandoni, G. F. Italiano, A. Łukasiewicz and N. Parotsidis)
08/06/2021: 14h-15h

’‘From Bezout’s Identity to Space-Optimal Election in Anonymous Memory Systems’‘
by Damien Imbs (LIS)

An anonymous shared memory REG can be seen as an array of atomic registers such that there is no a priori agreement among the processes on the names of the registers. As an example a very same physical register can be known as REG[x] by a process p and as REG[y] (where y ≠ x) by another process q. Moreover, the register known as REG[a] by a process p and the register known as REG[b] by a process q can be the same physical register. It is assumed that each process has a unique identifier that can only be compared for equality. This talk will address the d-election problem, in which it is required to elect at least one and at most d leaders, in such an anonymous shared memory system. The 1-election problem is the familiar leader election problem. Let n be the number of processes and m the size of the anonymous memory (number of atomic registers). We will see why the condition gcd(m,n) ≤ d is necessary and sufficient for solving the d-election problem, where communication is through read/write or read/modify/write registers. The algorithm used to prove the sufficient condition relies on Bezout’s Identity - a Diophantine equation relating numbers according to their Greatest Common Divisor. Furthermore, in the process of proving the sufficient condition, we will see how 1-leader election can be solved using only a single read/write register (which refutes a 1989 conjecture stating that three non-anonymous registers are necessary), and that the exact d-election problem, where exactly d leaders must be elected, can be solved if and only if gcd(m,n) divides d.
25/05/2021: 14h-15h

’‘Algorithme presque optimal pour la chasse au trésor dans les graphes arbitraires’‘
by Arnaud Labourel (LIS)

Nous allons considérer dans cet exposé un agent mobile navigant dans un graphe qui doit trouver une cible inerte (appelé trésor) cachée dans l’un des nœuds. L’agent n’a aucune connaissance a priori du graphe, de la localisation du trésor ou de la distance initiale par rapport à celui-ci. Le coût d’un algorithme de chasse au trésor est le nombre de déplacements effectuées par l’agent jusqu’à ce qu’il trouve le trésor dans le pire des cas. Afin d’analyser le coût d’algorithme de chasse au trésor, on définit e(d) comme étant le nombre d’arêtes dont au moins une extrémité est à une distance inférieure à d de la position de départ de l’agent. Il est possible de montrer que tout algorithme de chasse au trésor a un coût en Ω(e(d)). Awerbuch, Betke, Rivest et Singh dans un papier de 1999 ont même conjecturé qu’il était impossible de trouver un trésor caché à une distance au plus d à un coût presque linéaire en e(d). Nous réfutons cette conjecture en donnant un algorithme de chasse au trésor déterministe ayant un coût en O(e(d) log d). Article en collaboration avec Sébastien Bouchard (LaBRI, Université de Bordeaux), Yoann Dieudonné (MIS Lab., Université de Picardie Jules Verne) et Andrzej Pelc (Département d’informatique, Université du Québec en Outaouais) accepté à ICALP 2021.
13/04/2021 : 14h-15h

’‘Long-Lived Shared Objects with Polylogarithmic Amortized Step Complexity.’‘
by Alessia Milani (LaBRI, Université de Bordeaux)

Shared data objects are an essential abstraction in distributed computing, as they provide a consistent interface for multiple processes to interact via shared data. Linearizability is the main consistency criterion that formalizes the correctness of shared object implementations. Roughly speaking, it requires each concurrent execution on the shared object to be equivalent in some sense to a sequential one. This makes linearizable shared objects intuitive to use, but they can be expensive to implement. In 2000, 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 shared objects. In 2012, Aspnes, Attiya and Censor-Hillel 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. Previous results apply to two widely-used shared objects, the counter and the snapshot, but leave open the question of whether there exists deterministic algorithms with sub-linear amortized step complexity for these objects. We recently answer this question in the affirmative. In particular, for each of these objects we present the first wait-free read/write implementation whose amortized step complexity is polylogarithmic in all executions (i.e.; regardless of how many operations are performed on the object). In this talk, I will present the results on the counter. The talk will be self-contained. (This is a joint work with Mirza Ahad Baig, Danny Hendler and Corentin Travers)
16/03/2021: 14h-15h

’‘Self-stabilizing Systems in Spite of High Dynamics’‘
by Stéphane Devismes (VERIMAG, Université Grenoble Alpes)

A self-stabilizing distributed system, regardless its initial configuration, converges within finite time to a configuration from which its behavior is correct. By essence, self-stabilization is a non-masking fault tolerant approach since the arbitrary initial configuration can be seen as the result of arbitrary transient faults. In this talk, we will consider self-stabilization in highly dynamic networks, i.e., networks suffering from unexpected and frequent topological changes. Precisely, assuming that nodes are uniquely identified, we study the self-stabilizing leader election problem in three important classes of dynamic networks to obtain solutions tolerating both transient faults (such as memory corruption) and frequent topological changes. We first study conditions under which our problem can be solved and then propose several algorithms. Our results reveal that the assumption on the knowledge of the number N of processes is central. Indeed, we show that, as soon as there is no strong guarantees on the temporal connectivity in the network, the knowledge of the exact value of N is required. Finally, the convergence time of self-stabilizing leader election cannot be bounded in some important cases. In those cases, we show that our solutions are speculative since their convergence time can be still bounded in a subset of more probable executions.
23/06/2020

’‘Schéma de distance pour les graphes pontés sans clique de taille 4’‘
by Arnaud Labourel (DALGO, LIS)

Pour cet exposé, je vous présenterai un schéma de distance approximée pour la famille des graphes pontés n’ayant pas de clique de taille 4 en tant que sous-graphe induit. Un schéma de distance approximée sur une famille de graphes consiste en une fonction d’encodage qui attribue une étiquette binaire à chaque sommet d’un graphe G, et en une fonction de décodage qui retourne une approximation de la distance (dans notre cas entre une fois et quatre fois la distance) dans le graphe G entre deux sommets u et v en utilisant seulement leurs étiquettes, et donc sans connaissance supplémentaire sur le graphe. Les graphes pontés (bridged en anglais) sont les graphes qui n’admettent pas de cycle isométrique de plus de trois sommets et nous considérerons dans cet exposé la sous-famille de ces graphes qui ne contiennent pas de clique de taille 4. Je vous montrerai comment il est possible de s’appuyer sur les propriétés métriques de ces graphes pour concevoir un tel schéma. C’est un travail effectué en collaboration avec Victor Chepoi et Sébastien Ratel.
22/11/2019 : 10h30 at salle de réunion du LIS, Luminy (Préfabriqué)

’‘Schémas de compression pour les classes maximums et amples.’‘
by Jérémie Chalopin (DALGO, LIS)

Dans cet exposé, je parlerai des connections qui existent entre des questions venant de la théorie de l’apprentissage et des concepts étudiés en géométrie et en théorie métrique des graphes. Après avoir expliqué tous les mots du titre de l’exposé, je présenterai un contre-exemple issu de la géométrie qui montre que les constructions existantes de schémas de compressions pour les classes maximums sont erronées. Je présenterai ensuite une preuve de l’existence de ces schémas de compression pour les classes maximums ainsi que des pistes pour pouvoir généraliser ce résultat aux classes amples. (Travail réalisé avec V. Chepoi, S. Moran et M. K. Warmuth. https://arxiv.org/abs/1812.02099 )
25/10/2019 : 10h30 at salle de réunion du LIS, Luminy (Préfabriqué)

’‘Livraison collaborative avec des agents mobiles contraints en énergie.’‘
by Arnaud Labourel (DALGO)

Dans cet exposé je vous parlerai du problème de livraison collaborative avec des agents mobiles. On considère un graphe pondéré (orienté ou non) dans lequel se trouve des agents mobiles initialement dispersés. L’objectif des agents est de transporter un colis d’un sommet source à un sommet destination. Chaque agent a un montant d’énergie limité lui permettant de parcourir une trajectoire de longueur au plus B. Les agents doivent donc collaborer car aucun n’a assez d’énergie pour transporter seul le colis de la source à la destination. Ce problème avait déjà été étudié mais nous ajoutons une contrainte supplémentaire qui est que les agents doivent utiliser uniquement un chemin prédéfini pour transporter le colis. Cette contrainte peut se justifier par des raisons de sécurité, en considérant qu’un seul chemin est sûr dans le réseau pour transporter le colis. Bien que cette contrainte réduise l’espace de recherche des solutions réalisables, le problème reste difficile à résoudre tout comme l’est le problème initial. Je vous montrerai des algorithmes d’approximation (pour le montant d’énergie B des agents) en temps polynomial pour les graphes orientés et non orientés, et vous donnerai une preuve de NP-dureté pour l’approximation dans le cas orienté. (Travail en collaboration avec Jérémie Chalopin, Shantanu Das, Yann Disser et Matúš Mihalák)
27/09/2019 : 10h30 at salle de réunion du LIS, Luminy (Préfabriqué)

’‘Ce que vos parents ont dit de ne pas faire dans un protocole sans fil’‘
by Cédric Berenger and Peter Niebert (DALGO)

Nous présentons deux travaux en cours dans le domaine des protocoles sans fil qui ont en commun d’exploiter des transgressions de l’usage habituel de la couche physique. Pour comprendre ces travaux, nous introduisons d’abord le côté physique de la couche MAC de Bluetooth Low Energy, puis nous montrons, démonstration à l’appui, comment certains détournements de cette couche physique ouvrent des possibilités inattendues dans la conception de protocoles sans fil.
13/09/2019 : 10h30 at salle de réunion du LIS, Luminy (Préfabriqué)

’‘Overcoming Interference in the Beeping Model - Deterministic Optimal Leader Election’‘
by Fabien Dufoulon (LRI, Paris)

Small inexpensive inter-communicating electronic devices have become widely available. Although the individual device has severely limited capabilities (e.g., basic communication, constant-size memory or limited mobility), multitudes of such weak devices communicating together are able to form low-cost, easily deployable, yet highly performant networks. Such distributed systems present significant challenges however when it comes to the design of efficient, scalable and simple algorithms. In this presentation, we will focus on such systems, composed of devices with severely limited communication capabilities - using only simple bursts of energy. These distributed systems may be modeled using the beeping model, in which nodes communicate by beeping or listening to their neighbors (according to some undirected communication graph). This model was recently introduced (Cornejo and Kuhn, 2010), raising several question about the impact of beeping communication on fundamental problems, such as leader election, vertex coloring or multi-broadcast. Focusing on the leader election problem, we present the first deterministic optimal leader election beeping algorithm, which requires nodes to have unique identifiers. We also present a randomized version of this solution, working with anonymous nodes. This randomized solution is the first optimal randomized leader election beeping algorithm.
29/05/2019

’‘A Framework for Searching in Graphs in the Presence of Errors’‘
by Dariusz Dereniowski (Gdansk University of Technology, Pologne)

We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh- Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability p < 1/2 and a correct one with probability 1 - p).We study this problem both with adversarial errors and independent noise models. First, we show an algorithm that needs at most (log n)/(1-H(r)) queries in case of adversarial errors, where the adversary is bounded with its rate of errors by a known constant r < 1/2. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking an amortization argument. We then show that our algorithm coupled with a Chernoff bound argument leads to a simpler algorithm for the independent noise model and has a query complexity that is both simpler and asymptotically better than the one of Emamjomeh-Zadeh et al. [STOC 2016]. Our approach has a wide range of applications. First, it improves and simplifies the Robust Interactive Learning framework proposed by Emamjomeh-Zadeh and Kempe [NIPS 2017]. Secondly, performing analogous analysis for edge-queries (where a query to an edge e returns its endpoint that is closer to the target) we actually recover (as a special case) a noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon an algorithm for searching of unbounded domains due to Aslam and Dhagat [STOC 1991]. (Joint work with S. Tiegel, P. Uznanski and D. Wolleb-Graf)
26/04/2019 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Patrolling on Dynamic Ring Networks’‘
by Shantanu Das (DALGO, LIS)

We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every I(n) time units, with the objective of minimizing the idle time I(n). While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for k = 2 or k > 2 agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs. (Note: Joint work with Giuseppe. A. Diluna and Leszek A. Gasieniec.)
15/02/2019

’‘Distributed Algorithms meet Computer-Aided Verification’‘
by Josef Widder (TU Wien)

I will review some of my earlier results on work and time complexity of link-reversal routing algorithms, which were introduced by Gafni and Bertsekas in 1981. The theory we developed for the complexity analysis of these algorithms allowed us also to prove that executions of link reversal algorithms on large graphs are similar (a notion which we make precise) to executions on smaller graphs. The latter result has an interesting application to parameterized model checking of a link-reversal-based resource allocation scheme. In particular, we show cases where verification of large systems can be reduced to checking smaller ones. The observation that distributed algorithm theory has interesting application in computer-aided verification motivated me to explore this connection in more depth. In the second part of the talk, I will present a line of research that in the recent years led to breakthroughs in parameterized model checking of fault-tolerant broadcasting algorithms. I will close the talk by discussing ongoing research lines and open challenges. The results on link reversal is joint work with Bernadette Charron-Bost, Matthias Fuegger, Antoine Gaillard, and Jennifer Welch. Parameterized model checking of broadcasting algorithms is joint work with Igor Konnov, Marijana Lazic, and Helmut Veith.
14/12/2018 : 10h30

’‘Approximate Agreement in Dynamic Networks’‘
by Thomas Nowak (LRI, Paris)

Agreeing on a common value in a distributed system is a problem that lies at the heart of many distributed computing problems and occurs in several flavors. Unfortunately, even modest network dynamics already prohibit solvability of exact consensus, where agents have to decide on a single output value that is within the range of the agents’ initial values. For many problems (distributed control, clock synchronization, load balancing, …) it is however sufficient to asymptotically converge to the same value, or decide on values not too far from each other. We study solvability of these consensus variants in highly dynamic networks, provide time complexity results, and present fast algorithms. We then show how the results on dynamic networks are relevant for classical fault-models, such as asynchronous message passing with crashes. The talk is based on joint work with Bernadette Charron-Bost, Matthias Függer, and Manfred Schwarz.
26/11/2018 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Descriptive distributed complexity’‘
by Fabian Reiter (LSV, Université Paris-Saclay)

This talk connects two classical areas of theoretical computer science: descriptive complexity and distributed computing. The former is a branch of computational complexity theory that characterizes complexity classes in terms of equivalent logical formalisms. The latter studies algorithms that run in networks of interconnected processors. Although an active field of research since the late 1970s, distributed computing is still lacking the analogue of a complexity theory. One reason for this may be the large number of distinct models of distributed computation, which make it rather difficult to develop a unified formal framework. In my talk, I will outline how the descriptive approach, i.e., connections to logic, could be helpful in this regard.
26/10/2018 at salle de réunion du LIS, Luminy (Préfabriqué)

’‘k-enveloppe convexe asymptotique et problèmes associés dans les adversaires de messages’‘
by Eloi Perdereau (Doctorant, DALGO)

On considère le problème de l’accord “k-enveloppe convexe” asymptotique dans des systèmes distribués à passage de message. Pour résoudre ce problème, les agents (ayant pour valeurs un point dans R^d) doivent converger vers un polytope ayant au plus k sommets. Ce problème est une extension du consensus asymptotique qui a beaucoup été étudié en calcul distribué, mais également en théorie du contrôle. C’est également une variante de l’accord k-ensembliste (k-set agreement) dans laquelle la terminaison exacte est remplacée par une convergence. Dans cet exposé, je présenterai notre résultat de caractérisation de la solvabilité de l’accord “k-enveloppe convexe” asymptotique dans des adversaires de messages clos par suffixes. J’expliquerai l’intuition de preuves ainsi que la difficulté de ce genre de problème et l’importance de la terminaison. Pour cela, je vous présenterai un contre-exemple montrant qu’il n’est pas évident de résoudre la version approchée du problème lorsque k > 1 avec des algorithmes d’approximation.
29/06/2018 at Salle des commissions, Batiment TPR2, 1er étage (Luminy)

’‘Towards the blockchain formalization: the blockchain abstract data type’‘
by Antonella Del Pozzo (Researcher, CEA LIST, Paris)

Blockchains became a game changer in the distributed storage area due to their ability to mimic the functioning of a classical traditional ledger such as transparency and falsification proof in an untrusted environment. However, blockchain integration in industrial applications strongly depends on the formal guaranties of the quality of services provided, especially in terms of consistency. In this presentation we formalize the blockchain as a composition of abstract data types which helps us to define a hierarchy of consistency criteria that formally characterizes different typologies of blockchains. Moreover, we present some results on implementability and a mapping of representative existing blockchains from both academia and industry against the defined consistency criteria. Finally, we present two examples of Blockchain usage in the industrial context.
05/06/2018 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Anonymity in Distributed Read/Write Systems: a Short Problem-Based Introduction’‘
by Michel Raynal (Professeur, IRISA, Université de Rennes, et Hong Kong Polytechnic University)

This talk will be an algorithmic introduction to anonymity in asynchronous systems where processes communicate by reading and writing atomic registers. Two types of anonymity will be investigated: process-anonymity and memory-anonymity. Process-anonymity is when the processes cannot be distinguished the ones from the others (among other features, they do not have identifiers). Memory-anonymity is when the same memory locations can have different names at different processes (e.g., the location name A used by process p and the location name B used by another process q can correspond to the very same memory location X, and similarly for the names B at p and A at q which correspond to the same memory location = X). The talk will show how algorithms can cope with the uncertainty created by these two types of anonymity. To this end, taking examples from the literature, it will present anonymity-tolerant implementations of several concurrent objects, such as snapshot, consensus, and lock, each implementation satisfying a well-defined progress condition (obstruction-freedom, non-blocking, or wait-freedom). This paper must be considered as a short example-driven introductory tutorial on anonymous asynchronous read/write systems.
01/06/2018 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Balanced connected partitioning of unweighted grid graphs’‘
by Cédric Berenger (Doctorant, DALGO)

We consider a partitioning problem for grid graphs with special constraints: a (square) grid graph as well as a number of colors is given, a solution is a coloring approximatively assigning the same number of vertices to each color and such that the induced subgraph for each color is connected. In a “rooted” variant, a vertex to be included in the coloring for each color is specified as well. This problem has a concrete motivation in multimedia streaming applications. We show that the general problem is NP-complete. On the other hand, we define a reasonable easy subclass of grid graphs for which solutions always exist and can be computed by a greedy algorithm.
24/04/2018 at salle BOCAL du Bibliotheque (premiere étage), Luminy

’‘Edge-fault-tolerant spanners for single-source short(est) paths’‘
by Guido Proietti (Università degli Studi dell’Aquila)

A fault-tolerant (communication) network is required to be sparse and fast, but also to remain effectively operational following the occasional failure of some of the network’s links or nodes. On a theoretical side, this asks for designing a sparse subgraph of a given graph, which preserves not only the connectivity between pairs of nodes of interest after some edges/vertices removal, but that also contains (almost) shortest paths between them. In the literature, such type of structures are known as fault-tolerant spanners. In this talk, I will review the state-of-the-art for spanners tolerating a single edge failure in one of the most popular network topology, namely the single-source shortest-path tree.
20/04/2018 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘The Synchronization Power of Atomic Bitwise Operations’‘
by Damien Imbs (MCF, DALGO)

Bitwise AND, OR and XOR operations are very widely used, but have received little attention in the distributed setting. Because bitwise operations are available in most modern processors, they can constitute a valuable tool for synchronization in distributed systems. It is then natural to consider the level of synchronization that these operations can achieve. A shared AND/OR register consists of an array of x bits and offers three atomic operations: AND and OR operations, which take an array of x bits as parameter and change the state of the register by applying the corresponding bitwise operation, and a read operation which returns the content of the array. A shared AND/OR/XOR register additionally offers a XOR operation. After introducing shared AND/OR and AND/OR/XOR registers, this talk will exhibit their synchronization power by determining their consensus number, that is, the maximum number of processes that can solve wait-free consensus using these objects.
09/03/2018 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Collaborative Delivery with Heterogeneous Agents’‘
by Shantanu Das (MCF, DALGO)

Collaborative delivery is the problem of delivering a package from a source node to target node in a graph using multiple mobile agents, each of which has limited energy resources which limits the distance each agent can move in the graph. The agents may start from different locations in the graph. The original version of the problem put hard fixed budgets on the distance moved by each agent and asks whether there exists a feasible solution. We instead study the problem for heterogeneous agents which have different rates of energy consumption. Our objective is to minimize the total energy consumption for collaborative delivery of multiple packages between designated source - target pairs. To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages). We show hardness results and approximation algorithms for each of these sub-tasks. Finally, we give a polynomial-time constant factor approximation algorithms for collaborative delivery under the condition that an agent can carry at most one package at a time.
02/02/2018 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Exploring Graphs with Time Constraints by Unreliable Mobile Robots’‘
by Arnaud Labourel (MCF, DALGO)

In this presentation, I will talk about exploration of a graph by a collection of unreliable mobile robots. The graph is weighted (edge weight = time needed to traverse the edge) and each node is assigned a deadline. The exploration is successful if each node of the graph is visited before its deadline by at least one reliable robot. I will concentrate on line graphs and rings and consider two cases for the starting positions of the robots: either there are given in the input of the problem or we can choose them. For collections involving only reliable robots, I will present a centralized algorithms finding optimal times needed for exploration for both cases. Then, I will show that solving the line exploration problem with robots at given positions is NP-hard when some number of robots may be unreliable. The same problem has polynomial solutions for a ring and for the case when the initial robots’ positions on the line are arbitrary. I will also show that the problem is NP-hard for star graphs, even when the team consists of only two reliable robots.
19/01/2018 at meeting room of LIF, (Prefabricated building) Luminy

’‘Population Protocols with Faulty Communications’‘
by Giuseppe Antonio Di Luna (Postdoc, DALGO)

Starting from the seminal paper of Angluin et al, the population protocol model sparked a lot of interest in the research community. In the original population protocol model a set of anonymous and constant state agents passively move inside some space. When two agents are close enough, they interact by exchanging states and each agent modifies its internal state using the information provided by the other, i.e. there is a two-way interaction. Despite the small power of a single agent, a swarm of such agents can compute non-trivial predicates. Many papers have been published investigating the computational power of this model. Surprisingly, really few works examined what happens when the original assumption of two-way interactions is dropped. In this talk we will look at this case. We assume that when two agent meet and exchange their states a failure may happen in which one of the state is corrupted, leading to an unexpected one-way interaction. We investigate several models of omissive interactions, according to the capabilities of agents to detect or not a failure, providing a complete hierarchy of faulty interactions models. Our final task is to simulate two-way interactions in such harsh environments. Unfortunately, our results show that simulating is much harder than expected and that, even when failures are detectable, the original model has to be extended with some additional power to overcome the presence of faulty communications. Therefore, we try to circumvent the aforementioned impossibility by using common assumptions: presence of a leader, known bound on failures, known system size. Giving two-way simulators for these cases.
01/12/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘Distributed Algorithms for Energy Constrained Mobile Agents’‘
by Christina Karousatou (PhD Student, DALGO)

In this thesis we study and design algorithms for solving various well-known problems for mobile agents moving on a graph, with the additional constraint of limited energy which restricts the movement of the agents. Each mobile agent is an entity, equipped with a battery, that can traverse the edges of the graph and visit the nodes of the graph, consuming a part of its energy for movement. In contrast to various well-studied models for mobile agents, very little research has been conducted for the model considering the energy limitations. We study the fundamental problems of graph exploration, gathering and collaborative delivery in this model.
24/11/2017

’‘Comment explorer un arbre inconnu avec des agents à énergie limitée’‘
by Jérémie Chalopin (DALGO)

On souhaite explorer un arbre inconnu avec un groupe d’agents mobiles initialement regroupés sur un sommet. Chaque agent dispose d’une énergie limitée et ne peut pas traverser plus de B arêtes. On souhaite maximiser le nombre de sommets visités (par au moins un agent). Initialement, les agents n’ont aucune connaissance sur la structure de l’arbre, mais ils en découvrent la topologie au fur et à mesure qu’ils traversent de nouvelles arêtes. Nous supposons que les agents peuvent communiquer entre eux à distance illimitée, donc la connaissance qu’un agent obtient lors de la traversée d’une arête est instantanément transmise aux autres agents. On propose un algorithme qui partitionne l’arbre en sous-arbres au cours de l’exploration et fait des compromis entre un parcours en largeur et un parcours en profondeur. On montre que notre algorithme est 3-compétitif par rapport à la solution optimale qu’on peut obtenir si on connaît initialement une carte de l’arbre. On montre également une borne inférieure non-triviale de 2.17 sur le ratio de compétitivité de tout algorithme d’exploration.
26/10/2017 at salle de réunion du LIF, Luminy (Préfabriqué) [changement possible]

’‘Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance’‘
by David Ilcinkas (CR, LaBRI, CNRS, Bordeaux)

We deal with the problem of maintaining a shortest-path tree rooted at some process $r$ in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at $r$ in its connected component, $V_r$, and make all processes of other components detecting that $r$ is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks under the distributed unfair daemon (the most general daemon) without requiring any /a priori /knowledge about global parameters of the network. This is the first algorithm for this problem that is proven to achieve a polynomial stabilization time in steps.
20/10/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘Impact of initial knowledge on calculability in distributed systems’‘
by Antoine Naudin (PhD Student, DALGO)

Dans cette thèse, nous étudions l’impact des connaissances sur la calculabilité distribuée de problèmes fondamentaux au sein des réseaux distribués. Dans un système distribué, les entités de calcul ne possèdent que des informations partielles et locales pour résoudre des tâches globales. Néanmoins, ces informations partielles ne permettent pas de résoudre toutes les tâches et, dans ce cas, il sera nécessaire de donner plus de connaissances (locales ou globales) aux entités. Dans une première partie, nous caractérisons les connaissances nécessaires et suffisantes permettant de résoudre des problèmes tels la cartographie, l’élection et la k-élection dans un modèle à passage de messages particulier: le modèle des participants inconnus. Ce modèle est une extension naturelle du modèle à passage de messages permettant de modéliser un certain dynamisme des réseaux. Nos preuves sont constructives et pour chacun des problèmes étudiés, une condition caractérisant les connaissances nécessaires et suffisantes est fournie et un algorithme utilisant toute connaissance satisfaisant notre condition est proposé (et montré correct). Nous étendons ensuite le modèle aux graphes anonymes et, avec la même méthodologie, nous présentons une condition nécessaire sur la connaissance à fournir aux processus pour résoudre le problème de l’élection et nous proposons un algorithme utilisant une telle connaissance et une borne sur la taille du réseau. Dans la seconde partie, nous étudions l’impact des connaissances locales sur la calculabilité du problème de l’exploration de graphes anonymes avec arrêt. Pour cela, nous introduisons un nouveau modèle d’agent mobile doté d’un capteur spécial, nommé jumelles, lui permettant de percevoir le graphe induit par les sommets adjacent à sa position dans le réseau. Dans ce modèle, nous caractérisons exactement les graphes explorables sans connaissance globale et nous proposons un algorithme les explorant. Cette connaissance locale apportée à un coût car la complexité de tout algorithme d’exploration pour ces graphes croît plus vite que toute fonction calculable. Pour finir cette étude, nous montrons que de larges familles de graphes peuvent être explorées en un nombre de mouvements linéaire en la taille du graphe exploré. Nous proposons un algorithme qui, grâce aux jumelles, explore efficacement les graphes de Weetman contenant, entres autres, les graphes triangulés, les graphes de Johnson et certaines triangulations planaires.
04/09/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘Collaborative delivery by energy-sharing low-power mobile robots’‘
by Christina Karousatou (DALGO, LIF)

We study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one unit and the robot can only perform such move initially having at least one unit of energy. There are two distinguished nodes s and t in the graph and the goal for the robots is to deliver the package initially present on s to the node t. The package can be passed from one robot to another when they are colocated. In the first problem we study, the robots are initially placed at some given nodes of the graph and the question is whether the delivery is feasible. We prove that this problem is NP-complete. In the second problem, the initial positions of the robots are not fixed but a subset of nodes H of the graph is given as input together with an integer k, and the question is as follows: is there a placement of k robots at nodes in H such that the delivery is possible? We prove that this problem can be solved in polynomial time.
30/06/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘On-line searching of partial grids’‘
by Dariusz Dereniowski (Gdańsk University of Technology, Poland)

Consider a team of mobile agents starts at some node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. We restrict our attention to networks that are embedded into partial grids: nodes are placed on the plane at integer coordinates and only nodes at distance one can be adjacent. We give an on-line algorithm for the searchers that provides a monotone connected search strategy that uses $O(\sqrt{n})$ searchers for any unknown partial grid, where $n$ is the number of nodes in the grid. As for lower bound, $\Omega(\sqrt{n}/\log n)$ is the best possible competitive ratio for such an algorithm.
16/06/2017 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Online exploration of weighted graphs’‘
by Euripides Markou (University of Thessaly, Greece)

We study the problem of exploring an unknown undirected graph with non-negative edge weights. Starting at a distinguished initial vertex s, an agent must visit every vertex of the graph and return to s. Upon visiting a node, the agent learns all incident edges, their weights and endpoints. The goal is to find a tour with minimal cost of traversed edges. This variant of the exploration problem has been introduced by Kalyanasundaram and Pruhs and is known as a fixed graph scenario. There have been recent advances by Megow, Mehlhorn, and Schweitzer, however the main question whether there exists a deterministic algorithm with constant competitive ratio (w.r.t. to offline algorithm knowing the graph) working on all graphs and with arbitrary edge weights remains open. In this paper we study this problem in the context of advice complexity, investigating the tradeoff between the amount of advice available to the deterministic agent, and the quality of the solution.
26/05/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘Maximal exploration of trees with energy-constrained agents’‘
by Christina Karousatou (PhD Student, LIF)

We wish to explore an unknown tree with a team of k >= 1 initially collocated mobile agents. Each agent has limited energy and cannot, as a result, traverse more than B edges. The goal is to maximize the number of nodes collectively visited by all agents during the execution.Initially, the agents have no knowledge about the structure of the tree, but they gradually discover the topology as they traverse new edges. We assume that the agents can communicate with each other at arbitrary distances, therefore the knowledge obtained by one agent after traversing an edge is instantaneously transmitted to the other agents.We propose an intuitive algorithm based on depth-first search and we study its performance compared to the optimal solution that we could obtain if we knew in advance the map of the tree. We prove that this algorithm has a constant competitive ratio. We also provide a lower bound on the competitive ratio of any algorithm.
12/05/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘On the computability power of message-based communication primitives’‘
by Damien Imbs (Postdoc, LIF)

In fault-tolerant distributed computing, computability is a core issue. A fundamental result is that, in an asynchronous system in which any number of processes can crash, and in which these processes communicate either by message-passing or through a shared memory, set agreement (agreeing on a strict subset of the input values) is impossible. Moreover, adding a black box that allows solving k-set agreement (agreeing on at most k < n different values) does not allow to solve (k-1)-set agreement. This impossibility result can be circumvented by using stronger communication primitives. A well-known message-based primitive is Total-Order broadcast, which delivers messages in the same order at every process. From a computability point of view, it is equivalent to a shared memory augmented with 1-set agreement (also called consensus). A recent result determined that SCD-Broadcast, a weaker message-based primitive, is equivalent to a shared memory and thus does not allow to solve set agreement. This talk will present the k-SCD-Broadcast message-based primitive that lies between these two extremes, and will show that it is equivalent to a shared memory augmented with k-set agreement.
14/04/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘Self-stabilizing Metric Graphs’‘
by Jonas Lefèvre (ATER, IRIF, Université Paris Diderot)

I will present a self-stabilizing algorithm for overlay networks that for an arbitrary given metric specified via a distance oracle constructs the graph representing that metric. The algorithm works under both an asynchronous and a synchronous daemon. In the synchronous case, the algorithm stabilizes O(n) rounds and is almost silent. The construction used to obtain this result may be useful for other problems.
07/04/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘The Power of Weaknesses, variations on Population and Community Protocols’‘
by Mikaël Rabie (ATER, LIP, ENS de Lyon)

Population Protocols is a model of computation over a finite set of agents. It corresponds to a model of devices with a weak memory interacting pairwisely to communicate and compute a global result. Restrictions over the interaction rules, and time consideration have been studied. In this thesis, we consider two new restrictions over the rules that brings a more rational behavior to agents: Pavlovian rules make a parallel with game theory and Trustful rules permit to add a coherence in terms of frequencies. Adding tools to population protocols agents have been studied. Giving unique identifiers corresponds to Community Protocols, adding Turing Machines corresponds to Passively Mobile Model. We provide time consideration to the first model, and then look at what happens when there can be Homonym agents. We fill a gap in the second model, depending on the computation space we provide to each agent.
05/04/2017 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Self-Oscillations and population protocols’‘
by Anissa Lamani (Postdoc, MIS, Université de Picardie Jules Verne)

Population protocols (PPs) have been introduced by Angluin et al. as a model of passive distributed systems in which a collection of finite-state mobile agents interact with each other in order to achieve a common task. Motivated by the well-known BZ reaction, we consider the problem of autonomously generating oscillatory executions from any initial configuration i.e., in a self-stabilizing manner. Under the deterministic scheduler, we show that the self-stabilizing leader election (SS-LE) problem and the self-stabilizing oscillation (SS-OSC) problem are equivalent, in the sense that an SS-OSC protocol is constructible from a given SS-LE protocol and vice versa, which unfortunately implies that (1) resorting to a leader is inevitable and (2) n states are necessary to create an oscillation of amplitude n, where n is the number of agents. Under the probabilistic scheduler, we consider a more general problem as follows: let N be the set of non-negative integers and f be a periodic non-negative integer functionf: N -> N with a period α, i.e., f(t + α) = f(t) for all t in N. We investigate the problem of designing a PP that realizes f starting from any arbitrary configuration.
31/03/2017 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Robustness in highly dynamic networks’‘
by Arnaud Casteigts (MCF, LaBRI, Université de Bordeaux)

We investigate a special case of hereditary property that we refer to as robustness, which corresponds to a property being inherited in all connected spanning subgraphs of the original graph. This definition has two interpretations; the first one relates to static networks in which some edges may fail permanently; the second, less evident but more significant, relates to highly dynamic networks of a very general type. In this paper, we focus on the maximal independent set problem (MIS). We characterize the graphs in which all MISs are robust and show that the distributed problem of finding one in this particular case is a local problem. This is done constructively, by presenting an algorithm that uses only information available within a sublogarithmic distance in the number of nodes n. On the negative side, we show that finding a robust MIS in general graphs is not local and may require information up to distance $\Omega(n)$ in some graphs, which implies a separation with classical MIS. This result also implies that any strategy is asymptotically (in order) as bad as collecting all the network information at one node and solving the problem in an offline manner. We present an algorithm that computes a robust MIS in a given graph, if one exists, and reject otherwise. Significantly, our algorithm has polynomial running time despite the fact that exponentially many MISs may exist, making it practical in both distributed and centralized settings.
17/03/2017 at salle de réunion du LIF, Luminy (Préfabriqué)

’‘Distributed Evacuation in Graphs with Multiple Exits’‘
by Shantanu Das (MCF, DALGO)

We consider the problem of efficient evacuation using multiple exits. We formulate this problem as a discrete problem on graphs where mobile agents located in distinct nodes of a given graph must quickly reach one of multiple possible exit nodes, while avoiding congestion and bottlenecks. Each node of the graph has the capacity of holding at most one agent at each time step. Thus, the agents must choose their movements strategy based on locations of other agents in the graph, in order to minimize the total time needed for evacuation. In offline scenario, we present a polynomial time solution to compute the optimal strategy for evacuation of all agents. For online (distributed) version, we present a constant competitive algorithm when agents can communicate at distance two in the graph. We also show that when the agents are heterogeneous and each type of agent has access to only a subgraph of the original graph then computing the optimal strategy is NP-hard in the offline case, with full global knowledge. This result holds even if there are only two types of agents.
03/02/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘Maintenance of random logical networks’‘
by Romaric Duvignau (DALGO)

Modelling real-life logical networks (eg P2P networks, social networks) can be a cumbersome task, especially when those networks are dynamic and decentralized simultaneously. A good model is however often needed to analyse or get more precise results on the complexity of distributed algorithms working over these networks. In this context, it might be convenient to use a simplified model of topology (and evolution) to get simulation performance or ease a theoretical analysis. We will show however that care has to be taken in the model choice as some well-known topologies (eg Erdős–Rényi model) cannot arise “naturally” in a decentralized fashion. We will then give several instances of interesting efficiently maintainable models. We will try to highlight along the way the advantages and drawbacks induced by exact maintenance of random logical networks over existing methods.
27/01/2017 at meeting room of LIF, (Prefabricated building) Luminy

’‘Data Aggregation in Dynamic Networks’‘
by Quentin Bramas (Doctorate, LIP6, UPMC Paris)

Les graphes dynamiques, aussi appelés graphes évolutifs, graphes temporels ou graphes variant dans le temps, ont gagné en popularité car il permettent de modéliser un grand nombre de phénomènes, et plus particulièrement les interactions dans les réseaux dont la topologie évolue rapidement, comme les réseaux de capteurs sans fil, les protocoles de population, ou bien les réseaux sociaux. Dans un graphe dynamique, les noeuds et les arrêtes apparaissent et disparaissent au fil du temps, et ces changements ne sont pas vus comme des fautes mais bien comme une caractéristique à part entière du graphe. Dans cette présentation, je vais montrer plusieurs manières de définir les graphes dynamiques et quelles sont leurs propriétés. Enfin, je présenterai à titre d’exemple mes contributions sur le problème de l’agrégation de données dans les graphes dynamiques, d’un point de vue centralisé ou distribué, avec connaissance du futur ou non.
13/01/2017 at salle de réunion du LIF, Luminy

’‘Counting in Anonymous Dynamic Networks’‘
by Giuseppe Antonio Di Luna (Postdoc, University of Ottawa)

Counting is a fundamental problem of every distributed system as it represents a basic building block to implement high level abstractions. We focus on deterministic counting algorithms, that is we assume that no source of randomness is available to processes. We consider a dynamic system where processes do not leave the computation while there is an adversary that continuously changes the communication graph connecting such processes. The adversary is only constrained to maintain at each round a connected topology, i.e., $1$-interval connectivity $G(1-IC)$ of Kuhn et al. In such environment, it has been shown by Michail et al., that counting cannot be solved without a leader. Therefore, we assume that all processes are anonymous but the distinguished leader. In the talk we will discuss bounds and algorithms for counting in the aforementioned framework. Our bounds are obtained investigating networks where the distance between the leader and an anonymous process is persistent across rounds and is at most $h$, we denote such networks as G(PD)_h. Interestingly we will show that counting in such networks requires $\Omega(log |V|)$ rounds even when the bandwidth is unlimited. This implies that counting in networks with constant dynamic diameter requires a number of rounds that is function of the network size. We will discuss other results concerning the accuracy of counting algorithms and the robustness of the aforementioned bound. For the possibility side we will show an optimal counting algorithm for $G(PD)_h$ networks and a quick look on a counting algorithm for $G(1-IC)$ networks.