Main

Past talks 2 (2018–2021)

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

2021

---

Lundi 22 novembre : Local algorithms for dominating set in sparse graphs Alexandre VIGNY (University of Bremen)
We show how local algorithms can compute constant factor approximations of minimum dominating sets for sparse graphs. More precisely, we first generalize existing algorithms to classes of graphs with bounded expansion, and then improve the known approximation factor for graphs classes that are planar or more restricted.

Lundi 25 octobre : Réalisation d'un simulateur pour les algorithmes de requête de proximité sur des nuages de points mobiles Gustave MONCE (Bordeaux INP)
Dans le cadre d’applications qui concernent des points en mouvement, qu’il s’agisse de points réels ou virtuels, il est souvent intéressant de garder, pour chaque point, une liste de points proches. Dans les jeux vidéos (virtuel), il est nécessaire de garantir que le visuel perçu par deux joueurs proches soit identique. Dans la circulation routière (réel), il peut être intéressant d’obtenir la liste des voitures proches afin de garder des distances de sécurité entre les voitures et de prévenir tout accident. Quelle que soit l’application considérée, la difficulté principale provient du mouvement des points. En effet, une méthode naïve pour maintenir une structure de données sur un ensemble mobile de points consisterait à recalculer entièrement la structure cible à intervalles de temps réguliers, mais cela est soit coûteux (si on recalcule la structure trop souvent), soit peu précis (si on recalcule la structure trop rarement). Il convient donc de chercher des méthodes qui, le plus possible, n’amènent à faire des calculs seulement lorsque la structure devient insatisfaisante, suivant le nombre de points à traiter. Dans un contexte distribué, il convient de plus d’être économe en communications, puisque la bande passante des différents appareils peut être limitée.

Tobias Castanet a conçu des algorithmes qui permettent, pour un ensemble de points mobiles donnés, de maintenir ou d’obtenir la liste des points proches, c’est-à-dire la liste des points à distance inférieure à R d’un point donné. Néanmoins, la correction de ces algorithmes reste compliquée, et il convient de compléter les mesures de performances théoriques avec des mesures plus pratiques, issues de simulations.

Un simulateur a donc été réalisé afin de mesurer les performances de différents algorithmes ainsi que d'aider au débogage de ces algorithmes. Nous verrons comment ce simulateur a été réalisé, son fonctionnement, ainsi que les différentes optimisations et mesures de performances réalisées.

Lundi 5 juillet (14h30) : Calcul de plus courts chemins multicritères et problèmes géométriques connexes (PhD defense) Antonin LENTZ (LaBRI, Bordeaux)
Cette thèse s'intéresse au calcul de plus courts chemins multicritères approché. Lorsque l'on prend en compte plusieurs critères à la fois, de nombreux chemins de coûts différents peuvent proposer différents compromis intéressants. On appelle ensemble de Pareto l'ensemble de ces chemins. Son calcul est souvent prohibitif, c'est pourquoi on cherche généralement à n'en calculer qu'un sous ensemble. Certaines méthodes sont performantes en pratique mais elles n'offrent aucune garantie de représentativité, c'est-à-dire de distribution des chemins calculés dans l'ensemble de Pareto. A l'inverse, d'autres méthodes garantissent une certaine représentativité et des complexités intéressantes mais elles sont généralement inutilisables en pratique.

Nous commençons par proposer des optimisations pour le calcul d'ensembles de Pareto exacts, ainsi que des algorithmes d'approximation avec des garanties théoriques intéressantes, en termes de complexité et de représentativité. Nous introduisons également la notion de Pareto compatible qui garantit que la sortie d'un algorithme n'est constituée que de chemins optimaux. Nous présentons un algorithme bicritère vérifiant cette propriété. Nous menons une étude expérimentale, montrant que notre algorithme est intéressant lorsque les ensembles de Pareto sont grands.

Afin d'améliorer nos algorithmes d'approximation en 3D, nous étudions les Thêta-graphes. Nous proposons des algorithmes efficaces pour leur maintenance dynamique. Ensuite, nous étudions une requête de proximité orientée, utilisant un Thêta-graphe pour trouver les plus proches voisins dans une direction donnée. Enfin, nous détaillons comment appliquer nos algorithmes dédiés aux Thêta-graphes pour le calcul de plus courts chemins tricritères.

Lien pour suivre l'exposé et les questions : https://youtu.be/EJp5ajlNAPc

Lien pour suivre le résultat des délibérations du jury : https://youtu.be/8j62uLWECqc

Lundi 14 juin : Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs Arnaud LABOUREL (LIS, Marseille)
A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B=2(1+α)r, for some positive real constant α, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most ⌊B⌋ edge traversals between two consecutive visits at node s. Let e(d) be the number of edges whose at least one extremity is at distance less than d from s. Awerbuch, Betke, Rivest and Singh conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost O(e(d)logd), and then show how to modify this algorithm to work in the model from with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.

This is a joint work with Sébastien Bouchard, Yoann Dieudonné, and Andrzej Pelc

