TERMINE - Sémi-doc Jeudi 29 Janvier - David Bonnin

Bonjour à tous,

Un sémi-doc se déroulera jeudi 29 de 14h00 à 15h00 dans l’amphithéâtre du LaBRI.
L’orateur sera David Bonnin, de l'équipe CombAlgo.
Son exposé s’intitule Distributed computing with a majority of faulty processes : renaming and splitters.

Pour le résumé voir la version anglaise ci-dessous.
Un pot suivra dans le hall du LaBRI.

L’équipe Sémi-doc.

--------------------- English version --------------------------

Hello to all,

A semi-doc will take place on Thursday from 2:00 pm to 3:00 pm in the lecture hall of LaBRI.
The speaker will be David Bonnin (CombAlgo team)
His presentation title is Distributed computing with a majority of faulty processes : renaming and splitters.

A drinks party will follow.

Description :

Distributed computing is a vast domain that studies the interaction of several independent entities (called ``processes'') communicating with each other to work locally towards some global objective.
There are many different models used in this context, some of which assume that some processes may suddenly crash and stop doing anything, without warning.
The study of fault-resilient algorithms (i.e. algorithms that take into account the possibility of crashes) is rather extensive, including in the asynchronous model I consider, but most of the results in this domain only consider a strict minority of faulty processes (no more than n/2 processes may crash during any execution).
The object of my phd thesis is to study what can be done, and which results can be extended, in the case where a majority of processes may crash.

The renaming problem has been introduced by Attiya et al. [1], and consists on the following : Each process start with a unique name in a large namespace (such as an IP address), and each process tries to acquire a new name such as, at the end of the algorithm, each process has a new unique name in a much smaller namespace.
This problem was first solved in asynchronous message-passing systems with a strict minority of processes that might crash, and later largely studied in wait-free shared memory systems, which can themselves be simulated in the former model (as explained in [2]).
Splitters are basic shared memory objects that were introduced in [3] in order to build a fast renaming algorithm, and extending the renaming to a ``long-lived'' version.
A splitter is an object that can be accessed through one operation Split(), and returns a direction in {right, down, stop}, with the property that not all processes return right, not all return down, and at most 1 process may return stop.

In asynchronous message-passing systems with a majority of faulty processes, the renaming problem cannot be solved, and splitters cannot be implemented. But we extended these notions to k-renaming and k-splitters, both for one-shot and long-lived versions.
Instead of having unique name for each process, each new name (in a small namespace) may be acquired by at most k processes, and at most k processes accessing a k-splitter may return stop.
We developed David Bonninan optimal algorithm for implementing k-splitters, i.e. the algorithm implements them with k = floor(n/(n-f)), where n in the number of processes and f the maximal number of faulty processes among them, and it is not possible to implement k'-splitters with k' < floor(n/(n-f)).
Although the namespace is not optimal, especially in the long-lived version, k-renaming based on these k-splitters is optimal for the same reason that k=floor(n/(n-f)) is both a lower bound, and a reached upper bound.

[1] H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R. Reischuk. Renaming in an asynchronous environment. J. ACM, 37(3):524–548, July 1990.
[2] H. Attiya, A. Bar-Noy, and D. Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124–142, 1995.
[3] M. Moir and J. H. Anderson. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming, 25(1):1 – 39, 1995.

Avatar Gravatar
AILS #1 Le 27 mars 2015

On trouve toujours du bon contenu dans ce site merci

Fil Rss des commentaires de cet article

Ecrire un commentaire

Quelle est la dernière lettre du mot innr ? :