Programme
Mercredi 28 mars
- 10h00 - Accueil
-
10h20 - (IRIF)
When considering distributed computing, reliable message-passing synchronous systems on the one side, and asynchronous failure-prone shared-memory systems on tyhe other side, remain two quite independently studied ends of the reliability/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of wait-freedom is central to the second one. The paper proposes a new DECOUPLED model in an attempt to reconcile these two worlds. It consists of a synchronous and reliable communication graph of n nodes, and on top a set of asynchronous crash-prone processes, each attached to a communication node. To illustrate the DECOUPLED model, the paper presents an asynchronous 3-coloring algorithm for the processes of a ring. From the processes point of view, the algorithm is wait-free. From a locality point of view, each process uses information only from processes at distance $O(\log^∗{n})$ from it. This local wait-free algorithm is based on an extension of the classical Cole and Vishkin vertex coloring algorithm in which the processes are not required to start simultaneously. This is joint work with Armando Castañeda, Carole Delporte, Hugues Fauconnier, Sergio Rajsbaum, Michel Raynal.
-
11h00 - (LaBRI)
Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids. This is joint work with Marthe Bonamy, Mikaël Rabie, Jukka Suomela and Jara Uitto.
-
11h40 - (LaBRI)
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(\log{n})$ 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.
- 12h20 - Déjeuner
-
14h00 - (Vérimag)
We propose a general scheme, called Algorithm $A$, to compute spanning-tree-like data structures on arbitrary networks. $A$ is self-stabilizing and silent and, despite its generality, is also efficient. It is written in the locally shared memory model with composite atomicity, assuming the distributed unfair daemon, the weakest scheduling assumption of the model. Its stabilization time is at most $4 nmax$ rounds, where $nmax$ is the maximum number of processes in a connected component. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves holding for large classes of instantiations of Algorithm $A$. We illustrate the versatility of our approach by proposing several such instantiations that efficiently solve classical problems such as leader election, and unconstrained and shortest-path spanning tree constructions.
-
14h40 - (LaBRI)
In road networks, shortest path problem has already been intensively studied and answered in a convincing way. However, people may prefer other transportation means than cars. This leads to a more general problem that is to take into account individual preferences. We want to answer a shortest path query by allowing the use of several kind of transportation and taking into account several parameters other than time. We will talk about difficulties and solutions added by this generalisation.
-
14h50 - (IRIF)
Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on data-structures distributed over the nodes (e.g., spanning trees or routing tables). We consider mechanisms consisting of two components: a prover assigning a certificate to each node, and a distributed algorithm called verifier that is in charge of verifying the distributed proof formed by the collection of all certificates. In this talk, we show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs for establishing perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol. If we allow every node to communicate to distance at most $t$, one might expect that the certificate sizes can be reduced by a multiplicative factor of at least $t$. In trees, cycles and grids, we show that such tradeoffs can be established for all network predicates, i.e., it is always possible to linearly decrease the certificate size. In arbitrary graphs, we show that any part of the certificates common to all nodes can be evenly redistributed among these nodes, achieving even a better tradeoff: this common part of the certificate can be reduced by the size of a smallest ball of radius $t$ in the network. In addition to these general results, we establish several upper and lower bounds on the certificate sizes used for distributed proofs for spanning trees, minimum-weight spanning trees, diameter, additive and multiplicative spanners, and more, improving and generalizing previous results from the literature. This is joint work with Pierre Fraigniaud, Juho Hirvonen, Ami Paz and Mor Perry.
- 15h30 - Pause
-
15h50 - (IRIF)
We demonstrates that the Preferential Attachment rule naturally emerges in the context of evolutionary network formation, as the unique Nash equilibrium of a simple social network game. In this game, each node aims at maximizing its degree in the future, representing its social capital in the “society” formed by the nodes and their connections. This result provides additional formal support to the commonly used Preferential Attachment model, initially designed to capture the “rich get richer” aphorism. This is joint work with Chen Avin, Avi Cohen, Zvi Lotker, and David Peleg, to appear in WWW 2018.
- 16h30 - Discussions
- 17h00 - Fin de la réunion
Organisateurs
 |
 |
 |