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

fYear

1992

fDate

9-12 Jun 1992

Firstpage

426

Lastpage

433

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on

Conference_Location

Yokohama

Print_ISBN

0-8186-2865-0

Type

conf

DOI

10.1109/ICDCS.1992.235012

Filename

235012