Programme
Mercredi 9 octobre
- 10h30 - Accueil
-
11h00 - (IRIF)
We consider the problem of synthesizing distributed algorithms working on a specific execution context. We show it is possible to use the linear time temporal logic in order to both specify the correctness of algorithms and their execution contexts. We then provide a method allowing to reduce the synthesis problem of finite state algorithms to some model-checking problems. We finally apply our technique to automatically generate algorithms for consensus and epsilon-agreement in the case of two processes using the SMT solver Z3. This is a joint work with Carole Delporte, Hugues Fauconnier, François Laroussinie and Yan Jurski.
-
11h30 - (LIS)
The notion of an anonymous shared memory (recently introduced in PODC 2017) considers that processes use different names for the same memory location. As an example, a location name $A$ used by a process $p$ and a location name $B\neq A$ used by another process $q$ can correspond to the very same memory location $X$, and similarly for the names $B$ used by $p$ and $A$ used by $q$ which may (or may not) correspond to the same memory location $Y\neq X$. Hence, there is permanent disagreement on the location names among processes. In this context, the PODC paper presented -- among other results -- a symmetric deadlock-free mutual exclusion (mutex) algorithm for two processes and a necessary condition on the size $m$ of the anonymous memory for the existence of a symmetric deadlock-free mutex algorithm in an $n$-process system. This condition states that $m$ must be greater than $1$ and belong to the set $M(n) = \{m: \forall~ \ell: 1<\ell \leq n:~ \gcd(\ell,m)=1\}$ (symmetric means that, while each process has its own identity, process identities can only be compared with equality). This talk will present two algorithms that consider that the registers are anonymous read/write atomic registers, and that work for any $m$ greater than $1$ and belonging to the set $M(n)$. Hence, this condition on $m$ is both necessary and sufficient. The talk will also show that the condition $m\in M(n)$ is necessary for deadlock-free mutex on top of anonymous read/modify/write atomic registers. It follows that, when $m>1$, $m\in M(n)$ is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the anonymous registers read/write or read/modify/write. This is a joint work with Zahra Aghazadeh, Michel Raynal, Gadi Taubenfeld and Philipp Woelfel.
- 12h00 - Déjeuner
- 14h00 - (IRISA)
Most recent CRDT techniques rely on a causal broadcast primitive to provide guarantees on the delivery of operation deltas. Such a primitive is unfortunately hard to implement efficiently in large open networks, whose membership is often difficult to track. As an alternative, we argue in this paper that pure state-based CRDTs can be efficiently implemented by encoding states as specialized Merkle trees, and that this approach is well suited to open networks where many nodes may join and leave. At the core of our contribution lies a new kind of Merkle tree, called Merkle Search Tree (MST), that implements a balanced search tree while maintaining key ordering. This latter property makes it particularly efficient in the case of updates on sets of sequential keys, a common occurrence in many applications. We use this new data structure to implement a distributed event store, and show its efficiency in very large systems with low rates of updates. In particular, we show that in some scenarios our approach is able to achieve both a 66% reduction of bandwidth cost over a vector-clock approach, as well as a 34% improvement in consistency level. We finally suggest other uses of our construction for distributed databases in open networks. This is a joint work with Michel Raynal and François Taïani.
-
14h30 - (LaBRI)
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 garantee, 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. This is a joint work with Olivier Beaumont, Nicolas Hanusse and Corentin Travers.
-
15h00 - (IRIF)
A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. An important class of distance labeling schemes is that of hub labelings, where a node $v \in G$ stores its distance to the so-called hubs $S_v \subseteq V$, chosen so that for any $u,v \in V$ there is $w \in S_u \cap S_v$ belonging to some shortest $uv$ path. Notice that for most existing graph classes, the best distance labelling constructions existing use at some point a hub labeling scheme at least as a key building block. Our interest lies in hub labelings of sparse graphs, i.e., those with $|E(G)| = O(n)$, for which we show a lower bound of $n/2^{O(\sqrt{\log n})}$ for the average size of the hubsets. Additionally, we show a hub-labeling construction for sparse graphs of average size $O(n/\mathrm{RS}(n)^{c})$ for some $0 < c < 1$, where RS$(n)$ is the so-called Ruzsa-Szemerédi function, linked to structure of induced matchings in dense graphs. This implies that further improving the lower bound on hub labeling size to $n/2^{(\log n)^{o(1)}}$ would require a breakthrough in the study of lower bounds on RS$(n)$, which have resisted substantial improvement in the last 70 years. For general distance labeling of sparse graphs, we show a lower bound of $\mathrm{SumIndex}(n)/2^{O(\sqrt{\log n})}$, where $\mathrm{SumIndex}(n)$ is the communication complexity of the Sum-Index problem over $Z_n$. Our results suggest that the best achievable hub-label size and distance-label size in sparse graphs may be $\Theta(n/2^{(\log n)^c})$ for some $0 < c < 1$. This is joint work with Adrian Kosowski and Przemyslaw Uznanski.
- 15h30 - Pause
- 16h00 - (LIS)
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 simultaneous 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. This is a joint work with Eloi Perdereau.
- 16h30 - Discussions sur le futur de DESCARTES
- 17h30 - Fin de la 1ère journée
Jeudi 10 octobre
- 9h15 - Accueil
-
9h30 - (IRIF)
This talk will introduce the audience with interactive proofs in the context of distributed network computing, and survey some of recent results, including the existence of various tradeoffs between different parameters like size of the proofs, number of interactions, message size, etc. This is a joint work with Pierluigi Crescenzi and Ami Paz.
-
10h00 - (Vérimag)
We initiate research on self-stabilization in highly dynamic message-passing systems. We first reformulate the definition of self-stabilization to accommodate with the highly dynamic context. Then, we propose self-stabilizing leader election algorithms for three wide classes of TVGs: the class TCB$(\Delta)$ of TVGs with temporal diameter bounded by $\Delta$, the class TCQ$(\Delta)$ of TVGs with temporal diameter quasi-bounded by Delta, and the class TCR of TVGs with recurrent connectivity, where TCB$(\Delta)$ is included in TCQ$(\Delta)$ and TCQ$(\Delta)$ in included in TCR. In more detail, we present three self-stabilizing leader election algorithms for Classes TCB$(\Delta)$, TCQ$(\Delta)$, and TCR, respectively. The first one stabilizes in at most 3Delta rounds; the stabilization time of the two others cannot be bounded in general, however we exhibit small time complexity bounds holding for them in more favorable cases, meaning that these solutions are speculative. Precisely, in Class TCQ$(\Delta)$, both algorithms stabilize in $O(\Delta)$ rounds. This is a joint work with Colette Johnen, Franck Petit, Karine Altisen, and Anaïs Durand.
- 10h30 - Pause 11h00 - (LIP6)
-
11h30 - (IRISA)
The atomic register is one of the most basic and useful object of computing science, and its simple read-write semantics is appealing when programming distributed systems. Hence, its implementation on top of crash-prone asynchronous message-passing systems has received a lot of attention. It was shown that having a strict minority of processes that may crash is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous message-passing system. This talk visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm that reduces latency in many cases: a write operation always costs a round-trip delay, while a read operation costs a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the original algorithm proposed by Attiya, Bar-Noy, and Dolev. This is a joint work with Achour Mostéfaoui.
- 12h00 - Déjeuner
- 14h00 - (IRIF)
Centrality metrics play a central role in many problems related to network analysis. Betweenness centrality, in particular, is one of the most popular and well-studied centrality metric. In this talk, we present a fast and simple distributed algorithm to compute betweenness centrality. We prove its convergence and we show it is directly applicable, with minimal modifications, to any distance-vector routing protocol based on Bellman-Ford. This is a joint work with Pierre Fraigniaud and Ami Paz.
- 14h30 - (LaBRI)
A shared-memory counter is a well-studied and widely-used concurrent object. It supports an Inc operation that increases its value by 1 and a Read operation that returns its current value. It is well known that any $n$-processes implementation of counters from read and write operations has linear worst case complexity, even if only a weak form of liveness is guaranteed (e.g., obstruction-freedom). This lower bound however does not give any indication on how counter implementations perform globally. In this talk, we show that indeed efficient counter implementation do exist if we consider instead of the individual worst-case step complexity, the total work total work incurred by performing several operations in the worst case. Specifically, we present the first wait-free $n$-processes counter, implemented using only read and write operations, whose amortized operation step complexity is $O(\log^2{n})$ in all executions. This is a joint work with Ahad Mirza Baig, Danny Hendler and Alessia Milani.
- 15h00 - Discussions sur la prochaine réunion
- 15h30 - Fin de la réunion
In the context of self-stabilization, a silent algorithm
guarantees that the communication registers (a.k.a register) of
every node do not change once the algorithm has stabilized. At the
end of the 90's, Dolev et al. [Acta Inf. '99] showed that, for
finding the centers of a graph, for electing a leader, or for
constructing a spanning tree, every silent deterministic algorithm
must use a memory of $\Omega(\log n)$ bits per register in $n$-node
networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using
the notion of proof-labeling-scheme, that, for constructing a
minimum-weight spanning tree (MST), every silent algorithm must use
a memory of $\Omega(\log^2{n})$ bits per register. It follows that
requiring the algorithm to be silent has a cost in terms of memory
space, while, in the context of self-stabilization, where every node
constantly checks the states of its neighbors, the silence property
can be of limited practical interest. In fact, it is known that
relaxing this requirement results in algorithms with smaller
space-complexity.
In this talk, we are aiming at measuring how much gain in terms of
memory can be expected by using arbitrary deterministic
self-stabilizing algorithms, not necessarily silent. To our
knowledge, the only known lower bound on the memory requirement for
deterministic general algorithms, also established at the end of the
90's, is due to Beauquier et al. [PODC '99] who proved that
registers of constant size are not sufficient for leader election
algorithms. We improve this result by establishing the lower bound
$\Omega(\log\log{n})$ bits per register for deterministic
self-stabilizing algorithms solving $(\Delta+1)$-coloring, leader
election or constructing a spanning tree in networks of maximum
degree~$\Delta$.
This is a joint work with Laurent Feuilloley and Gabriel Le Bouder.