Programme
Lundi 2 octobre
- 13h - Arrivée au Château
- 13h15 - Déjeuner
-
14h30 - (LaBRI)
Ouverture
-
14h40 - (LaBRI)
Relationships between various communication models of shared memory paradigm for fault-tolerant distributed computingThere is a proliferation of communication models for distributed computing, in shared memory paradigm. Since subtle changes in the communication model can result in significant changes to the solvability/unsolvability or to the complexity of various problems, it becomes imperative to understand the relationships between the many models. The situation becomes even more complicated when additional requirements such as fault-tolerance are added to the mix. This motivates us to study under what circumstances a program designed for one model and delivering some set of additional guarantees can be converted into an "equivalent" programs for a different model while delivering comparable guarantees.
- 15h40 - (LIS)
- 16h10 - Pause
-
16h40 - (IRIF)
I will discuss recent advances in lower bound techniques for the LOCAL model. I will focus on "algorithmic" lower bounds by simulation arguments. Simulation techniques have provided both strong and simple distributed computing lower bounds in the recent years. Göös et al. (PODC 2014) used a series of simulation arguments to lift a linear-in-Delta lower bound for maximal fractional matching to the standard LOCAL model. Brandt et al. (STOC 2016) used a simulation to show that a randomized algorithm for the sinkless orientation problem implies a weaker and faster algorithm, proving a lower bound of $\Omega(\log\log n)$ rounds. Chang et al. (FOCS 2016) gave a number of different simulation results, showing for example that algorithms with certain complexities can be automatically speed up and that randomized lower bounds imply even stronger deterministic lower bounds. I will try to illustrate the core intuition of some of these proofs and give a taste of the techniques used. I will also talk about how some these results are starting to form a complexity theory of distributed graph algorithms, at least for the case of relatively sparse graphs. I want to highlight some of the major open questions, the shortcomings of our current proof techniques, and also some possible ways forward.
-
17h10 - (LaBRI)
A failure detector is a distributed oracle that provides each process with a module that continuously outputs an estimate of which processes in the system have failed. The perfect failure detector provides accurate and eventually complete information about process failures. We show that, in asynchronous failure-prone message-passing systems, perfect failure detection can be achieved by an oracle that outputs at most $⌈\log \alpha(n)⌉ + 1$ bits per process in $n$-process systems, where $\alpha$ denotes the inverse-Ackermann function. This result is essentially optimal, as we also show that, in the same environment, no failure detector outputting a constant number of bits per process can achieve perfect failure detection.
Mardi 3 octobre
-
9h - (Vérimag)
In this talk, we deal with (deterministic) leader election in unidirectional rings of homonym processes, i.e., unidirectional rings where process labels may not be unique. We study this problem assuming that processes have no a priori knowledge on the number of processes. We consider ring classes where the labeling of processes is asymmetric. We propose three algorithms for asymmetrically labeled classes where a bound $k$ on the multiplicity of labels is known, i.e., no label occurs more than $k$ times in any ring of such classes.
- 10h - Pause
- 10h30 - (IRIF)
Distributed snapshots, as introduced by Chandy and Lamport in the context of asynchronous failure-free message-passing distributed systems, are consistent global states (made up of process local states and channel states) through which the observed distributed application might have passed. It is known that two such distributed snapshots cannot necessarily be compared (in the sense of determining which one of them is the "first"). Differently, snapshots introduced in asynchronous crash-prone read/write distributed systems (made up of the state of all the shared read/write variables) are totally ordered, which greatly simplify their use by upper layer applications. In order to benefit from shared memory snapshot objects, it is possible to simulate a read/write shared memory on top of an asynchronous crash-prone message-passing system, and build then snapshot objects on top of it. This paper presents algorithms building snapshot objects directly on top of an asynchronous crash-prone message-passing system. "Directly" means here "without building an intermediate layer such as a read/write shared memory". To the authors knowledge, the proposed algorithms are the first providing such constructions. Interestingly enough, these algorithms are more efficient than the indirect solution, yet relatively simple. Joint work with Hugues Fauconnier, Sergio Rajsbaum and Michel Raynal.
-
11h - (Vérimag)
We present the PADEC framework that builds certified proofs of self-stabilizing algorithms using the proof assistant Coq. We first define in Coq one of the most commonly used computational model in the self-stabilizing area. We then illustrate the use of our framework by: (1) certifying a non-trivial part of an existing self-stabilizing algorithm; and (2) certifying a commonly-used composition operation for self-stabilizing algorithms.
-
11h30 - (IRIF)
We will survey the relations between three classic models of distributed computing: the local model, the congest model, and the congested clique model. We will then outline two links between the congested clique model, and two other computational models. The first is a reduction from Boolean circuits, which sheds some light on the inability to prove lower bounds for the congested clique. The second is an adaptation of parallel matrix multiplication algorithms to the congested clique, a result which allows fast distance computation and triangle detection.
- 12h15 - Déjeuner
-
14h30 - (LIS)
In fault-tolerant distributed computing, computability is a core issue. A fundamental result is that, in an asynchronous system in which any number of processes can crash, and in which these processes communicate either by message-passing or through a shared memory, set agreement (agreeing on a strict subset of the input values) is impossible. Moreover, adding a black box that solves $k$-set agreement (agreeing on at most $k < n$ different values) does not allow to solve $(k-1)$-set agreement. This impossibility result can be circumvented by using stronger communication primitives. A well-known message-based primitive is Total-Order broadcast, which delivers messages in the same order at every process. From a computability point of view, it is equivalent to a shared memory augmented with 1-set agreement (also called consensus). A recent result determined that SCD-Broadcast, a weaker message-based primitive, is equivalent to a shared memory and thus does not allow to solve set agreement. This talk will present the $k$-SCD-Broadcast message-based primitive that lies between these two extremes, and will show that it is equivalent to a shared memory augmented with $k$-set agreement.
- 15h -
- 15h30 - Pause
-
16h -
On s'intéresse au problème suivant: Alice souhaite communiquer un message confidentiel à Bob, et dispose pour cela de $n=2t+1$ canaux parallèles, dont $t$, on ne sait pas lesquels, sont contrôlés par un adversaire, qui peut lire et modifier tout symbole transmis sur ces canaux. On s'intéresse au nombre minimum de symboles qu'il est nécessaire de transmettre pour faire parvenir au destinataire un message secret, de manière inconditionnellement sûre. Ce problème, connu sous l'appellation "Perfectly Secure Message Transmission", a été proposé par Dolev et al. en 1993: nous présenterons quelques développements récents.
-
16h30 -
In 2009, Gavoille, Kosowki and Markiewicz introduced the physical local ($\phi$-local) model as a way to simplify the task of finding lower bounds on distributed graph algorithms where making use of the possibilities offered by quantum information is allowed. In this talk, we recall this model and we go over recent results by Holroyd and Liggett in probability theory and their significance for the colouring problem in the $\phi$-local model. Some original results pertaining to the adequation of the $\phi$-local model and the probabilistic model are also presented. In particular, we show that Holroyd and Liggett's result for the path graph is more or less optimal.
- 17h15 - Business Meeting
Proof-labeling schemes are known mechanisms
providing nodes of networks with certificates that can be verified
locally by distributed algorithms. Given a boolean predicate on
network states, such schemes enable to check whether the predicate is
satisfied by the actual state of the network, by having nodes
interacting with their neighbors only. Proof-labeling schemes are
typically designed for enforcing fault-tolerance, by making sure that
if the current state of the network is illegal with respect to some
given predicate, then at least one node will detect it. Such a node
can raise an alarm, or launch a recovery procedure enabling the system
to return to a legal state. In this paper, we introduce
error-sensitive proof-labeling schemes. These are proof-labeling
schemes which guarantee that the number of nodes detecting illegal
states is linearly proportional to the edit-distance between the
current state and the set of legal states. By using error-sensitive
proof-labeling schemes, states which are far from satisfying the
predicate will be detected by many nodes, enabling fast return to
legality. We provide a structural characterization of the set of
boolean predicates on network states for which there exist
error-sensitive proof-labeling schemes. This characterization allows
us to show that classical predicates such as, e.g., acyclicity, and
leader admit error-sensitive proof-labeling schemes, while others like
regular subgraphs don't. We also focus on compact error-sensitive
proof-labeling schemes. In particular, we show that the known
proof-labeling schemes for spanning tree and minimum spanning tree,
using certificates on $O(\log{n})$ bits, and on $O(\log^2{n})$ bits,
respectively, are error-sensitive, as long as the trees are locally
represented by adjacency lists, and not just by parent pointers.
Mercredi 4 octobre
- 9h -
- 10h - Pause
-
10h30 -
We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node $t$ in a given tree $T$. Upon querying a node $v$ of the tree, the strategy receives as a reply an indication of the connected component of $T\setminus\{v\}$ containing the target $t$. The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total query cost for a worst-case choice of the target. Designing an optimal strategy for a weighted tree search instance is known to be strongly NP-hard, we'd like to present our new approximation algorithm for weighted cases.
-
11h -
The goal of a hub-based distance labeling scheme for a network $G=(V,E)$ is to assign a small subset $S(u) \subseteq V$ to each node $u\in V$, in such a way that for any pair of nodes $u,v$, the intersection of hub sets $S(u) \cap S(v)$ contains a node on the shortest $uv$-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least $r$ intersecting a given ball of radius $2r$. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.
- 11h30 - Discussions
- 12h - Déjeuner
- 13h15 - Départ