We consider the problem of approximate consensus in mobile networks containing Byzantine nodes. We assume that each correct node can communicate only with its neighbors and has no knowledge of the global topology. As all nodes have moving ability, the topology is dynamic. The number of Byzantine nodes is bounded by f and known by all correct nodes. We first introduce an approximate Byzantine consensus protocol which is based on the linear iteration method. As nodes are allowed to collect information during several consecutive rounds, moving gives them the opportunity to gather more values. We propose a novel sufficient and necessary condition to guarantee the final convergence of the consensus protocol. The requirement expressed by our condition is not "universal": in each phase it affects only a single correct node. More precisely, at least one correct node among those that propose either the minimum or the maximum value which is present in the network, has to receive enough messages (quantity constraint) with either higher or lower values (quality constraint). Of course, nodes' motion should not prevent this requirement to be fulfilled. Our conclusion shows that the proposed condition can be satisfied if the total number of nodes is greater than 3f+1.
extend approximate consensus to partially connected networks @cite_1 @cite_5 . However without using flooding, they did not completely achieve global convergence. Approximate consensus problem is also addressed in multi-agent system @cite_6 @cite_14 @cite_13 @cite_2 @cite_0 . These protocols are called linear iterative consensus and mainly based on linear control theory and matrix theory. Without Byzantine failure, @cite_6 indicates that in an undirected graph a sufficient and necessary condition for consists in having adequate connected graphs. For a directed graph, @cite_14 points out that a sufficient and necessary condition consists in having a spanning tree contained in adequate connected graphs. When no Byzantine failure occurs, the speed of was analyzed in @cite_13 . Based on the knowledge of the global topology, @cite_2 and @cite_0 address approximate consensus problem in systems where nodes suffer from Byzantine faults.
@cite_14 @cite_1 @cite_6 @cite_0 @cite_2 @cite_5 @cite_13
2099175737 2107802325 2144246223 1978442567 2074032690
This note considers the problem of information consensus among multiple agents in the presence of limited and unreliable information exchange with dynamically changing interaction topologies. Both discrete and continuous update schemes are proposed for information consensus. This note shows that information consensus under dynamically changing interaction topologies can be achieved asymptotically if the union of the directed interaction graphs have a spanning tree frequently enough as the system evolves. 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 time- steps (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. We consider the problem of distributed function calculation in the presence of faulty or malicious agents. In particular, we consider a setup where each node has an initial value and the goal is for (a subset of) the nodes to calculate a function of these values in a distributed manner. We focus on linear iterative strategies for function calculation, where each node updates its value at each time-step to be a weighted average of its own previous value and those of its neighbors; after a sufficiently large number of time-steps, each node is expected to have enough information to calculate the desired function of the initial node values. We study the susceptibility of such strategies to misbehavior by some nodes in the network; specifically, we consider a node to be malicious if it updates its value arbitrarily at each time-step, instead of following the predefined linear iterative strategy. If the connectivity of the network topology is 2f or less, we show that it is possible for a set of f malicious nodes to conspire in a way that makes it impossible for a subset of the other nodes in the network to correctly calculate an arbitrary function of all node values. Our analysis is constructive, in that it provides a specific scheme for the malicious nodes to follow in order to obfuscate the network in this fashion. In a distributed system, it is often necessary for nodes to agree on a particular event or to coordinate their activities. Applications of distributed agreement are many, such as Commit Protocols in distributed database systems, selection of a monitor node in a distributed system, detecting an intruder, or agreeing on the malicious behavior of a node. Among many forms of Distributed Agreement, one form is called Approximate Agreement (AA), in which the nodes, by exchanging their local values with other nodes, need to agree on values which are approximately equal to each other. Research on AA for fully connected networks is relatively mature. In contrast, the study of AA in partially connected networks has been very limited. More specifically, no general solution to the AA problem exists for such networks. This research solves the AA problem for a specific, scalable, partially connected network with limited relays. The research considers the worst failure mode of nodes, called Byzantine, and hybrid failure modes. The results show low communication cost in comparison to fully connected networks. The network is designed to take advantage of the results available for fully connected networks. Thus, the analysis for obtaining the expressions for Convergence Rate and Fault Tolerance becomes relatively easy. We consider the set G consisting of graphs of fixed order and weighted edges. The vertex set of graphs in G will correspond to point masses and the weight for an edge between two vertices is a functional of the distance between them. We pose the problem of finding the best vertex positional configuration in the presence of an additional proximity constraint, in the sense that, the second smallest eigenvalue of the corresponding graph Laplacian is maximized. In many recent applications of algebraic graph theory in systems and control, the second smallest eigenvalue of Laplacian has emerged as a critical parameter that influences the stability and robustness properties of dynamic systems that operate over an information network. Our motivation in the present work is to "assign" this Laplacian eigenvalue when relative positions of various elements dictate the interconnection of the underlying weighted graph. In this venue, one would then be able to "synthesize" information graphs that have desirable system theoretic properties.