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-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
