HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

A randomized algorithm for the joining protocol in dynamic distributed networks

Colin Cooper 1 Ralf Klasing Tomasz Radzik
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We consider a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The algorithm acts to maintain connectivity, low diameter and constant vertex degree. This is effected as follows: On joining each vertex donates a fixed number of tokens to the network. The tokens contain the address of the donor vertex. Tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself. For example, an edge cut which leaves components of size at least $t^(c+2)/2c$ the network reconnects immediately (whp) on replacing lost edges from the token pool, where $t$ is the size of the network and $c$ is a constant of the protocol.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:02:55 PM
Last modification on : Friday, February 4, 2022 - 3:12:37 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:36:26 PM


  • HAL Id : inria-00070627, version 1



Colin Cooper, Ralf Klasing, Tomasz Radzik. A randomized algorithm for the joining protocol in dynamic distributed networks. RR-5376, INRIA. 2004, pp.21. ⟨inria-00070627⟩



Record views


Files downloads