Skip to Main content Skip to Navigation
Reports

Star: A Stable and Robust Membership Protocol

Abstract : We present the design and analysis of STAR, a fully decentralized self-stabilizing randomized membership protocol building a strongly connected overlay graph with sub-logarithmic diameter and almost homogeneous logarithmic degree. STAR is the first protocol to simultaneously maintain the following properties on the resulting graph $G$: {(i)} The graph maintains the {\em Eulerian\/} property, namely that the in-degree and out-degree of each node are the same, and that $G$ is strongly connected. {(ii)} The out-degree of each node automatically converges to an average of $2 \ln (n)+O(1)$ without any node knowing the exact size $n$ of the network. {(iii)} The diameter of the overlay graph will be $\frac{\ln n}{\ln \ln n + \ln 2}+O(1)$ with high probability. {(iv)} STAR is self-stabilizing. Starting from an arbitrary graph topology, or after disruptive error, {\stella} will cause the overlay graph to converge to the desired properties.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00399546
Contributor : Erwan Le Merrer <>
Submitted on : Monday, July 27, 2009 - 11:38:34 AM
Last modification on : Tuesday, June 15, 2021 - 4:13:17 PM
Long-term archiving on: : Thursday, June 30, 2011 - 11:45:36 AM

File

star.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00399546, version 2

Citation

Ajoy Datta, Anne-Marie Kermarrec, Lawrence Larmore, Erwan Le Merrer. Star: A Stable and Robust Membership Protocol. [Research Report] 2009. ⟨inria-00399546v2⟩

Share

Metrics

Record views

651

Files downloads

477