A high-performance communication topology for decentralized protocols

Preserving transaction atomicity and ensuring its commitment is key to the maintenance of data integrity in a distributed database. The distributed consensus protocol is a prominent example of a mechanism used to accomplish safe commitment of a distributed transaction. These protocols are based primarily on repeated message exchange among all sites/nodes and their performance is characterized not only by the number of these messages but also by the underlying communication topology. This thesis proposes a measure of performance known as average message complexity and proposes a communication structure based on folded even graphs called the Folded Even Network (FEN). Performance of FEN is compared to other known structures and is shown to outperform them for various values of the number of nodes in the network. It is also shown that large topologies can be generated by connecting multiple FENs together. The expanded structure is also shown to have the same complexity as a single FEN.