Name
Abstract | ||
|---|---|---|
We consider the (deterministic) ℓ-exclusion problem, a generalization of the mutual exclusion problem which allows use of 1 ≤ ℓ < n identical copies of a non-sharable reusable resource among n processes, instead of only one, as standard mutual exclusion. This problem is defined using three properties: safety, fairness, and avoidance of ℓ-deadlock. We first show that any algorithm satisfying the three aforementioned properties has a waiting time of Ω(n − ℓ) rounds. Thus, when n is large, the gain (in terms of waiting time) of having ℓ copies of a resource, instead of one, becomes negligible. We propose to reformulate the problem by replacing the avoidance of ℓ-deadlock property by a new property, which we call fast waiting time, which requires waiting time of O(n/ℓ) rounds, which is asymptotically optimal. We call this new version of the problem fast waiting time ℓ-exclusion. We give two self-stabilizing solutions for this new problem. Our first solution works in oriented rooted ring networks. Our second solution is a generalization of the first, and works in every connected identified network. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2684464.2684465 | ICDCN |
Keywords | Field | DocType |
algorithms,distributed systems,self-stabilization,-exclusion,&ell,waiting time,reliability,-token circulation,self stabilization,exclusion,ell | Discrete mathematics,Computer science,Computer network,Algorithm,Self-stabilization,Token circulation,Asymptotically optimal algorithm,Mutual exclusion | Conference |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabienne Carrier | 1 | 15 | 1.97 |
| Ajoy Kumar Datta | 2 | 317 | 40.76 |
| Stéphane Devismes | 3 | 192 | 25.74 |
| Lawrence L. Larmore | 4 | 859 | 109.15 |