Lundi 7 juin : Robustness of distances and diameter in an aging network Timothée CORSINI (LaBRI, Bordeaux)
A property of a graph G is robust if it is satisfied in all connected spanning subgraphs of G. This notion of robustness is a particular kind of heredity, motivated by dynamic networks. In this talk, I will present work in progress around the characterization of graphs that have a robust diameter (among others). This property has some importance in distributed algorithms, because it guarantees that even if some edges of a network disappear, the diameter (which is often used as a measure of complexity for distributed algorithms) will remain stable as long as connectivity holds. Unfortunately, the problem of deciding if the diameter of a graph is robust turns out to be difficult (co-NP-complete), but interestingly, deciding the robustness of the distance between two vertices is tractable, based on a characterization of this property in terms of series-parallel graphs and ear decomposition.

This is joint work with Arnaud Casteigts and Hervé Hocquard.

Lundi 31 mai : Long-Lived Shared Objects with Polylogarithmic Amortized Step Complexity Alessia MILANI (LaBRI, 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. Slides

Lundi 17 mai : Maximum 0-1 Timed Matching on Temporal Graphs Subhrangsu MANDAL (IIT, Kharagpur)
Temporal graphs are graphs where the topology and/or other properties of the graph change with time. They have been used to model applications with temporal information in various domains. Problems on static graphs become more challenging to solve in temporal graphs because of dynamically changing topology, and many recent works have explored graph problems on temporal graphs. In this paper, we define a type of matching called {\em 0-1 timed matching} for temporal graphs, and investigate the problem of finding a {\em maximum 0-1 timed matching} for different classes of temporal graphs. We assume that only the edge set of the temporal graph changes with time. Thus, a temporal graph can be represented by associating each edge with one or more non-overlapping discrete time intervals for which that edge exists. We first prove that the problem is NP-complete for rooted temporal trees when each edge is associated with two or more time intervals. We then propose an $O(n^2 \log n)$ time algorithm for the problem on a rooted temporal tree with $n$ vertices when each edge is associated with exactly one time interval. The problem is then shown to be NP-complete also for bipartite temporal graphs even when each edge is associated with a single time interval and degree of each vertex is bounded by a constant $k \geq 3$. We next investigate approximation algorithms for the problem for temporal graphs where each edge is associated with more than one time intervals. It is first shown that there is no $\frac{1}{n^{1-\epsilon}}$-factor approximation algorithm for the problem for any $\epsilon > 0$ even on a rooted temporal tree with $n$ vertices unless NP = ZPP. We then present a $\frac{5}{2\mathcal{N}^* + 3}$-factor approximation algorithm for the problem for general temporal graphs where $\mathcal{N^*}$ is the average number of edges overlapping in time with each edge in the temporal graph. The same algorithm is also a constant-factor approximation algorithm for temporal graphs with degree of each vertex bounded by a constant.

Lundi 3 mai : Asynchronous Self-Stabilizing Stable Marriage. Marie LAVEAU (iCube, Strasbourg)
The *Stable Marriage Problem* (SMP) is a matching problem where participants have preferences over their potential partners. The objective is to find a matching that is optimal (stable in certain sense) with respect to these preferences. This type of matching has a lot of widely used applications such as the assignment of children to schools, interns to hospitals, kidney transplant patients to donors, as well as taxi scheduling or content delivery on the Internet.

In this talk, we present two asynchronous self-stabilizing algorithms for the stable marriage problem. For both algorithms, the asynchrony is modeled with an unfair scheduler. A common way to obtain self-stabilizing algorithms is to detect if the algorithm's output is correct and if not, repair (either locally or globally). Based on this idea, the first algorithm relies on local repairs while the second uses a global one. The first algorithm is based on the centralized method of Ackermann et al. (SICOMP' 2011). The starting point of the second algorithm is the local detection/global correction scheme of Awerbuch et al. (DA' 1994). With this scheme, a non-self-stabilizing algorithm (with initialization) that satisfies the property of *local checkability* can be combined with a detector and a reset algorithm. When a problem is detected, the reset algorithm solves the problem by globally resetting the system. The result of this composition is a self-stabilizing version of the given algorithm. Unfortunately, the local checkability definition of DA '1994 does not apply to our case, due to the unfair daemon. Consequently, we propose an adapted definition that might be useful for other problems.

Lundi 29 mars à 14h : Contributions to temporal graph theory and mobility-related problems soutenance de thèse de Jason SCHOETERS (LaBRI, Bordeaux)
In this thesis, we consider research questions that pertain respectively to temporal graphs, to mobility, as well as to the interaction between the two. The problem we consider on temporal graphs is motivated by a 20-year old open question, namely what the analog definition of a spanning tree in temporal graphs is. It turns out that this notion has puzzled researchers ever since, due to the fact that even analogs of sparse spanners do not exist in general temporal graphs. Our main result on this topic is showing that sparse spanners however exist in significant particular cases. On the other end of the field of dynamic networks, motivated mostly by the particular case of MANETs, we study the design of physical movements and how this may be approached in an algorithmic fashion, instead of through typical control theory methods. This led us to consider a discrete model of acceleration called racetrack and to revisit the traveling salesperson problem (TSP) with this additional constraint. While seemingly unrelated, the questions of movement design on one hand, and temporal graphs on the other, end up being in strong interaction when considering the execution of distributed algorithms in a MANET scenario. In an effort to connect the two ends of the spectrum, our third contribution considers the interaction between the two, by means of the design of collective movements that induce temporal graph properties in the resulting communication network. This third topic is developed as a software package, available for researchers in distributed computing.

Connexion : https://u-bordeaux-fr.zoom.us/j/87091396515

Lundi 22 mars : Want to Gather? No Need to Chatter! Sébastien BOUCHARD (LaBRI, Bordeaux)
A team of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node and declare that they have all met. Agents have different labels which are positive integers, and move in synchronous rounds along links of the network. The above task is known as gathering and was traditionally considered under the assumption that when some agents are at the same node then they can talk, i.e., exchange currently available information. The presentation will show that this ability of talking is not needed for gathering.

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 15 mars : Broadcasting with mobile agents in dynamic networks Shantanu DAS (LIS, Marseille)
We study the standard communication problem of broadcast for mobile agents moving in a network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. In this model, broadcast is a communication primitive for information transfer from one agent, the source, to all other agents. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modelled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of other agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine how many agents are necessary and sufficient to solve the broadcast problem in dynamic networks. While two agents plus the source are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes at least n − 2 agents plus the source are necessary and sufficient. We show lower bounds on the number of agents and provide some algorithms for solving broadcast using the minimum number of agents, for various topologies. These results show how the connectivity of the underlying graph affects the communication capability of a team of mobile agents in constantly connected dynamic networks. (Joint Work with Nikos Giachoudis, Flaminia L. Luccio, and Euripides Markou)

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 8 mars : Can Uncoordinated Beeps tell Stories? Fabien DUFOULON (Technion - Israel Institute of Technology, Haifa)
This work studies distributed systems of devices with severely limited communication capabilities: they communicate only via simple bursts of energy. Such systems may be analyzed using the beeping model (over a communication graph), where devices (nodes) communicate, in synchronous rounds, by beeping or listening to their neighbors. Simultaneous communications result in non-destructive interference: a node with multiple neighbors beeping simultaneously still detects a beep. This simple, general and energy efficient communication mechanism makes the beeping model widely applicable. The main challenge to algorithm design in this model stems from the poor expressiveness of beeps and the interference caused by simultaneous communications. Additionally, nodes wake up adversarially---that is, at arbitrarily different times---and thus they do not have access to a global clock. In this harsh model, exceedingly few problems are known to be solvable (e.g., maximal independent set and 1-hop desynchronization). In this work, we provide the first algorithm solving the 2-hop desynchronization problem (a variant of 2-hop coloring). By solving this problem, nodes can avoid simultaneous collisions. Leveraging this property, we also present a message-passing abstraction layer that allows the execution of traditional distributed computing (e.g., CONGEST) algorithms. As a result, a large class of problems can be solved in this model.

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 1 mars : On Implementing Stabilizing Leader Election with Weak Assumptions on Network Dynamics Anaïs DURAND (LIMOS, Clermont-Ferrand)
We consider self-stabilization and its weakened form called pseudo-stabilization. We study conditions under which (pseudo- and self-) stabilizing leader election is solvable in networks subject to frequent topological changes. To model such an high dynamics, we use the dynamic graph (DG) paradigm and study a taxonomy of nine important DG classes. Our results show that self-stabilizing leader election can only be achieved in the classes where all processes are sources.

Furthermore, even pseudo-stabilizing leader election cannot be solved in all remaining classes, except in the class where at least one process is a timely source. We illustrate that result by proposing a pseudo-stabilizing leader election algorithm for the latter class. We also show that in this last case, the convergence time of pseudo-stabilizing leader election algorithms cannot be bounded. Nevertheless, we show that our solution is speculative since its convergence time can be bounded when the dynamics is not too erratic, precisely when all processes are timely sources.

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 22 février : Branch-and-cut-and-price approaches for two-echelon vehicle routing problems Guillaume MARQUES (ATOPTIMA, Bordeaux)
Atoptima is a software editor in decision support system aiming to offer cutting-edge mathematical optimization to all businesses requiring resource assignment optimization.

We will focus on methods of mathematical optimization to solve vehicle routing problems in two-level distribution systems. In such a system, the first level involves trucks that ships goods from a distribution center to intermediate depots called satellites. The second level involves city freighters that are loaded with goods at satellites and deliver the customers. Each customer must be visited once. The two-echelon vehicle routing problem seeks to minimize the total transportation cost in such a distribution system.

In this presentation, we will talk about the branch-and-cut-and-price algorithm and state-of-the-art key features to optimize vehicle routing problems. We will introduce a new route based formulation for the problem which does not use variables to determine product flows in satellites. We will propose a new branching strategy which significantly decreases the size of the branch-and-bound tree. We will suggest a new family of satellite supply inequalities, and we empirically show that it improves our formulation. Experiments reveal that our algorithm can solve all literature instances with up to 200 customers and 10 satellites. Then, we will see how to tackle the variant of the problem where customers must be visited within time-windows. We will finish on an adaptation of the problem prototyped at Atoptima.

Most of the talk comes from the work done during my PhD (joint work with Ruslan Sadykov, Rémy Dupas, Jean-Christophe Deschamps) at Université de Bordeaux.

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 1 février : Local certification of planar and bounded-genus graphs Laurent FEUILLOLEY (LIRIS, Lyon)
Many distributed graph algorithms are designed for general graphs or bounded-degree graphs, but some algorithms exploit other graph structures. For example one can get a good dominating set approximation in planar graph in constant time, which is impossible in general graph. A problem here is that it is not possible to check locally that the network is e.g. planar, and we would like to do so before running our local algorithm specially tailored for planar graphs.

In this talk I will present how we can certify planarity by assigning small informative labels to the nodes. Then I will show how to extend this to bounded genus graphs.

In a few words, for certifying planarity, the approach consists basically in (virtually) transforming the graph into an outerplanar graph by duplicating some nodes of a spanning tree, and then to use the ordering of the nodes around the outerface as a labeling. The extension to bounded genus is via careful surgery on the surfaces in order to go back to the planar case.

This talk is based on the two following papers which are joint work with Pierre Fraigniaud, Ivan Rapaport, Éric Rémila, Pedro Montealegre and Ioan Todinca.

Compact Distributed Certification of Planar Graphs. PODC 2020.

https://arxiv.org/abs/2005.05863

Local Certification of Graphs with Bounded Genus. Preprint.

https://arxiv.org/abs/2007.08084

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 25 janvier : Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension Guillaume DUCOFFE (ICI, Bucharest)
Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs and planar graphs, to name a few. We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many such classes – where the distance VC-dimension of a graph G is defined as the VC-dimension of its ball hypergraph: whose hyperedges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free graphs has distance VC-dimension at most |V(H)|− 1.

• Our first main result is a Monte Carlo algorithm that on graphs of distance VC-dimension at most d, for any fixed k, either computes the diameter or concludes that it is larger than k in time O(k ·mn^{1−εd}), where εd ∈ (0; 1) only depends on d. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such graphs.
• Then as a byproduct of our approach, we get a truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense graph classes. The latter classes include all proper minor-closed graph classes, bounded-degree graphs and graphs of bounded expansion.
• Finally, we show how to remove the dependency on k for any graph class that excludes a fixed graph H as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such graphs one obtains a truly subquadratictime randomized algorithm for computing their diameter.

We note that all our results also hold for radius computation. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of ε-nets, region decomposition and other partition techniques.

If time allows, I will also mention recent improvements of the above results, to eccentricity and distance oracle computations.

This is joint work with Michel Habib and Laurent Viennot.

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 11 janvier : Infinite Grid Exploration by Disoriented Robots Quentin BRAMAS (iCube, Strasbourg)
We study the infinite grid exploration (IGE) problem by a swarm of autonomous mobile robots. Those robots are opaque, have limited visibility capabilities, and run using synchronous Look-Compute-Move cycles. They all agree on a common chirality, but have no global compass. Finally, they may use lights of different colors that can be seen by robots in their surroundings, but except from that, robots have neither persistent memories, nor communication mean. We show that using only three fixed colors, six robots, with a visibility range restricted to one, are necessary and sufficient to solve the non-exclusive IGE problem. We show that using modifiable colors with only five states, five such robots, with a visibility range restricted to one, are necessary and sufficient to solve the (exclusive) IGE problem. Assuming a visibility range of two, we also provide an algorithm that solves the IGE problem using only seven identical robots without any light.

Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

Lundi 4 janvier : Discussions autour du projet Kune Christian GLACET (CTO Kune, Bordeaux)
Kune est une start-up montée par Christian Glacet (ancien doctorant du LaBRI) et Maxime Phelipot. Le projet porte sur le développement d'une application de planification de voyage intelligent, faisant intervenir plusieurs problèmes algorithmiques tels que le TSP et le sac à dos. Cet exposé sera l'occasion de discuter de ces problèmes et du projet en général.

Connexion : https://u-bordeaux-fr.zoom.us/j/8290692255

2020

Lundi 14 décembre : Modeling Spatio-Temporal Phenomena using Graphs Kamaldeep Singh OBEROI (LITIS, Rouen)
Modeling and analysing spatio-temporal (ST) phenomena is a well known research domain which plays a key role in the development of Geographic Information Systems. The need for modeling ST phenomena is to understand the evolution of the phenomenon as a whole as well as formalize the behavior of the entities which constitute the considered phenomenon. Different qualitative and quantitative methods have been proposed to describe such entities and in turn their ST evolution. Taking the qualitative point of view, a phenomenon can be considered to consist of different entities having some spatial/non-spatial relations between them, without considering the precise information for their representation. This results in a graph-based model where the nodes of the graph represent the entities and edges represent the relations between them. Taking two representative examples, urban road traffic and invasive team sports, we will first take a look at how a dynamic graph-based model can be defined for each. Next, we will discuss the advantage of using graphs for modeling such phenomena and see how the structure of the graph can be applied for analyzing the behavior of the entities and the evolution of the phenomenon, something which is missing from the quantitative models.

Lundi 7 décembre : On Efficient Low Distortion Ultrametric Embedding Guillaume Lagarde (LaBRI, Bordeaux)
A classic problem in unsupervised learning and data analysis is to find simple and easy-to-visualize representations of the data that still preserve its essential properties. Hierarchical clustering is one such representation that is widely used and preserves the underlying hierarchical structure of the data. The task of finding an interesting hierarchical clustering can be formalized as the task of finding an embedding of the data into an ultrametric space. The most popular algorithms are the so-called "agglomerative" ones (single linkage, average linkage, Ward's method, etc.). However these methods exhibit a prohibitive quadratic running time, making them impractical to handle large inputs. In this talk I will present a new algorithm that runs for Euclidean metric in time n^{1+1/c^2} for any constant c >= 1 and outputs a 5c-approximation of the "best" ultrametric. We complement this approach with some lower bounds and prove in particular that, in some settings, there is no 3/2-approximation running in subquadratic time. Finally I will present some empirical evaluation of the algorithm on some classic machine learning datasets. Joint work with Vincent Cohen-Addad and Karthik C. S.

Details to be posted there: https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

Lundi 30 novembre : Élection Autostabilisante dans les Réseaux à Haute Dynamicité Colette JOHNEN (LaBRI)
Nous nous intéressons à la conception d'algorithmes autostabilisants pour des réseaux identifiés hautement dynamiques. Précisément, nous considérons le problème de l'élection dans trois classes de graphes dynamiques (TVG) : la classe TCB(∆) les TVG de diamètre temporel borné par ∆, la classe TCQ(∆) les TVG de diamètre temporel quasiment borné par ∆ et la classe TCR des TVG à connectivité temporelle récurrente. Nous montrons qu'en dépit des identités, dans les classes TCQ(∆) et TCR, tout algorithme autostabilisant d'élection nécessite la connaissance exacte du nombre de processus. Puis nous proposons trois algorithmes d'élection. Le premier, pour la classe TCB(∆), stabilise en au plus 3∆ rondes. Dans TCQ(∆) et TCR, le temps de stabilisation d'un algorithme autostabilisant d'élection ne peut pas être borné. Cependant, nous montrons que nos deux solutions sont spéculatives, c'est-à-dire qu'elles ont de bonnes performances dans des cas favorables ; en effet, elles stabilisent en O(∆) rondes lorsque l'on se restreint à la classe TCB(∆).

Travail commun avec Karine Altisen, Stéphane Devismes, Anaïs Durand, et Franck Petit.

Details to be posted there: https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

Lundi 23 novembre : Adjacency Labelling for Planar Graphs (and Beyond) Cyril GAVOILLE (LaBRI, Bordeaux)
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an $n$-vertex planar graph $G$ is assigned a $(1+o(1))\log_2 n$-bit label and the labels of two vertices $u$ and $v$ are sufficient to determine if $uv$ is an edge of $G$. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices such that every $n$-vertex planar graph is an induced subgraph of $U_n$. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and $k$-planar graphs.

This work will appear at FOCS'20 and is joint with Vida Dujmović, Louis Esperet, Gwenaël Joret and Pat Morin.

Lundi 2 novembre : Back to the Coordinated Attack Problem Emmanuel GODARD (LIS, Marseille)
We consider the well known Coordinated Attack Problem, where two generals have to decide on a common attack, when their messengers can be captured by the enemy. Informally, this problem represents the difficulties to agree in the present of communication faults. We consider here only omission faults (loss of message), but contrary to previous studies, we do not to restrict the way messages can be lost, i.e. we make no specific assumption, we use no specific failure metric. In the large subclass of message adversaries where the double simulta- neous omission can never happen, we characterize which ones are obstructions for the Coordinated Attack Problem. We give two proofs of this result. One is combinatorial and uses the classical bivalency technique for the necessary condition. The second is topological and uses simplicial complexes to prove the necessary condition. We also present two different Consensus algorithms that are combinatorial (resp. topological) in essence. Finally, we analyze the two proofs and illustrate the relationship between the combinatorial approach and the topological approach in the very general case of message adversaries. We show that the topological characterization gives a clearer explanation of why some message adversaries are obstructions or not. This result is a convincing illustration of the power of topological tools for distributed computability.

Joint work with Eloi Perdereau

Details to be posted there: https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

Lundi 28 septembre : Schéma d’étiquetage de distance pour des familles de graphes définies par des propriétés métriques Arnaud LABOUREL (LIS, Marseille)
Les schémas d’étiquetage sont une manière de répartir l’information d’un graphe sur ses sommets. Ils consistent en une fonction d’encodage qui attribue à chaque sommet d’un graphe G une étiquette binaire, et une fonction de décodage qui calcule le résultat d’une requête entre deux sommets en utilisant seulement leurs étiquettes. Dans notre cas nous allons nous intéresser à des requêtes de distance et donc la fonction de décodage devra calculer la distance (ou une approximation de celle-ci) entre les deux sommets à partir de leurs étiquettes. Nous nous intéressons à de tels schémas pour deux familles importantes de la théorie métrique des graphes: les graphes médians et les graphes pontés. Les graphes médians sont les graphes tels que pour tout triplet de sommet l'intersection de tous les plus courts chemins possibles entre deux sommets du triplet consiste en un unique sommet. Je vous présenterai un schéma de distance pour la sous-famille des graphes médians qui ne contiennent pas de cube, utilisant des étiquettes de O(log^3 n) où n est le nombre de sommets des graphes. 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 présenterai un schéma de distance 4-approchée (donnant une approximation de la distance comprise en une fois et quatre fois celle-ci) utilisant des techniques similaires à celui des graphes médians. C’est un travail effectué en collaboration avec Victor Chepoi et Sébastien Ratel.

Details to be posted there: https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

Lundi 14 septembre : Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints Jason SCHOETERS (LaBRI, Bordeaux)
We study a new version of the Euclidean TSP called VectorTSP (VTSP for short) where a mobile entity is allowed to move according to a set of physical constraints inspired from the pen-and-pencil game Racetrack (also known as Vector Racer). The spirit of this model is that no speed limitations apply and inertia depends on the current velocity. As such, this model is closer to typical models considered in path planning problems, although applied here to the visit of n cities in a non-predetermined order. In this work, we motivate and introduce VectorTSP and discuss some fundamental differences between this problem and other versions of TSP. This is joint work with Arnaud Casteigts and Mathieu Raffinot.

Details to be posted there: https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

Lundi 15 juin : Distributed graph coloring Louis ESPERET (GSCOP, Grenoble)
All the details are here: https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

Lundi 22 juin : Dynamic graphs and connectivity Mathilde Vernet (LITIS, Le Havre)
Connectivity in graphs is a well known issue, relevant to many applications. In the classical static context, it might seem simple even though some related problems are NP-complete. But in dynamic graphs, sometimes, even the simplest questions are far from trivial. What is the equivalent of a connected component in a dynamic graph ? How to identify those components ? In addition to connectivity itself, we can look at related problems. How to extend the definition of the Steiner problem in dynamic graphs ? This talk, based on my PhD thesis with Eric Sanlaville and Yoann Pigné, will consider those questions.

The connection details are here: https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

10-12 juin : IWOCA 2020 (organized by our group)
The registration is free of charge. See the details here: https://iwoca2020.labri.fr/

Lundi 6 avril : Computing Maximum Matchings in Temporal Graphs Hendrik Molter (TU, Berlin)
Résumé : Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e, t) such that no vertex is matched more than once within any time window of ∆ consecutive time slots, where ∆ ∈ N is given. The requirement that a vertex cannot be matched twice in any ∆-window models some necessary “recovery” period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.

Based on joint work with George B. Mertzios, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche.

La vidéo de l'exposé est disponible sur le serveur Mediapod de l'Université : https://mediapod.u-bordeaux.fr/video/6559-computing-maximum-matchings-in-temporal-graphs/

Lundi 30 mars : An Algorithmic Theory of Brain Networks Nancy Lynch (MIT, Boston) - vidéo synchro.
Résumé : This talk will describe my recent work with Cameron Musco and Merav Parter, on studying neural networks from the perspective of the field of Distributed Algorithms. In our project, we aim both to obtain interesting, elegant theoretical results, and also to draw relevant biological conclusions.

GT via Zoom, plus d'informations : https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

Lundi 23 mars : CANCELED Spatio-temporal modelling of urban road traffic Kamaldeep Singh OBEROI (LITIS, Rouen)
Résumé : TBA

Lundi 17 février : The excitement of physicists about active matter Thomas Barois (LOMA, U. Bordeaux)
Résumé : "Active matter" is a topic that knew a burst around 2010 in the physics community. Although there is no official definition of active matter, it generally refers to a situation with an ensemble of self-moving elements in interaction. The main motivation of this topic was to mimic the collective behaviour of animals such as birds flocks (nuées) of fish school (bancs) by minimal physical models.

In this talk, I will first discuss few models and notably the Vicsek model (1995) that gives a good insight of what active matter is. I will try and explain why physicists are interested in these types of models of active matter as opposed to a more conventionnal "passive" matter (the traditional atoms/molecules organizing in solid/fluid/gas).

In the second part of the talk, I will discuss more specifically the experimental systems we are using here in Bordeaux to study collective effects such as agregation, cooperative effects or traffic jams.

Lundi 27 janvier : Atelier démo/formation JBotSim Rémi Laplace (LaBRI)
Résumé : JBotSim [1] est une bibliothèque de simulation d'algorithmes pour réseaux dynamiques (entre autres). Il s'agit d'un logiciel libre porté par les membres du thème Algorithmique Distribuée du LaBRI et développé en Java.

Rémi Laplace, l'ingénieur de recherche SysNum chargé de son développement et sa maintenance depuis 18 mois, vous propose une séance atelier en deux parties et sur deux heures (il n'est pas obligatoire de rester les deux heures). La première partie servira d'introduction à JBotSim, montrant les différents contextes dans lesquels cet outil peut être utilisé, notamment par le biais d'exemples simples. Pendant la seconde partie, plus orientée TP, vous pourrez vous familiariser avec JBotSim et nous pourrons, le cas échéant, travailler ensemble sur vos problématiques de recherche.

À cet effet, il serait idéal :

d'apporter votre ordinateur pour pouvoir travailler de votre côté
- (bonus) avoir l'environnement de développement IntelliJ IDEA déjà installé vous fera gagner du temps [2]
nous contacter en avance [3] pour nous faire part d'idées ou d'algorithmes éventuels à implémenter ensemble

[1]: https://jbotsim.io/ [2]: https://www.jetbrains.com/fr-fr/idea/ [3]: contact@jbotsim.io (Arnaud Casteigts et Rémi Laplace)

Lundi 13 janvier : Trade-offs in Distributed Interactive Proofs Pierluigi Crescenzi (IRIF)
Résumé : The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of sequential interactive proofs theory, we study the power of distributed interactive proofs. This is achieved via a series of results establishing trade-offs between various parameters impacting the power of interactive proofs, including the number of interactions, the certificate size, the communication complexity, and the form of randomness used. Our results also connect distributed interactive proofs with the established field of distributed verification. In general, our results contribute to providing structure to the landscape of distributed interactive proofs. This is a joint work with Pierre Fraigniaud and Ami Paz.

Lundi 6 janvier (15h) : Bellman-Ford sous stéroïdes : Un algorithme de routage pour l'établissement automatique des tunnels (partie 2, l'algorithme) 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.

