Name
Abstract | ||
|---|---|---|
Given two functions f and g mapping nodes to non-negative integers, we give a silent self-stabilizing algorithm that computes a minimal (f, g)-alliance in an asynchronous network with unique node IDs, assuming that every node p has a degree at least g(p) and satisfies f(p) ≤ g(p). Our algorithm is safely converging in the sense that starting from any configuration, it first converges to a (not necessarily minimal) (f, g)-alliance in at most four rounds, and then continues to converge to a minimal one in at most 5n + 4 additional rounds, where n is the size of the network. Our algorithm is written in the shared memory model. It is proven assuming an unfair (distributed) daemon. Its memory requirement is O(log n) bits per process, and it takes <InlineEquation ID=\"IEq1\" <EquationSource Format=\"TEX\"$O(\\varDelta^3n)$</EquationSource> </InlineEquation> steps to stabilize, where <InlineEquation ID=\"IEq2\" <EquationSource Format=\"TEX\"$\\varDelta$</EquationSource> </InlineEquation> is the degree of the network. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jpdc.2015.02.001 | Journal of Parallel and Distributed Computing |
Keywords | Field | DocType |
-alliance,safe convergence,self-stabilization | Convergence (routing),Integer,Binary logarithm,Discrete mathematics,Asynchronous network,Shared memory model,Theoretical computer science,Self-stabilization,Daemon,Mathematics | Conference |
Volume | Issue | ISSN |
81 | C | 0743-7315 |
Citations | PageRank | References |
3 | 0.38 | 21 |
Authors | ||
5 | ||
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 |
| Yvan Rivierre | 5 | 34 | 4.69 |