In many network applications the computation takes place on the minimum-cost spanning tree (MST) of the network; unfortunately, a single link or node failure disconnects the tree. In this paper we consider for the first time the problem of computing all the replacement minimum-cost spanning trees distributively, and we efficiently solve the problem. We design a solution protocol and we prove that the total amount of data items communicated during the computation is O(n 2). This communication can be achieved either transmitting O(n) long messages, if the system so allows, or O(n 2) standard messages. Even in systems that do not allow long messages, the proposed protocol constitutes a significant improvement over the individual computation of the replacement trees.

Distributed Computation of All Node Replacements of a Minimum Spanning Tree

PAGLI, LINDA;PRENCIPE, GIUSEPPE;
2007

Abstract

In many network applications the computation takes place on the minimum-cost spanning tree (MST) of the network; unfortunately, a single link or node failure disconnects the tree. In this paper we consider for the first time the problem of computing all the replacement minimum-cost spanning trees distributively, and we efficiently solve the problem. We design a solution protocol and we prove that the total amount of data items communicated during the computation is O(n 2). This communication can be achieved either transmitting O(n) long messages, if the system so allows, or O(n 2) standard messages. Even in systems that do not allow long messages, the proposed protocol constitutes a significant improvement over the individual computation of the replacement trees.
9783540744658
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/187734
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact