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 modelchecking problems. We finally apply our technique to automatically generate algorithms for consensus and epsilonagreement 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 deadlockfree 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 deadlockfree 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 deadlockfree 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 deadlockfree 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 statebased 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 vectorclock 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 bitlabels 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 socalled 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 hublabeling construction for sparse graphs of average size $O(n/\mathrm{RS}(n)^{c})$ for some $0 < c < 1$, where RS$(n)$ is the socalled RuzsaSzemeré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 SumIndex problem over $Z_n$. Our results suggest that the best achievable hublabel size and distancelabel 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 selfstabilization in highly dynamic messagepassing systems. We first reformulate the definition of selfstabilization to accommodate with the highly dynamic context. Then, we propose selfstabilizing 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 quasibounded 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 selfstabilizing 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 readwrite semantics is appealing when programming distributed systems. Hence, its implementation on top of crashprone asynchronous messagepassing 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 crashprone asynchronous messagepassing system. This talk visits the notion of a fast implementation of an atomic register, and presents a new timeefficient asynchronous algorithm that reduces latency in many cases: a write operation always costs a roundtrip delay, while a read operation costs a roundtrip 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, BarNoy, 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 wellstudied 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 distancevector routing protocol based on BellmanFord. This is a joint work with Pierre Fraigniaud and Ami Paz.
 14h30  (LaBRI)
A sharedmemory counter is a wellstudied and widelyused 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., obstructionfreedom). 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 worstcase step complexity, the total work total work incurred by performing several operations in the worst case. Specifically, we present the first waitfree $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 selfstabilization, 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 prooflabelingscheme, that, for constructing a
minimumweight 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 selfstabilization, 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
spacecomplexity.
In this talk, we are aiming at measuring how much gain in terms of
memory can be expected by using arbitrary deterministic
selfstabilizing 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
selfstabilizing 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.