Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070627
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:02:55 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:36:26 PM

Identifiers

  • HAL Id : inria-00070627, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

372

Files downloads

195