Broadcasting in synchronous networks with dynamic faults

Broadcasting in synchronous networks with dynamic faults

0.00 Avg rating0 Votes
Article ID: iaor2002382
Country: United States
Volume: 27
Issue: 4
Start Page Number: 309
End Page Number: 318
Publication Date: Jul 1996
Journal: Networks
Authors: , ,
Keywords: communication
Abstract:

The problem of broadcasting in a network is to disseminate information from one node to all other nodes by transmitting it over communication links that connect nodes. We consider the time of broadcasting in the presence of at most k dynamic link failures. If a node knows source information, then in the next step all its neighbors connected by operational links also get to know it. Faults are dynamic, in the sense that a link may alternate arbitrarily between being operational or faulty, provided that, at every time step, the number of faulty links does not exceed k. The time bounds on broadcasting are considered with respect to two parameters: the number k of faulty links and the diameter d of the underlying graph. Broadcasting is guaranteed to be successful if and only if the edge connectivity of the network exceeds k, and we consider only such networks. For a fixed k, it is shown that broadcasting is always completed in time O(dk+1), where the bound is a function of diameter d. For a fixed d, it is shown that broadcasting is always completed in time O(kd/2−1), where the bound is a function of k. We prove that these orders of magnitude cannot be improved in general. Among networks, particularly interesting are those in which broadcasting time is close to their diameter in the presence of at most k dynamic faults, where k + 1 is the edge-connectivity of the network. We show that multidimensional tori have this property.

Reviews

Required fields are marked *. Your email address will not be published.