The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes are selected to interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.
The model we introduce and analyze in this paper can be viewed as an extension to the model discussed by @cite_30 , who used a gossip algorithm to describe the spread of misinformation in social networks. In their model, the state of each node is viewed as its belief and the randomized gossip algorithm characterizes the dynamics of the belief evolution. We believe that our model is one of the first to consider faulty and misbehaving nodes in gossip algorithms. While the distributed systems community has since long recognized the need to provide fault tolerant systems, e.g. , @cite_16 @cite_10 , efforts to provide similar results for randomized gossiping algorithms have so far been limited. This paper aims at providing such results.
@cite_30 @cite_16 @cite_10
2120015072 2126924915 2126906505
We provide a model to investigate the tension between information aggregation and spread of misinformation. Individuals meet pairwise and exchange information, which is modeled as both individuals adopting the average of their pre-meeting beliefs. "Forceful" agents influence the beliefs of (some of) the other individuals they meet, but do not change their own opinions. We characterize how the presence of forceful agents interferes with information aggregation. Under the assumption that even forceful agents obtain some information from others, we first show that all beliefs converge to a stochastic consensus. Our main results quantify the extent of misinformation by providing bounds or exact results on the gap between the consensus value and the benchmark without forceful agents (where there is efficient information aggregation). The worst outcomes obtain when there are several forceful agents who update their beliefs only on the basis of information from individuals that have been influenced by them. The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor. It is shown that the problem is solvable for, and only for, n ≥ 3 m + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods. This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Boolean values or values from some bounded range, and in which approximate, rather than exact, agreement is the desired goal. Algorithms are presented to reach approximate agreement in asynchronous, as well as synchronous systems. The asynchronous agreement algorithm is an interesting contrast to a result of , who show that exact agreement with guaranteed termination is not attainable in an asynchronous system with as few as one faulty process. The algorithms work by successive approximation, with a provable convergence rate that depends on the ratio between the number of faulty processes and the total number of processes. Lower bounds on the convergence rate for algorithms of this form are proved, and the algorithms presented are shown to be optimal.