# Seminary

Talks are scheduled on Mondays from 2 to 3PM, in room 178.

Subscription: send an email to sympa@diff.u-bordeaux.fr with subject "subscribe labri.algodist-gt your_name your_firstname".

## Upcoming talks :

Lundi 18 mars 2019 : Introduction au monitoring continu de flux distribué Nicolas Hanusse (LaBRI)
Résumé : Dans le modèle de monitoring distribué continu, chaque noeud du réseau observe un flux local d'information. L'objectif est de calculer une fonction de l'union des observations en minimisant les communications. Je présenterai brièvement le modèle et quelques résultats de la littérature.

Lundi 25 mars 2019 : Low-depth decompositions of sparse graphs Michal Pilipczuk
Abstract: Decomposition techniques are widely used in designing algorithms on sparse inputs, like planar graphs or graphs of bounded maximum degree. The idea is to cover the input structure with a relatively small number of well-behaved "pieces", so that the search for a global solution can be reduced to searching for a solution in each of the pieces separately. A classic application of this principle is the Baker's layering technique: for every k, every planar graph can be partitioned into k+1 parts so that any k of them induce a graph of treewidth O(k). During the talk we will describe a stronger type of decompositions, called low-treedepth decompositions or p-centered colorings. Here, the idea is that the well-behaved pieces should have bounded depth rather than width. This kind of decompositions is particularly useful for designing parameterized algorithms on sparse graphs, especially in the regimes of low space complexity and of distributed computing. Finally, we will sketch a proof that planar graphs admit p-centered colorings with O(p^19) colors; this part of the talk will be based on a joint work with Sebastian Siebertz, presented at SODA 2019.

Lundi 1 avril au 5 avril 2019 : Réunions ANR et Workshop CoA à Roscoff
Pas de GT cette semaine car la moitié d'entre nous sera à Roscoff.

Lundi 8 avril 2019 : Splitter networks as an introduction to wait-free shared memory distributed computing Corentin Travers (LaBRI)
This talk is in our "culture générale" series.

Lundi 15 avril 2019 : TBA Devan Sohier, UVSQ

Date ultérieure à préciser : Bellman-Ford sous stéroïdes : Un algorithme de routage pour l'établissement automatique des tunnels Mohamed Lamine Lamali (LaBRI)
Résumé : Dans un réseau, un tunnel est une portion d'un chemin où le paquet d'un protocole est encapsulé dans un autre. Un tunnel commence par une encapsulation et se termine par la désencapsulation correspondante. Les tunnels peuvent être imbriqués, la suite des en-têtes des paquets formant une pile de protocole. Les tunnels sont omniprésents dans les réseaux actuels (Transition IPv4/IPv6sécurité, VPN, Onion routing, etc.). Malheureusement, les protocoles de routage actuels ne sont pas capables de construire automatiquement des tunnels, ceux-ci étant précalculés à l'avance et établis par scripts. Le problème algorithmique sous-jacent est celui du calcul du chemin, et plus particulièrement de décider où encapsuler. Il existe un algorithme polynomial pour résoudre le problème, mais à notre connaissance, aucun algorithme distribué n'a été proposé. Dans cet article, nous proposons le premier algorithme de routage distribué avec établissement automatique de tunnels, c'est-à-dire prenant en compte les encapsulations et les conversions de protocoles. Notre algorithme est une généralisation de l'algorithme de Bellman-Ford distribué, où les vecteurs de distances sont remplacés par des vecteurs de piles. Cet algorithme construit des tables de routage permettant de savoir vers quel voisin envoyer un paquet en fonction de sa destination et de sa pile de protocoles. Nous montrons que la taille des messages est polynomiale, même si un plus court chemin peut être exponentiel. Nous montrons également que l'algorithme converge polynomialement en fonction de la taille du réseau et de son diamètre.

Date ultérieure à préciser : TBA Maria Potop-Butucaru (LIP6)

## Archives :

