Lundi 1er octobre
- 10h00 - Accueil
10h20 - (IRIF)
Cet exposé présente les détecteurs de défaillances et les principaux résultats les concernant.
11h00 - (IRISA)
This talk is an algorithmic introduction to anonymity in asynchronous systems where processes communicate by reading and writing atomic read/write registers. Two types of anonymity are investigated: process-anonymity and memory-anonymity. Process-anonymity is when the processes cannot be distinguished the ones from the others (among other features, they do not have identifiers). Memory-anonymity is when the same memory locations can have different names at different processes (e.g., the location name $A$ used by process $p_i$ and the location name $B$ used by another process $p_j$ can correspond to the very same memory location $X$, and similarly for the names $B$ at $p_i$ and $A$ at $p_j$ which correspond to the same memory location $Y \neq X$). The talk will show how algorithms can cope with the uncertainty created by these two types of anonymity. To this end, taking examples from the literature, it will present anonymity-tolerant implementations of several concurrent objects, such as snapshot, consensus, and lock, each implementation satisfying a well-defined progress condition (obstruction-freedom, non-blocking, or wait-freedom). This paper must be considered as a short example-driven introductory tutorial on anonymous asynchronous read/write systems.
- 11h40 - Déjeuner
14h00 - (IRISA)
During this talk, we will investigate two ways to improve a multisource push-pull rumor spreading algorithm. The first one uses Random Linear Network Coding (RLNC) to increase chance of sending new information to nodes, hence improving throughput and latency. The second one's goal is to reconfigure algorithm's parameters automatically during its execution thanks to control theory to limit the number of variables to configure. This is joint work with David Bromberg and Davide Frey.
14h30 - (IRIF)
Distributed proofs are mechanisms enabling the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g. having a specific diameter), or on data-structures distributed over the nodes (e.g. a spanning tree). 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. This is joint work with Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen and Mor Perry.
- 15h10 - Pause
15h30 - (LS2N)
This talk presents a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message $m$ and later delivers a set of messages including a message $m′$, no process delivers first a set of messages including $m′$ and later a set of message including $m$. This talk will mainly focus on the "power" side of the abstraction, from the programming model viewpoint: it will present SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data), and distributed tasks. On the “computability limits” side it will show that SCD-broadcast and read/write registers are computationally equivalent.
16h00 - (IRISA)
A new notion of process failure explicitly related to contention has recently been introduced by Taubenfeld (NETYS'18). More precisely, given a predefined contention threshold $\lambda$, this notion considers the executions in which process crashes are restricted to occur only when process contention is smaller than or equal to $\lambda$. If crashes occur after contention bypassed $\lambda$, there are no correctness guarantees (e.g., termination is not guaranteed). Taubenfeld showed that, when $\lambda = n-1$, consensus can be solved in $n$-process asynchronous read/write system despite the crash of one process, thereby circumventing the well-known FLP impossibility result. In this talk, we consider two types of crash failures: contention-related and classical crash failures. We present algorithms suited to both these types of failures for $k$-set agreement and renaming. This is joint work with Michel Raynal and Gadi Taubenfeld.
- 16h40 - Discussions
- 17h00 - Fin de la réunion