Efficient decentralized consensus protocols in a distributed computing system

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.