2019

Lundi 2 décembre : Approximation algorithm for estimating distances in Distributed Virtual Environments Tobias Castanet (LaBRI)
Résumé : We deal with the issue of guaranteeing properties in Distributed Virtual Environments (DVEs) without a server and without global knowledge of the system state and therefore only by exchanging messages. This issue is particularly relevant in the case of online games, that operate in a fully distributed framework and for which network resources such as bandwidth are the critical resources. In the context of games, players typically need to know the distance between their character and other characters, at least approximately. Players all share the same position estimation algorithm but, in general, do not know the current positions of others. We provide a synchronized distributed algorithm Alc to guarantee, at any time, that the estimated distance between any pair of characters A and B is always a 1 + ε approximation of the current distance. Our result is twofold: (1) we prove that if characters move randomly in a 1 dimensional grid, the number of messages of Alc is optimal up to a constant factor; (2) in a more general and practical setting, we also observe that the number of messages of Alc for actual game traces is much less than the standard algorithm sending actual positions at a given frequency.

Lundi 25 novembre : Bellman-Ford sous stéroïdes : Un algorithme de routage pour l'établissement automatique des tunnels (partie 1, le problème) 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.

Lundi 21 octobre : Overcoming interference in the beeping communication model Fabien Dufoulon (LRI)
Résumé : 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 work, we are interested in studying 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). Simultaneous communications (i.e., collisions) result in non-destructive interference: a node with two or more neighbors beeping simultaneously detects a beep.

