Detalhes do Documento

Fast distributed computation of distances in networks

Autor(es): Almeida, Paulo Sérgio cv logo 1 ; Baquero, Carlos cv logo 2 ; Cunha, Alcino cv logo 3

Data: 2012

Identificador Persistente: http://hdl.handle.net/1822/24670

Origem: RepositóriUM - Universidade do Minho


Descrição
Comunicação publicada em "IEEE Conference on Decision & Control (CDC)", pag. 5215-5220 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.
Tipo de Documento Artigo
Idioma Inglês
delicious logo  facebook logo  linkedin logo  twitter logo 
degois logo
mendeley logo

Documentos Relacionados



    Financiadores do RCAAP

Fundação para a Ciência e a Tecnologia Universidade do Minho   Governo Português Ministério da Educação e Ciência Programa Operacional da Sociedade do Conhecimento União Europeia