Evènement pour le groupe Algorithmique Distribuée


Date 2014-12-15  14:00-15:00
TitreSplitting and renaming with a majority of faulty processes 
Résumé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 an 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. 
Lieu178 
OrateurDavid Bonnin (LaBRI, Université de Bordeaux) 



Aucun document lié à cet événement.

Retour
Retour à l'index