Seminar Room, ground floor (Building IMAG)
31 août 2017 - 10h15
Workshop ESTATE/VERIMAG Distributed Algorithms
par
Abstract: In the context of the ANR project ESTATE, we organize a workshop on distributed algorithms.
Programme
Talks ANR ESTATE
10:15-11h00 : Preuves de terminaison par variants, Pierre Castéran
11:00-11h30 : Composition certifiée d'algorithmes autostabilisants silencieux, Pierre Corbineau
11:30 12:00 : Asynchronous approach in the plane: A deterministic polynomial algorithm, Sébastien Bouchard
12:15-13:30 Repas (buffet)
Workshop
13:30-14:30 Set-Constrained Delivery Broadcast: Definition, Abstraction Power, and Computability Limits
by Michel Raynal (IRISA and University of Rennes)
(Joint work with Damien Imbs, Achour Mostéfaoui, Matthieu Perrin)
Abstract: This talk will introduce 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.
After having presented an algorithm implementing SCD-broadcast, the talk will investigate its programming power and its computability limits. On the ``power'' side it presents 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 shows that SCD-broadcast and read/write registers are computationally equivalent.
Bio: Michel Raynal is a full professor in Computer Science at University of Rennes. His main research interests are
(a) distributed algorithms, distributed computability, dependability, and
(b) the fundamental principles that underlie the design and the construction of distributed computing systems.
He received the 2015 Prize for Innovation in Distributed Computing. Michel Raynal is a senior member of the prestigious “Institut Universitaire de France” and a member of Academia Europaea.
14:30-14:45 break
14:45-15:45 Distributed Property Testing
by Pierre Fraigniaud (CNRS and University Paris Diderot)
Abstract: This talk will present some of the most recent results about distributed property testing. The latter is a variant of property testing, adapted to distributed network computing, where the sequence of centralized queries to nodes of a network is replaced by a sequence of concurrent actions performed by these nodes. Distributed property testing is, by some aspects, stronger than (sequential) property testing, as all nodes can be probed in just one step. However, by other aspects, it is also weaker, including the lack of a central entity gathering the results of all probes. Moreover, the distributed computing model may impose restrictions to the capacity of the nodes to exchange information, like in, e.g., the classical CONGEST model. In this latter model, the talk will present upper and lower bound techniques for the problem of distributedly testing the presence of given subgraphs.
Bio: Pierre Fraigniaud is a senior researcher at the CNRS. He is currently the director of IRIF (Institut de Recherche en Informatique Fondamentale). His main research interest is parallel and distributed computing, and specifically the design and analysis of distributed algorithms and data structures for networks.
In 2012, he received the Silver Medal from CNRS, and, in 2014, the Prize for Innovation in Distributed Computing.
15:45-16:00 break
16:00-17:00 Relationships between various communication models of shared memory paradigm for fault-tolerant distributed computing
by Colette Johnen (Univ. Bordeaux, CNRS, LaBRI)
Abstract: There 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.
Bio: Colette Johnen is full professor in Computer Science at University of Bordeaux (France) since 2008. Her research interests include theoretical models of distributed systems, distributed algorithms, and routing in communication networks.
