Name
Abstract | ||
|---|---|---|
We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is O(n(2)) moves with high probability, under the adversarial distributed daemon. Among all adversarial distributed daemons and with the anonymous assumption, our algorithm provides the best known complexity. Moreover, the previous best known algorithm working under the same daemon and using identity has a O(m) complexity leading to the same order of growth than our anonymous algorithm. Finally, we do not make the common assumption that a node can determine whether one of its neighbors points to it or to another node, and still we present a solution with the same asymptotic behavior. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1142/S012962641650016X | PARALLEL PROCESSING LETTERS |
Keywords | Field | DocType |
Randomized algorithm,self-stabilization,maximal matching,anonymous network | Randomized algorithm,Computer science,Algorithm,Matching (graph theory),Theoretical computer science,Self-stabilization,Asymptotic analysis,Daemon,Distributed computing,Adversarial system | Journal |
Volume | Issue | ISSN |
26 | SP4 | 0129-6264 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johanne Cohen | 1 | 228 | 33.97 |
| Jonas Lefèvre | 2 | 2 | 0.71 |
| Khaled Maamra | 3 | 1 | 2.04 |
| Laurence Pilard | 4 | 104 | 10.83 |
| Devan Sohier | 5 | 80 | 13.40 |