Title :
Efficient decentralized consensus protocols in a distributed computing system
Author :
Chen, Ming-Syan ; Wu, Kun-Lung ; Yu, Philip S.
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
Abstract :
Two classes of efficient decentralized consensus protocols for a distributed computing system consisting of an arbitrary number of nodes, one without an initiator and the other with an initiator, are described. It is shown that the protocol without an initiator can be systematically executed and completed in the minimal number of steps. The protocol with an initiator is divided into three phases: broadcasting phase, shuffling phase, and confirming phase. It is proved that under the protocol with initiator, a distributed system of p nodes reaches consensus with an initiator in the minimal number of steps required. The total number of messages required by the protocol with initiator is derived
Keywords :
distributed processing; protocols; arbitrary number of nodes; broadcasting phase; confirming phase; decentralized consensus protocols; distributed computing system; shuffling phase; Availability; Broadcasting; Clocks; Costs; Distributed computing; Distributed processing; High performance computing; Message passing; Microprocessors; Protocols;
Conference_Titel :
Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on
Conference_Location :
Yokohama
Print_ISBN :
0-8186-2865-0
DOI :
10.1109/ICDCS.1992.235012