Its simple, general and energy efficient communication mechanism makes the beeping model widely applicable. However, that simplicity comes at a cost. Due to the poor expressiveness of beeps and the interference caused by simultaneous communications, algorithm design is challenging. Throughout this work, we overcome both difficulties in order to provide efficient communication primitives. More precisely, we provide solutions for the two following fundamental problems: leader election and 2-hop desynchronization.

Lundi 7 octobre : Lower bounds for maximal matchings and maximal independent sets Mikaël Rabie (LIP6)
Abstract : There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log*n) communication rounds; here n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log*n) rounds even if Δ = 2. However, the dependency on Δ is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. In this presentation, I will first provide previous results on the bounds depending in n, before providing the tools and ideas we used for the case of Delta dependency.

Lundi 30 septembre : Tractable reliable communication in static and dynamic compromised networks. Giovanni Farina (LIP6)
Abstract : Many solutions to fault tolerant distributed system problems, such as state machine replication, safe broadcast or agreement, rely on reliable communication primitives which ensure the correct messages exchange between processes even in case of failures, guaranteeing their authorship and delivery. Although considering quite strong system assumptions (a highly connected communication network, digitally signed messages, the knowledge on the communication network topology) a reliable communication primitive can be efficiently implemented, especially under the message complexity point of view, it may become intractable to provide under the weaker and more general assumptions of an unknown and/or dynamic communication network. In this talk, we review and improve the state-of-art solutions implementing Byzantine fault tolerant reliable communication in multi-hop networks and we discuss their possible employment on dynamic networks.

