Distributed function calculation via linear iterative strategies in the presence of malicious agents
Date
2011Source
IEEE Transactions on Automatic ControlVolume
56Issue
7Pages
14951508Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Given a network of interconnected nodes, each with its own value (such as a measurement, position, vote, or other data), we develop a distributed strategy that enables some or all of the nodes to calculate any arbitrary function of the node values, despite the actions of malicious nodes in the network. Our scheme assumes a broadcast model of communication (where all nodes transmit the same value to all of their neighbors) and utilizes a linear iteration where, at each timestep, 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 or faulty if, instead of following the predefined linear strategy, it updates its value arbitrarily at each timestep (perhaps conspiring with other malicious nodes in the process). We show that the topology of the network completely characterizes the resilience of linear iterative strategies to this kind of malicious behavior. First, when the network contains 2f or fewer vertexdisjoint paths from some node xj to another node xi, we provide an explicit strategy for f malicious nodes to follow in order to prevent node xi from receiving any information about xj's value. Next, if node xi has at least 2f+1 vertexdisjoint paths from every other (nonneighboring) node, we show that xi is guaranteed to be able to calculate any arbitrary function of all node values when the number of malicious nodes is f or less. Furthermore, we show that this function can be calculated after running the linear iteration for a finite number of timesteps (upper bounded by the number of nodes in the network) with almost any set of weights (i.e., for all weights except for a set of measure zero). © 2011 IEEE.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.

Article
A twostage distributed architecture for voltage control in power distribution systems
Robbins, B. A.; Hadjicostis, Christoforos N.; DomínguezGarcia, A. D. (2013)In this paper, we propose an architecture for voltage regulation in distribution networks that relies on controlling reactive power injections provided by distributed energy resources (DERs). A local controller on each bus ...

Article
A distributed generation control architecture for islanded ac microgrids
Cady, S. T.; DomínguezGarcia, A. D.; Hadjicostis, Christoforos N. (2015)In this paper, we propose a distributed architecture for generation control in islanded ac microgrids with both synchronous generators and inverterinterfaced power supplies. Although they are smaller and have lower ratings, ...

Article
Outage probability under channel distribution uncertainty
Ioannou, I.; Charalambous, Charalambos D.; Loyka, S. (2012)Outage probability and capacity of a class of blockfading MIMO channels are considered under partial channel distribution information. Specifically, the channel or its distribution is not known but the latter is known to ...