The convergence of binary majority consensus algorithms is studied in networks with different types of disturbances. It is shown how randomization can foster convergence.

The problem of finding a consensus in a group of people occurs in many social contexts. In a similar way, distributed algorithms for consensus play an important role in networked computing and communication systems if centralized decision making is difficult or impossible. Each entity in such a system processes only local information obtained from its neighbors and ideally performs only simple computations. Despite this simplicity, the process of consensus building should be robust against different types of disturbance, such as faulty entities, noise, and communication errors.

A research team with members from Klagenfurt and Genoa has now analyzed the robustness of a special class of consensus algorithms, namely binary consensus, in which all entities must eventually agree on one out of two possible values. The motivation for their study is as follows: Some binary consensus algorithms that work well in noiseless and error-free networks—such as the well-known Gacs-Kurdyumov-Levin algorithm—show convergence problems in networks with disturbances. In turn, some other algorithms that are inferior in noiseless and error-free networks may actually improve their performance with the introduction of some noise and errors. This seemingly counterintuitive phenomenon can be partially explained by the fact that the system becomes randomized by noise and errors. It is known that randomization can help a system to escape from deadlocks and can thus have positive effects on its convergence.

The Klagenfurt-Genoa researchers show that additive noise, topology randomness, and message loss can increase the convergence rate of simple binary consensus algorithms, while presence of faulty nodes always inhibits convergence. They also propose a new consensus rule, called Random Neighbors Majority, which embeds randomization directly into the consensus algorithm, thus yielding a better convergence rate and robustness toward faulty entities. “By introducing a small level of randomness in a controlled manner, our rule reaches almost sure convergence in some scenarios,” says Alexander Gogolev, who obtained a PhD degree in the context of this study. He is one of the first graduates from the European doctoral program “Interactive and Cognitive Environments” issuing joint and double PhD degrees with five participating universities from Italy, Spain, Austria, the UK, and the Netherlands.

Publication

Alexander Gogolev, Nikolaj Marchenko, Lucio Marcenaro, and Christian Bettstetter. Distributed Binary Consensus in Networks with Disturbances. ACM Transactions on Autonomous and Adaptive Systems, vol. 10, no. 3, article 19, September 2015.

The text of this blog entry is partly based on the introduction of the mentioned journal article. The work was done within the Erasmus Mundus Joint Doctorate in “Interactive and Cognitive Environments”. Gogolev was supported by Lakeside Labs with funding from the ERDF, KWF, and the state of Austria under grant 20214/21530/32606.