Consensus Resiliency of Stochastic Observation via Ring Lattices of Sensors Facing Byzantine Attacks

We consider the observation of a random, binary environment state via a set of sensing nodes connected through a ring lattice. Each node obtains a correct observation with a positive probability and broadcasts its observation to its neighbors. A system operator selects a consensus threshold for the number of consistent observations, and a consensus is reached when any node has accumulated sufficient consistent observations. A Byzantine attacker can manipulate a certain number of nodes to broadcast misleading information, and thus prohibit a correct consensus. We formulate this problem as a zero-sum game and analyze the equilibria. We show that the attacker has a dominant strategy for selecting the nodes to manipulate and the information to broadcast/block. We show that, unless the attacker's budget is abundant, the system operator can select an optimal consensus threshold to balance between the chance of a correct consensus and the risk of a wrong consensus. We also use the equilibrium structure to characterize the network resiliency, i.e., the minimal number of Byzantine nodes that would eliminate the chance of a correct consensus, given the size and connectivity of the ring lattice. The results are relevant for hardware surveillance, infrastructure inspection, disaster response, etc.