A randomized algorithm for the joining protocol in dynamic distributed networks |
| |
Authors: | Colin Cooper Ralf Klasing Tomasz Radzik |
| |
Affiliation: | 1. Department of Computer Science, King’s College London, London, UK;2. LaBRI - CNRS - Université de Bordeaux 1, 351 cours de la Liberation, 33405 Talence Cedex, France |
| |
Abstract: | We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The 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 vertex 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. |
| |
Keywords: | Randomized algorithm Dynamic network Joining protocol Random graph process Overlay network Random walks Peer to peer networks Self repairing networks |
本文献已被 ScienceDirect 等数据库收录! |