Distributed function calculation via linear iterations in the presence of malicious agents - Part II: Overcoming malicious behavior

Abstract

Given a network of interconnected nodes, each with a given initial value, we develop a distributed strategy that enables some or all of the nodes to calculate any arbitrary function of these initial values, despite the presence of some malicious (or faulty) nodes. Our scheme utilizes a linear iterative strategy where, at each time-step, each node updates its value to be a weighted average of its own previous value and those of its neighbors. We consider a node to be malicious if, instead of following the predefined linear iterative strategy, it updates its value arbitrarily at each time-step (perhaps by conspiring and coordinating with other malicious nodes). When there are up to f malicious nodes, we show that any node in the network is guaranteed to be able to calculate any arbitrary function of all initial node values if the graph of the network is at least (2f +1)-connected. Specifically, we show that under this condition, the nodes can calculate their desired functions after running the linear iteration for a finite number of timesteps (upper bounded by the number of nodes in the network) using almost any set of weights (i.e., for all weights except for a set of measure zero). Our approach treats the problem of fault-tolerant distributed consensus, where all nodes have to calculate the same function despite the presence of faulty or malicious nodes, as a special case. ©2008 AACC.