Skip to Main content Skip to Navigation

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
Contributor : Erwan Le Merrer Connect in order to contact the contributor
Submitted on : Monday, July 27, 2009 - 11:38:34 AM
Last modification on : Thursday, January 20, 2022 - 4:13:12 PM
Long-term archiving on: : Thursday, June 30, 2011 - 11:45:36 AM


Files produced by the author(s)


  • HAL Id : inria-00399546, version 2


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



Record views


Files downloads