AN EFFICIENT COMMUNICATION STRUCTURE FOR DECENTRALIZED ALGORITHMS WITH FAULT-TOLERANCE

Decentralized algorithms can be characterized by successive rounds of message interchanges. Several communication structures have been propo sed to design decentralized algorithms such as diffusion computations, logically fully connected structures and neighbouring-set communicati on structures. In this paper, we present a new communication structure , called KDAMS, which can be used to design message and bit optimal de centralized algorithms for evaluating associative and commutative func tions which include distributed transaction commitment and extrema fin ding. In addition, the KDAMS has the potential for easily imposing fau lt-tolerant mechanisms.