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.
Type de document :
[Research Report] 2009
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
Contributeur : Erwan Le Merrer <>
Soumis le : lundi 27 juillet 2009 - 11:38:34
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : jeudi 30 juin 2011 - 11:45:36


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers