Distributed systems play a critical role in providing scalable and reliable services. One important problem in distributed systems is reaching consensus among the interconnected servers (or agents). This problem is particularly challenging because of the existence of adversarial servers that can exhibit malicious behaviors, preventing the normal servers from reaching consensus. One existing work has proposed the adversarial robust consensus protocol (ARC-P) to solve the consensus problem in complete networks whenever there are more cooperative agents than adversaries. However, oftentimes complete connectivity among the servers is not available, due to, for example, network partition among the servers. Therefore, solutions are needed to address the consensus problem that only utilize local information from the neighbors of the servers.
The reason the existing ARC-P with only local information cannot guarantee consensus among the servers is that no node has enough neighbors in the different sets, which leads every node to discard all useful information from outside its own set. In this way, nodes in different sets would have different values, preventing consensus from being reached. To address this issue, the authors recognize and define the robustness property of networks. Furthermore, they show that networks with the robustness property guarantee the consensus. According to the authors,
Typically, an upper bound on the number of faults or threats in the network is assumed, i.e., at most F out of n nodes fail or are compromised. We refer to this threat assumption, or scope of threat, as the F-total model. In cases where it is preferable to make no global assumptions, we are interested in other threat assumptions that are strictly local. For example, whenever each node only assumes that at most F nodes in its neighborhood are compromised (but there is no other bound on the total number of compromised nodes), the scope of threat is F-local.
In particular, they prove that with the F-total model, the consensus is guaranteed if the network is (F+1,F+1)-robust, and that with the F-local model, the consensus is ensured if the network is (2F+1)-robust.In summary, the main contribution of this paper is that it discovers and proves that consensus can be guaranteed for networks with the robustness property by employing only local information in ARC-P.