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 faulttolerant 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 faulttolerance 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 linearinDelta 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 failureprone messagepassing 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 inverseAckermann 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 failurefree messagepassing 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 crashprone 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 crashprone messagepassing system, and build then snapshot objects on top of it. This paper presents algorithms building snapshot objects directly on top of an asynchronous crashprone messagepassing 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 selfstabilizing algorithms using the proof assistant Coq. We first define in Coq one of the most commonly used computational model in the selfstabilizing area. We then illustrate the use of our framework by: (1) certifying a nontrivial part of an existing selfstabilizing algorithm; and (2) certifying a commonlyused composition operation for selfstabilizing 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 faulttolerant 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 messagepassing 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 $(k1)$set agreement. This impossibility result can be circumvented by using stronger communication primitives. A wellknown messagebased primitive is TotalOrder 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 1set agreement (also called consensus). A recent result determined that SCDBroadcast, a weaker messagebased primitive, is equivalent to a shared memory and thus does not allow to solve set agreement. This talk will present the $k$SCDBroadcast messagebased 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
Prooflabeling 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. Prooflabeling schemes are
typically designed for enforcing faulttolerance, 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
errorsensitive prooflabeling schemes. These are prooflabeling
schemes which guarantee that the number of nodes detecting illegal
states is linearly proportional to the editdistance between the
current state and the set of legal states. By using errorsensitive
prooflabeling 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
errorsensitive prooflabeling schemes. This characterization allows
us to show that classical predicates such as, e.g., acyclicity, and
leader admit errorsensitive prooflabeling schemes, while others like
regular subgraphs don't. We also focus on compact errorsensitive
prooflabeling schemes. In particular, we show that the known
prooflabeling schemes for spanning tree and minimum spanning tree,
using certificates on $O(\log{n})$ bits, and on $O(\log^2{n})$ bits,
respectively, are errorsensitive, 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 nonnegative weight function, and the considered objective is to minimize the total query cost for a worstcase choice of the target. Designing an optimal strategy for a weighted tree search instance is known to be strongly NPhard, we'd like to present our new approximation algorithm for weighted cases.

11h 
The goal of a hubbased 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 shortestpath 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