Lundi 1 juillet 2019 : Wireless Broadcast with short labelling Gewu Bu (LIP6)
Résumé : We talk about the broadcast problem in wireless networks when the broadcast is helped by a labelling scheme. We focus on two variants of broadcast: broadcast without acknowledgement (i.e. the initiator of the broadcast is not notified at the end of broadcast) and broadcast with acknowledgement. Our contribution is twofold. First, we propose label optimal broadcast algorithms in a class of networks issued from recent studies in Wireless Body Area Networks then we extend our solutions to arbitrary networks. We propose an acknowledgement-free broadcast strategy using 1-bit labels and broadcast with acknowledgement using 2-bits labels. In the class of level-separable networks our algorithms finish within 2D rounds for both broadcast with and without acknowledgement, where D is the eccentricity of the broadcast initiator. Second, we improve a recent labelling-based broadcast scheme with acknowledgement designed for arbitrary networks in terms of memory complexity.

Lundi 3 juin 2019 : Long-lived Counters with polylog amortized step complexity. Ahad Mirza Baig, Chennai Mathematical Institute
Résumé : A shared counter is a widely-used concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. Jayanti,Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of concurrent objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. We answer this question by providing a wait-free counter implementation that uses only read and write operations, and whose amortized step complexity is polylogarithmic in all executions. In this talk, I will present the proposed algorithm. I would also briefly discuss other approaches to circumvent the lower-bound, especially, limited-use concurrent objects.

