Skip to Main content Skip to Navigation
New interface
Reports (Research report)

A framework for proving the self-organization of dynamic systems

Emmanuelle Anceaume 1 Xavier Défago 2 Maria Potop-Butucaru 3 Matthieu Roy 4 
1 ADEPT - Algorithms for Dynamic Dependable Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
3 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
4 LAAS-TSF - Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : This paper aims at providing a rigorous definition of self- organization, one of the most desired properties for dynamic systems (e.g., peer-to-peer systems, sensor networks, cooperative robotics, or ad-hoc networks). We characterize different classes of self-organization through liveness and safety properties that both capture information regarding the system entropy. We illustrate these classes through study cases. The first ones are two representative P2P overlays (CAN and Pastry) and the others are specific implementations of Ω (the leader oracle) and one-shot query abstractions for dynamic settings. Our study aims at understanding the limits and respective power of existing self-organized protocols and lays the basis of designing robust algorithm for dynamic systems.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Maria Potop-Butucaru Connect in order to contact the contributor
Submitted on : Tuesday, November 9, 2010 - 2:22:42 PM
Last modification on : Wednesday, October 26, 2022 - 8:15:59 AM
Long-term archiving on: : Thursday, February 10, 2011 - 2:48:58 AM


Files produced by the author(s)


  • HAL Id : inria-00534372, version 1
  • ARXIV : 1011.2312


Emmanuelle Anceaume, Xavier Défago, Maria Potop-Butucaru, Matthieu Roy. A framework for proving the self-organization of dynamic systems. [Research Report] Rapport LAAS n° 10746, LAAS. 2010, pp.26. ⟨inria-00534372⟩



Record views


Files downloads