Title :
Information dissemination in distributed systems with faulty units
Author :
Bagchi, Anindo ; Hakimi, S. Louis
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., California Univ., Davis, CA, USA
fDate :
6/1/1994 12:00:00 AM
Abstract :
Consider a network consisting of units connected by links in which some units could be faulty. Suppose each unit has a message which must be transmitted to all other (fault-free) units. We present an algorithm for doing this in a network operating in a fully distributed manner that requires at most 3n logn+O(n) message transmissions by fault-free units. Among other things, our result can be used to devise an algorithm for distributed system level diagnosis which is more efficient than the best currently known algorithm for this purpose
Keywords :
communication complexity; distributed algorithms; failure analysis; fault tolerant computing; message passing; reliability; reliability theory; distributed algorithm; distributed system level diagnosis; distributed systems; election; fault-free units; faulty units; information dissemination; spanning tree; Broadcasting; Distributed algorithms; Distributed computing; Fault diagnosis; Graph theory; Intelligent networks; Multiprocessor interconnection networks; Nominations and elections; Terminology;
Journal_Title :
Computers, IEEE Transactions on