Lundi 27 mai 2019 : Soyez Efficace, Rembobinez Colette Johnen, LaBRI
Résumé : Nous proposons un algorithme, appelé SDR, qui réinitialise de manière auto-stabilisante et totalement distribuée un réseau anonyme, lorsque c’est nécessaire, c’est à dire que chaque processus, détectant localement une anomalie, peut déclencher une réinitialisation. SDR est coopératif au sens où il coordonne les réinitialisations concurrentes afin de gagner en efficacité. Nous utilisons SDR pour rendre auto-stabilisant des algorithmes distribués. Notre approche permet de résoudre efficacement à la fois les problèmes statiques et dynamiques, comme le montrent les deux exemples d’algorithme utilisant SDR que nous proposons. En effet, nous avons, tout d’abord, conçu un algorithme auto-stabilisant silencieux calculant une (f, g)-alliance 1-minimale dans les réseaux identifiés. Aucun algorithme auto-stabilisant ne résolvait auparavant ce problème sans aucune restriction sur f et g. Nous avons ensuite proposé un algorithme auto-stabilisant d’unisson. Ce dernier stabilise en O(n) rondes et O(Dn^2) mouvements (D est le diamètre et n est le nombre de processus dans le réseau). Par rapport aux algorithmes précédents, notre algorithme améliore le temps de stabilisation en mouvements sans pénalité sur le temps de stabilisation en rondes, ni l’espace mémoire utilisé.

