Efficient routing protocols in nameless networks

Abstract : Two types of distributed fully asynchronous probabilistic algorithms are given in the present paper which elect a leader and find a spanning tree in arbitrary anonymous networks of processes. Our algorithms are simpler and slightly improve on those with respect to communication complexity. So far, the present algorithms are very likely to be the first fully and precisely specified distributed communication protocols for nameless networks. They are basically patterned upon the spanning tree algorithm designed and motivated by the previous works proposed. For the case where no bound is known on the network size, we give a message terminating algorithm with error probability e which requires 0(m log log(nr) + n log n) messages on the average, each of size 0(log r + log log n) where n and m are the number of nodes and links in the network and r = 1/e. In the case where some bounds are known on n (N < n ² KN, with K ³ 1), we give a process terminating algorithm with error probability e, with 0(m + n log n) messages of size 0(log n) in the worst case. In either case, the (virtual) time complexity is 0(D x log log(nr)). In the particular case where the exact value of n is known a variant of the preceding algorithm process terminates and always succeeds in 0(m + n log n) messages of size 0(log n).
Type de document :
RR-1254, INRIA. 1990
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 17:54:31
Dernière modification le : vendredi 16 septembre 2016 - 15:11:33
Document(s) archivé(s) le : mardi 12 avril 2011 - 18:28:50



  • HAL Id : inria-00075304, version 1



Ivan Lavallee, C. Lavault. Efficient routing protocols in nameless networks. RR-1254, INRIA. 1990. 〈inria-00075304〉



Consultations de la notice


Téléchargements de fichiers