Fast Distributed Computation of Distances in Networks

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2012

Autores

Almeida, PS (Autor) Outra; Baquero, C (Autor) Outra; Cunha, A (Autor) Outra

Ata de Conferência Internacional

Título: Proceedings of the IEEE Conference on Decision and Control

Páginas: 5215-5220

51st IEEE Conference on Decision and Control, CDC 2012

Maui, HI, 10 December 2012 through 13 December 2012

Indexação

ISI Web of Knowledge - 7 Citações

Scopus - 13 Citações

Outras Informações

ID Authenticus: P-008-9K6

DOI: 10.1109/CDC.2012.6426872

Abstract (EN): This paper presents a distributed algorithm to simultaneously compute the diameter, radius and node eccentricity in all nodes of a synchronous network. Such topological information may be useful as input to configure other algorithms. Previous approaches have been modular, progressing in sequential phases using building blocks such as BFS tree construction, thus incurring longer executions than strictly required. We present an algorithm that, by timely propagation of available estimations, achieves a faster convergence to the correct values. We show local criteria for detecting convergence in each node. The algorithm avoids the creation of BFS trees and simply manipulates sets of node ids and hop counts. For the worst scenario of variable start times, each node i with eccentricity ecc(i) can compute: the node eccentricity in diam(G)+ecc(i)+2 rounds; the diameter in 2 diam(G)+ecc(i)+ 2 rounds; and the radius in diam(G) + ecc(i) + 2 radius(G) rounds.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 6