(Travail commun avec S. Devismes.)

Lundi 13 mai 2019 : On the Approximabilty of Hub Allocation Problems Ralf Klasing, LaBRI
Résumé : Given a metric graph G = (V, E, w), a center c ∈ V, and an integer p, the Star p-Hub Center Problem is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children and the diameter of T is minimized. The children of c in T are called hubs. A similar problem called the Single Allocation p-Hub Center Problem is to find a spanning subgraph H* of G such that (i) C* is a clique of size p in H*; (ii) V \ C* forms an independent set in H*; (iii) each v ∈ V \ C* is adjacent to exactly one vertex in C*; and (iv) the diameter D(H*) is minimized. The vertices selected in C* are called hubs and the rest of the vertices are called non-hubs. Both Star p-Hub Center Problem and Single Allocation p-Hub Center Problem are NP-hard and have applications in transportation systems, telecommunication systems, and post mail systems. In this talk, I will present 5/3-approximation algorithms for both problems. Moreover, I will show that for any ε > 0, both problems have no (1.5 − ε)-approximation algorithm unless P=NP. If the input graph G is a Δβ-metric, for some β ≥ 1/2 (i.e., G satisfies the β-triangle inequality: w(u, v)≤β(w(u, x)+w(x, v)) for all vertices u, v, x ∈ V), we can further show that for any ε > 0, to approximate the two hub allocation problems to a ratio g(β)−ε is NP-hard and we give r(β)-approximation algorithms where g(β) and r(β) are functions of β.

Jeudi 18 et vendredi 19 avril 2019 : Vérification of Distributed Algorithms Javier Esparza, TU München
(18 après midi : 14:00-15:30 + 16:00-17:30; 19 matin : 9:00-10:30 + 11:00-12:30) -- Amphi du LaBRI

Résumé : Many distributed algorithms should be correct independently of the number of processes executing them. Examples include algorithms for mutual exclusion, leader election, distributed termination, distributed consensus, reliable broadcast, etc. We say that these systems are parametric in the number of processes, and call them parameterized systems. When the number of processes is fixed, many parameterized systems have a finite state space, and their correctness can be automatically analyzed using e.g. model-checking techniques. The challenge of parameterized verifciation is to automatically prove correctness for any number of processes. It amounts to proving that each member of an infinite family of finite-state systems is correct. Population protocols are a model of computation very much studied by the distributed systems community. They are used to describe and analyze algorithms able to run in arbitrary networks of unknown topology. The goal of a protocol is that all processes learn some information about the initial configuration of the network. Population protocols are a great testbed for parameterized verification techniques. In the course we will introduce them, discuss their expressive power, and analyze the theory and practice of proving them correct. The lectures will make extensive use of Peregrine, a tool for the simulation, analysis and verification of population protocols.

Lundi 15 avril 2019 : Circulation de jeton et réseaux dynamiques Devan Sohier, UVSQ
Résumé : Le recours à des marches aléatoires pour parcourir un système réparti permet de ne faire aucune hypothèse sur sa topologie. Ce mécanisme est robuste aux changements topologiques, mais le rendre auto-stabilisant nécessite de mettre en place des mécanismes globaux, qui eux sont sensibles aux changements topologiques. On est alors amené à chercher un compromis entre la vitesse à laquelle on corrige l’absence d’un jeton et le coût du mécanisme de correction. Ce compromis se modélise sous forme d’un problème d’optimisation, faisant intervenir les caractéristiques stochastiques du système (probabilité d’erreur, vitesse de transmission d’un message…) En faisant apparaître ces caractéristiques, on est en mesure reformuler le problème initial comme un problème d’optimisation sous incertitudes, que l’on peut résoudre par des heuristiques bayésiennes. Au prix de la relaxation de la contrainte de clôture de l’auto-stabilisation, on peut alors appliquer ces travaux à des réseaux anonymes, asynchrones (en un sens stochastique). Ce même type de raisonnement est également appliqué au problème de la recherche de plus courts chemins, dans le cadre d’un algorithme inspiré par les propriétés d’une moisissure, le Physarum.

Lundi 8 avril 2019 : Renaming Algorithms Corentin Travers (LaBRI)
Renaming is one of the canonical task in distributed computing. In the renaming task, a set of processes have to pick unique names in a small namespace. Despite its simple specification, elegant algorithms and sophisticated lower bounds have been discovered. The talk will review some of these results.

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 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 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.

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.

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.

2018

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.