2nn Symmetric Communication Structure for Decentralized Consensus Protocols Using a Duality of Indices

Amane NAKAJIMA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E77-D    No.6    pp.669-675
Publication Date: 1994/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
Keyword: 
distributed systems,  computer networks,  communication structures,  decentralized consensus protocols,  combinatorics,  finite projective planes,  

Full Text: PDF>>
Buy this Article


Summary: 
Distributed algorithms that entail successive rounds of message exchange are called decentralized consensus protocols. Several consensus protocols use a finite projective plane as a communication structure and require 4nn messages in two rounds, where n is the number of nodes. This paper presents an efficient communication structure that uses a finite projective plane with a duality of indices. The communication structure requires 2nn messages in two rounds, and can therefore halve the number of messages. It is shown that a finite projective plane with a duality can be constructed from a difference set, and that the presented communication structure has two kinds of symmetry.