Using Three States for Binary Consensus on Complete Graphs

We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts other nodes and updates its current state based on the state communicated by the last contacted node. We assume that both signaling (the information exchanged at node contacts) and memory (computation state at each node) are limited and restrict our attention to systems where each node can contact any other node (i.e., complete graphs). It is well known that for systems with binary signaling and memory, the probability of reaching incorrect consensus is equal to the fraction of nodes that initially held the minority state. We show that extending both the signaling and memory by just one state dramatically improves the reliability and speed of reaching the correct consensus. Specifically, we show that the probability of error decays exponentially with the number of nodes N and the convergence time is logarithmic in N for large N. We also examine the case when the state is ternary and signaling is binary. The convergence of this system to consensus is again shown to be logarithmic in N for large N, and is therefore faster than purely binary systems. The type of distributed consensus problems that we study arises in the context of decentralized peer- to-peer networks, e.g. sensor networks and opinion formation in social networks - our results suggest that robust and efficient protocols can be built with rather limited signaling and memory.

I. Introduction

The binary consensus problem is the following-Given a network where each node initially observes one of two states, 0 or 1, how to construct a robust distributed protocol which ensures that the nodes reach the right consensus, i.e., the majority observation at the start of the protocol. We are interested in the binary consensus problem when there is a limitation on the memory and the communication between the nodes of the network. In particular, we analyze two protocols for the binary consensus problem. In both protocols, we restrict the nodes to store one of three values 0, 1 and . In the first protocol, we restrict the signaling to be ternary, i.e, a node can communicate only one of three states, and in the second, we consider the case when the signaling is binary. We call the two protocols respectively, the ternary signaling and the binary signaling protocol. The extra state corresponds to an “undecided” state where the node is unsure of the majority value. This state can also be thought of as an extra quantization level which corresponds to the averaging of a 0 and a 1. We are interested in characterizing our two protocols with respect to error probability of final consensus and convergence rate. Our results are for the case when the underlying graph is complete. The complete graph assumption is a valid approximation for unstructured overlays in peer to peer networks, e.g., Freenet, Gnutella and Fast Track (see [7] for a survey). In such networks, nodes are connected by random edges, hence sampling of a node neighbourhood resembles sampling on a complete graph.