Vendredi 15 mars 2019 : Structural Information in Distributed Computing David Ilcinkas
(soutenance d'HDR, amphithéâtre du LaBRI).

Résumé : The defense will survey some of my contributions to the field of distributed computing in networks, from the point of view of the information available to the computing entities. I will also discuss some confidence issues in this topic of research.

Lundi 11 mars 2019 : Temporal Cliques Admit Sparse Spanners Jason Schoeters (LaBRI)
Résumé : Let G=(V,E) be an undirected graph on n vertices and λ:E →2^N a mapping that assigns to every edge a non-empty set of positive integer labels. These labels can be seen as discrete times when the edge is present. Such a labeled graph {\cal G}=(G,λ) is said to be temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar (STOC 2000) asked whether, given such a temporal graph, a sparse subset of edges can always be found whose labels suffice to preserve temporal connectivity---a temporal spanner. Axiotis and Fotakis (ICALP 2016) answered negatively by exhibiting a family of Θ(n^2)-dense temporal graphs which admit no temporal spanner of density o(n^2). The natural question is then whether sparse temporal spanners can always be found in some classes of dense graphs. In this paper, we answer this question affirmatively, by showing that if the underlying graph G is a complete graph, then one can always find temporal spanners of density O(n log n). The best known result for complete graphs so far was that spanners of density (n choose 2)−⌊n/4⌋=O(n^2) always exist. Our result is the first positive answer as to the existence of o(n^2) sparse spanners in adversarial instances of temporal graphs since the original question by Kempe et al., focusing here on complete graphs. The proofs are constructive and directly adaptable as an algorithm.

(Joint work with A. Casteigts and J. G. Peters, https://arxiv.org/abs/1810.00104)

Lundi 4 mars 2019 : Blockchain: Programming Abstractions Sara Tucci-Piergiovanni, CEA LIST
→ Slides

Résumé : The blockchain is the Bitcoin’s underlying data structure along with the protocol used to maintain it. In Bitcoin, transactions of digital coins between accounts are batched in so-called blocks, where each block is appended to the last one in a cryptographic way to make the malicious/accidental change of blocks content very hard. The protocol features, thanks to the Proof-of-Work, other nice properties, such as, (i) Sybil attack resistance, (ii) incentives for participants that contribute to producing blocks and (ii) a logical global clock represented by the number of produced blocks. These properties make the blockchain a replicated data structure that can be maintained in an open system, where processes can join and leave at will and do not trust each other. Beside these nice features, however, it is still unclear if blockchains can be used to do something else than storing transactions. The hope is that blockchains can be the backbone for the automatic execution of complex transactional protocols – called smart contracts by Nick Szabo. These transactional protocols involve causally dependent transactions of digital assets and related triggering conditions – without recurring to trusted third parties. We advocate that to realize this vision a sound programming model based on an abstract blockchain must be defined. In this talk we formalize the blockchain as an abstract data type that can be concurrently accessed by processes to execute transactional protocols. We distinguish and formalize two classes of abstract blockchains, those that guarantee no forks and those in which forks are possible. We also reduce these two classes to well-known concurrent objects, namely Compare & Swap and Atomic Snapshot. The proposed abstractions are the primitives programmers can use to more easily build transactional protocols that are correct and portable across different blockchains.

Lundi 11 février 2019 : Les réseaux de neurones, des réseaux (et des graphes) comme les autres ? (Partie 2) Akka Zemmari (LaBRI)
(Il s'agit de la suite de l'exposé du 28 janvier).

Résumé : Les réseaux de neurones sont au cœur des techniques d'apprentissage et sont pour beaucoup dans les dernières réussites de l'intelligence artificielle. Dans cet exposé, je présenterai les fondamentaux de ces réseaux : architecture, réseaux profonds, etc, les algorithmes et techniques utilisés pour l'apprentissage : rétro propagation, descente de gradient (et ses variantes), etc.

Lundi 4 février 2019 : Introduction to Quantum Computing Ion Nechita (LPT, Toulouse)
This talk is in our "culture générale" series.

Résumé : In this talk, I will give a short, mathematical, introduction to the field of quantum information. I will define quantum states and quantum channels, comparing them with their classical counterparts. The notion of quantum entanglement will be discussed in detail. Several protocols, such as quantum teleportation, will be presented and analyzed.

Lundi 28 janvier 2019 : Les réseaux de neurones, des réseaux (et des graphes) comme les autres ? (Partie 1) Akka Zemmari (LaBRI)
Il s'agit d'un exposé dans notre série culture générale. Aucun pré-requis n'est nécessaire.

Résumé : Les réseaux de neurones sont au cœur des techniques d'apprentissage et sont pour beaucoup dans les dernières réussites de l'intelligence artificielle. Dans cet exposé, je présenterai les fondamentaux de ces réseaux : architecture, réseaux profonds, etc, les algorithmes et techniques utilisés pour l'apprentissage : rétro propagation, descente de gradient (et ses variantes), etc.

Lundi 21 janvier 2019 : Survol des problématiques liées aux systèmes multi-agents Équipe SMAC de Toulouse
Il s'agit d'un exposé dans notre série culture générale. Lors de cet exposé, Marie-Pierre Gleizes et Pierre Glize, de l'IRIT, nous présenteront la problématique des systèmes multi-agents aussi généralement que possible. Cet exposé sera l'occasion de discuter de points communs entre cette discipline et l'algorithmique distribuée.

Lundi 14 janvier 2019 : Quelques rappels sur la complexité algorithmique Arnaud Casteigts

Lundi 7 janvier 2019 : Calcul de plus courts chemins dans un graphe multi-critères Antonin Lentz
L'exposé sera donné en français.

Résumé : Si l'on pondère les arêtes d'un graphe routier par le temps de parcours de celles-ci, il existe un unique plus court temps pour aller d'un sommet du graphe à un autre. Cependant, si l'on rajoute d'autres critères, le prix par exemple, on perd l'unicité et le nombre de plus courts chemins peut devenir déraisonnable (exponentiel en le nombre de sommets). On cherche donc à approcher ces plus courts chemins avec un ensemble couvrant de taille modeste. Les algorithmes existants étant soit trop lents, soit sans garanties, on propose une nouvelle méthode basée sur le rang des chemins pour éviter ces deux travers.

Lundi 24 et 31 décembre 2018 : Distribution de cadeaux dans les graphes planaires (...vacances de noël...)

Lundi 17 décembre 2018 : Algorithmes : à la recherche de l'universalité perdue Rachid Guerraoui (retransmission)
Retransmission de la leçon inaugurale au collège de France (amphi du LaBRI).

Résumé : L'algorithmique répartie est la discipline scientifique qui identifie les conditions nécessaires et suffisantes sur les réseaux, grands ou petits, permettant de retrouver l'universalité de la machine de Turing. Lorsque ces conditions ne sont pas satisfaites, il s'agit de définir les formes d'universalités restreintes qu'il est possible de réaliser. Sans cela, il est impossible d'appréhender ce que font les algorithmes exécutés sur une chaîne de blocs (blockchain), un cloud, un data center ou sur l'internet des objets, ni de définir ce que permettent de calculer exactement des architectures multi-processeurs. Autrement dit, il est impossible de comprendre l'informatique moderne qui est fondamentalement répartie.

Lundi 10 décembre 2018 : Soutenance de Thèse Henri Derycke
Titre de la thèse : Combinatoire dans des stabilisations du modèle du tas de sable sur la grille $\mathbf{Z}^2$

Mardi 27 novembre 2018 : 61 ans d'Yves Métivier (rétrospective sur le distribué)
Résumé : Les sujets abordés iront des monoïdes de commutation aux réétiquetages de graphes (calculs locaux), en passant par les revêtements et les algorithmes probabilistes, avec une ouverture sur les assistants de preuves. Voici les exposés prévus :

Le matin :

• Robert Cori : Un parcours aléatoire des travaux d’Yves
• Volker Diekert : Solutions sets of trace equations are EDT0L-languages
• Emmanuel Godard : Approche algébrique pour la calculabilité distribuée
• Bernadette Charron-Bost : Les algorithmes naturels de consensus

L'après-midi :

• Joffroy Beauquier : Mariage stable et complexité de communication
• Jérémie Chalopin : Exploration de graphes avec des jumelles
• Akka Zemmari : Que peut faire le hasard, quand on est dans le brouillard ?
• Dominique Mery : Vérification d'algorithmes répartis par construction

Plus d'informations sur http://ym61.labri.fr

Lundi 3 décembre 2018 : Introduction to quantum entanglement and quantum games Ghazal Kachigar
Abstract : In a paper published in 1964, John Bell showed that quantum mechanics can give rise to stronger correlations than what is possible in a purely classical world. His argument has been translated into a two-player game, called Bell’s game, with a quantum strategy that performs better than any classical strategy. Since then, other two- and multi-player games where there is a quantum advantage have been discovered.

In this talk, I will start by introducing basic concepts of quantum information theory (qubits, entanglement, measurement) in a simplified manner. We will then look at Bell’s game and its optimal quantum strategy, and after that, the GHZ game, a three-player game and its quantum winning strategy. If there is any time left, I will also present the Mermin-Peres magic square and some results surrounding it.

This talk assumes a certain degree of familiarity with linear algebra (vectors, matrices, eigenvalues and eigenspaces).

This talk is in our series culture générale. It will be given in French or in English depending on the audience.

Lundi 26 novembre 2018 : Dispersion processes Tomasz Radzik, King's College London
Résumé : We study a synchronous dispersion process in which M particles are initially placed at a distinguished origin vertex of an undirected graph G. At each time step, at each vertex v occupied by more than one particle at the beginning of this step, each of these particles moves to a neighbour of v chosen independently and uniformly at random. The dispersion process ends at the first step when each vertex has at most one particle. A similar process was proposed before in the context of some load balancing problems. For the complete graph with n vertices, we show that for any constant c > 0, with high probability, if M < (1-c)n/2, then the process finishes in O(log n) steps, whereas if M > (1+c)n/2, then the process needs exp{Omega(n)} steps to complete. We also show that a lazy variant of the process exhibits the same behaviour but for higher thresholds, allowing fast dispersion of more particles. For paths, trees, grids, hypercubes and Cayley graphs of large enough sizes (in terms of M), we give bounds on the time to finish and the maximum distance travelled from the origin as a function of the number of particles M.

(Joint work by Colin Cooper, Andrew McDowell, Tomasz Radzik, Nicolas Rivera, Takeharu Shiraga)

Lundi 19 novembre 2018 : Introduction à la complexité de communication Cyril Gavoille
Il s'agit d'un exposé dans notre série culture générale (en français au tableau).

Résumé : Dans cet exposé je présenterai une technique de borne inférieure adaptée pour certains problèmes issus du calcul distribué, mais pas que. Cela sera l'occasion d'introduire la "complexité de communication", et de montrer comment cet outil peut s'appliquer à la détection distribuée de cycles de longueur quatre.

Lundi 12 novembre 2018 : Soutenance d'HDR Alessia Milani (amphi du LaBRI)
Titre de l'Habilitation : On the complexity of democratizing concurrent programming: an algorithmic perspective

Lundi 5 novembre 2018 : Randomization and Quantization for Average Consensus Patrick Lambein, LIX
Résumé : Many problems in distributed control reduce to the distributed computation of the average of initial values in a networked system of autonomous agents, known as the average consensus problem. We present a randomized algorithm that solves this problem in networks with directed, time-varying communication topologies, in linear time in the size of the network. This algorithm leverages properties of exponential random variables, which allows for approximating sums by computing minima. It is completely decentralized, in the sense that it does not rely on agent identifiers or global information of any kind. Using a logarithmic rounding rule, we show that this algorithm can be used under the additional constraints of finite memory and channel capacity. We furthermore extend the algorithm with a termination test, by which the agents can decide irrevocably in finite time — rather than simply converge — on an estimate of the average.

Lundi 22 octobre 2018 : Introduction to the TSP Arnaud Casteigts
Il s'agit d'un exposé dans notre série culture générale, qui sera donné en français au tableau.

Lundi 15 octobre 2018 : Discussions sur le GT (tout le monde)

Lundi 8 octobre 2018 : Mutual Exclusion - New Twists on an Old Tale Danny Hendler, Ben-Gurion University
Résumé : Mutual exclusion, introduced by Dijkstra more than 50 years ago, is one of the most fundamental problems in distributed computing. In this talk, I will describe a few key results in classic shared-memory mutual exclusion research. Time permitting, I will also present novel variants of mutual exclusion whose goal is to model existing computer systems more realistically, as well as to model emerging new types of systems. The talk will be self-contained and no prior knowledge of shared-memory mutual exclusion is assumed.

Lundi 25 juin 2018 : " Exposé sur les bizantins " Sébastien Tixeuil, UPMC

Lundi 4 juin 2018 : A Journey through Dynamic Networks (with Excursions) Arnaud Casteigts
Résumé : Soutenance d'habilitation à diriger des recherches (14h, amphi du LaBRI).

Lundi 14 mai 2018 : ' Distributed Spanning Tree Computation, Distributed Topology Computation and... Coverings ' Yves Métivier
Résumé : We present a characterisation of graphs which enable the distributed computation of their topology or the distributed computation of a spanning tree in terms of coverings. (Travail avec Arnaud Casteigts et John Michael Robson)

Lundi 23 avril 2018 : Whac-A-Mole: Smart node positioning in clone attack in wireless sensor networks Akka Zemmari
Résumé : Wireless sensor networks are often deployed in unattended environments and, thus, an adversary can physically capture some of the sensors, build clones with the same identity as the captured sensors, and place these clones at strategic positions in the network for further malicious activities. Such attacks, called clone attacks, are a very serious threat against the usefulness of wireless networks. Researchers proposed different techniques to detect such attacks. The most promising detection techniques are the distributed ones that scale for large networks and distribute the task of detecting the presence of clones among all sensors, thus, making it hard for a smart attacker to position the clones in such a way as to disrupt the detection process. However, even when the distributed algorithms work normally, their ability to discover an attack may vary greatly with the position of the clones. We believe this aspect has been greatly underestimated in the literature. In this paper, we present a thorough and novel study of the relation between the position of clones and the probability that the clones are detected. To the best of our knowledge, this is the first such study. In particular, we consider four algorithms that are re- presentatives of the distributed approach. We evaluate for them whether their capability of detecting clone attacks is influenced by the positions of the clones. Since wireless sensor networks may be deployed in different situations, our study considers several possible scenarios: a uniform scenario in which the sensors are deployed uniformly, and also not uniform scenarios, in which there are one or more large areas with no sensor (we call such areas “holes”) that force communications to flow around these areas. We show that the different scenarios greatly influence the performance of the algorithms. For instance, we show that, when holes are present, there are some clone positions that make the attacks much harder to be detected. We believe that our work is key to better understand the actual security risk of the clone attack in the presence of a smart adversary and also with respect to different deployment scenarios. Moreover, our work suggests, for the different scenarios, effective clone detection solutions even when a smart adversary is part of the game.

Lundi 9 avril 2018 : (Méta)-noyaux constructifs et linéaires dans les graphes peu denses Valentin Garnero
Résumé : Dans cet exposé je vous présenterai les résultats obtenus au cours de ma thèse, laquelle traite de noyaux et de complexité paramétrée. La complexité paramétrée est une branche de l'algorithmie qui analyse la complexité d'un problème en fonction de la taille des données n et d'un paramètre k (arbitraire). L'objectif est de pouvoir attaquer des problèmes difficiles (NPc) et de montrer que l’exposition combinatoire n'est fonction que du paramètre (et pas de la taille des données), cad, trouver des algorithmes en f(k)+p(n). L'extraction de noyau est une méthode qui permet d'obtenir des algorithmes avec un telle complexité. Il s'agit d'un pré-calcul (une réduction polynomiale) qui réduit la taille des données en temps polynomial, tout en garantissant que la taille du noyau (l'instance réduite) est bornée par une fonction du paramètre g(k). Il suffit de résoudre le problème dans le noyau, de n'importe quelle façon, pour obtenir un algorithme en f(g(k)) + p(n).

La méthode de décomposition en régions [Alber, Fellows, Niedermeier] est un résultat majeur dans le domaine des noyaux. Elle a permis de construire de nombreux noyaux linaires pour des variantes de la Domination dans les graphes planaires. J'illustrerai cette méthode avec le cas de la Domination Rouge Bleu, qui consiste à trouver, dans un graphe bicoloré, un ensemble de sommets bleus tel que tous les sommets rouges sont à distance au plus 1 de la solution.

Cette méthode a ensuite été généralisée par des méta-résultats [ex: Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos], qui prouve l'existence de noyaux (dans des graphes peu denses) pour tout problème vérifiant certaines conditions génériques. Je présenterai un de ses méta-résultats, qui se base sur la programmation dynamique et sur la décomposition en protrusion, et qui a le mérite d’être constructif.

Lundi 26 mars 2018 : Distributed coloring in sparse graphs with fewer colors Marthe Bonamy
Résumé : We are concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the proof gives a (sequential) quadratic algorithm finding such a coloring. A natural problem is to improve this complexity in the distributed setting. Using the fact that planar graphs contain linearly many vertices of degree at most 6, Goldberg, Plotkin, and Shannon obtained a deterministic distributed algorithm coloring n-vertex planar graphs with 7 colors in O(logn) rounds. Here, we show how to color planar graphs with 6 colors in polylog(n) rounds. Our algorithm indeed works more generally in the list-coloring setting and for sparse graphs (for such graphs we improve by at least one the number of colors resulting from an efficient algorithm of Barenboim and Elkin, at the expense of a slightly worst complexity). Our bounds on the number of colors turn out to be quite sharp in general. Among other results, we show that no distributed algorithm can color every n-vertex planar graph with 4 colors in o(n) rounds. This is joint work with Pierre Aboulker, Nicolas Bousquet and Louis Esperet.

Lundi 19 mars 2018 : Simple Consensus Protocols Frederik Mallmann-Trenn, MIT
Résumé : We study consensus processes on the complete graph of n nodes. Initially, each node supports one from up to n different opinions. Nodes randomly and in parallel sample the opinions of constant many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion. In particular, we consider the Voter process, 3-Majority, and 2-Choices.

Lundi 5 mars 2018 : ' PADEC: A Framework for Certified Self-Stabilization ' Karine Altisen, Verimag
Résumé : Joint work with Pierre Corbineau and Stéphane Devismes

Self-stabilization is a property that allows distributed algorithms to withstand transient faults and recover a correct behavior within finite time. It has been introduced by Dijkstra in 1974. Over the last decades, progress in self-stabilization has led to consider more and more adversarial environments. This make the design, proof for correctness and complexity analysis of self-stabilizing solutions more and more intricate.

However, those proofs are commonly written by hand, based on informal reasoning. In this work, we propose instead to use a proof assistant, a tool which allows to develop certified proofs interactively and check them mechanically. We present the PADEC framework, a Coq library dedicated to building certified proofs of self-stabilizing algorithms.

We first define in Coq the computational model which is the most commonly used in the self-stabilizing area, and its semantics. We propose several tools for proving convergence of algorithms and for counting elements. We illustrate the use of our framework by: - certifying a non-trivial part of an existing self-stabilizing algorithm; - certifying a commonly-used composition operation for self-stabilizing algorithms.

Lundi 26 février 2018 : TBA Nicolas Hanusse REPORTÉ

Lundi 12 février 2018 : Distributed Recoloring: the addition of colors Mikaël Rabie, Aalto University

Résumé : Given two colorings of a graph, we consider the following question: can we re-color the graph from one coloring to the other through a series of elementary changes? Here, an elementary change, or step, consists in selecting an independent set and changing the color of each vertex to another also compatible with the colors of its neighbors. The answer is not always positive, and it is in fact a PSPACE-complete decision problem. In this talk, we try to quantify how considering a stable set at each step instead of a single vertex impacts the number of steps necessary for a re-coloring, and how much communication is needed in the LOCAL model (at each round, a vertex can only communicate with its neighbors, with no limitation as to the size of the messages nor the computation power of the vertex) to compute the re-coloring or decide there is none. We also consider the question of how many extra colors are needed to make the problem always feasible, and beyond that, how the number of necessary steps decreases with the addition of colors. The case of trees is of special interest. I will provide a collection of both positive and negative results around those questions. This a joint work with Marthe Bonamy, Paul Ouvrard, Jukka Suomela and Jara Uitto.

Lundi 5 février 2018 : Refinement-Based Composition for Computing Snapshots in Distributed Anonymous Networks Maha Boussabbeh

Résumé : Recording a global state of a distributed computation is one of the most important paradigm that finds applications in several aspects of a distributed system design. Algorithms recording such global states are called snapshot algorithms. Most of them assume that the network is not anonymous or there exists a distinguished process. We explore the correct-by-construction process to formalize snapshot computations in an anonymous network. Based on recent studies, we investigate existing algorithms to highlight how they can be composed and specified in a top/down approach in order to obtain a global view anonymously. This approach is supported by an incremental process controlled by model refinements.

Lundi 22 janvier 2018 : On the simplification of temporal cliques Arnaud Casteigts
Résumé : In the context of this talk, a temporal clique is a complete graph with a unique integer label on every edge. This number can be thought of as the only date at which both endpoints interact. In a recent article, Akrida, Gasieniek, Mertzios, and Spirakis show that n/4 well chosen edges can be removed in such a graph without breaking temporal connectivity (i.e. maintaining increasing paths (journeys) between every pair of nodes, in both directions). In this talk, I will present a three-steps proof which gradually improves upon this result. The first step shows that (n^2)/8 edges (i.e. one quarter of the edges) can be removed; the second step, building upon the first, shows that half of the edges can actually be removed; then the third step, building upon the other two, shows that all edges but O(n) can actually be removed. This is obviously tight (up to a constant factor). Characterizing the exact factor that our proof yields is still work in progress. On the other hand, we give a conjecture as to the exact number of edges which can be removed (à un près), supported by extensive simulations.

Lundi 15 janvier 2018 : The Firing Squad Problem Revisited Bernadette Charron-Bost, LIX

Résumé : In the classical firing squad problem, an unknown number of nodes represented by identical finite states machines is arranged on a line and in each time unit each node may change its state according to its neighbors' states. Initially all nodes are passive, except one specific node located at an end of the line, which issues a fire command. This command needs to be propagated to all other nodes, so that eventually all nodes simultaneously enter some designated “firing" state.

A natural extension of the firing squad problem, introduced in this paper, allows each node to postpone its participation in the squad for an arbitrary time, possibly forever, and firing is allowed only after all nodes decided to participate. This variant is highly relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously.

The main goal of this paper is to study the above variant of the firing squad problem under the assumptions that the nodes are infinite state machines, have full computational capabilities, and that the inter-node communication links can be changed arbitrarily in each time unit, i.e., are defined by a dynamic graph. In this setting, we study the following fundamental question: what connectivity requirements enable a solution to the firing squad problem?

Our main result is an exact characterization of the dynamic graphs for which the firing squad problem can be solved. When restricted to static directed graphs, this characterization implies that the problem can be solved if and only if the graph is strongly connected. We also discuss how information on the number of nodes or on the diameter of the network, and the use of randomization, can improve the solutions to the problem.

Joint work with Shlomo Moran (Technion)

Group

GT

Positions