Name
Abstract | ||
|---|---|---|
In this paper, we propose two {\em snap-stabilizing} distributed algorithms for the \emph{committee coordination problem}. In this problem, a committee consists of a set of processes and committee meetings are synchronized, so that each process participates in at most one committee meeting at a time. Snap-stabilization is a versatile technique allowing to design algorithms that efficiently tolerate transient faults. Indeed, after a finite number of such faults ({\em e.g.} memory corruptions, message losses, etc), a snap-% stabilizing algorithm immediately operates correctly, without any external intervention. We design snap-stabilizing committee coordination algorithms enriched with some desirable properties related to \emph{concurrency}, \emph{(weak) fairness}, and a stronger synchronization mechanism called {\em 2-Phase Discussion Time}. From previous papers, we know that (1) in the general case, (weak) fairness cannot be achieved in the committee coordination, and (2) it becomes feasible provided that each process waits for meetings infinitely often. Nevertheless, we show that even under this latter assumption, it is impossible to implement a fair solution that allows {\em maximal concurrency}. Hence, we propose two orthogonal snap-stabilizing algorithms, each satisfying 2-phase discussion time, and either maximal concurrency or fairness. The algorithm implementing fairness requires that every process waits for meetings infinitely often. Moreover, for this algorithm, we introduce and evaluate a new efficiency criterion called the \emph{degree of fair concurrency}. This criterion shows that even if it does not satisfy maximal concurrency, our snap-stabilizing fair algorithm still allows a high level of concurrency. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/IPDPS.2011.31 | Journal of Parallel and Distributed Computing |
Keywords | Field | DocType |
snap-stabilizing committee coordination,committee coordination problem,em maximal concurrency,2-phase discussion time,em snap-stabilizing,maximal concurrency,snap-stabilizing fair algorithm,committee coordination,committee meeting,fair concurrency,concurrent computing,distributed algorithm,distributed algorithms,communication networks,algorithm design and analysis,concurrency,synchronization,algorithm design,fault tolerance | Coordination game,Synchronization,Algorithm design,Finite set,Computer science,Concurrency,Parallel computing,Theoretical computer science,Distributed algorithm,Fault tolerance,Concurrent computing,Distributed computing | Conference |
Volume | Citations | PageRank |
87 | 3 | 0.38 |
References | Authors | |
20 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Borzoo Bonakdarpour | 1 | 490 | 45.02 |
| Stéphane Devismes | 2 | 61 | 6.15 |
| Franck Petit | 3 | 736 | 60.02 |