2N[ROOT-N] SYMMETRICAL COMMUNICATION STRUCTURE FOR DECENTRALIZED CONSENSUS PROTOCOLS USING A DUALITY OF INDEXES

Distributed algorithms that entail successive rounds of message exchan ge are called decentralized consensus protocols. Several consensus pro tocols use a finite projective plane as a communication structure and require 4n right perpendicular square-root n left perpendicular messag es in two rounds, where n is the number of nodes. This paper presents an efficient communication structure that uses a finite projective pla ne with a duality of indices. The communication structure requires 2n inverted right perpendicular square-root n inverted left perpendicular messages in two rounds, and can therefore halve the number of message s. It is shown that a finite projective plane with a duality can be co nstructed from a difference set, and that the presented communication structure has two kinds of symmetry.