Global Convergence 1 in Partially Fully Connected Networks (PFCN) with Limited Relays

Abstract – In a distributed system, it is often necessary for nodes to agree on a particular event or to coordinate their activities. Applications of distributed agreement are many, such as Commit Protocols in distributed database systems, selection of a monitor node in a distributed system, detecting an intruder, or agreeing on the malicious behavior of a node. Among many forms of Distributed Agreement, one form is called Approximate Agreement (AA), in which the nodes, by exchanging their local values with other nodes, need to agree on values which are approximately equal to each other. Research on AA for fully connected networks is relatively mature. In contrast, the study of AA in partially connected networks has been very limited. More specifically, no general solution to the AA problem exists for such networks. This research solves the AA problem for a specific, scalable, partially connected network with limited relays. The research considers the worst failure mode of nodes, called Byzantine, and hybrid failure modes. The results show low communication cost in comparison to fully connected networks. The network is designed to take advantage of the results available for fully connected networks- thus the analysis for obtaining the expressions for Convergence Rate and Fault Tolerance becomes relatively easy