Bibliographic Metadata

Randomized binary majority consensus : efficiency and robustness / Alexander Gogolev
Additional Titles
Randomized binary majority consensus: efficiency and robustness
AuthorGogolev, Alexander
CensorBettstetter, Christian ; Marcenaro, Lucio
DescriptionXVII, 122 S. : graph. Darst.
Institutional NoteKlagenfurt, Alpen-Adria-Univ., Diss., 2014
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)Randomisierter / binaerer / Mehrheitskonsensus / Robustheit
Keywords (EN)Randomization / binary / majority / consensus / robustness
URNurn:nbn:at:at-ubk:1-24911 Persistent Identifier (URN)
 The work is publicly available
Randomized binary majority consensus [2.52 mb]
Abstract (German)

Decision making by means of distributed consensus algorithms can be used in systems where centralized control is difficult or impossible. Algorithms that perform such a coordination in a fixed period of time - wait-free algorithms - can be beneficial in real-life distributed systems. These algorithms should be efficient and robust towards various disturbances, since the distributed consensus problem becomes non-trivial in real-life networked systems, restricted in connectivity and time.

Solutions that can solve consensus problem in such systems often decrease efficiency with stochastic disturbances. At the same time, some other algorithms can increase performance with disturbances. Employment of stochastic disturbances to promote efficiency and robustness of consensus is called randomization. Randomization has limited application to wait-free algorithms, due to the stochasticity it employs.

In this thesis we focus on wait-free algorithms for binary majority consensus with stochastic elements. First, we show that two standard algorithms, Gacs-Kurdyumov-Levin (GKL) and Simple Majority (SM) consensus, converge more often if randomized by noise and message loss in ordered and topologically random networks.

Next, we propose a Random Neighbor Majority (RNM) consensus with embedded randomization by neighbor selection. We show that with additional randomization by noise and errors RNM can outperform the GKL and SM in asynchronous environments.

Then we investigate the impact of the faulty nodes on consensus. We investigate faulty nodes with random, full, and persistent failure with different layout over the network. We show that faulty nodes with persistent failure are more adverse for binary majority consensus than faulty nodes with random and full failure. We show that randomization can promote robustness towards faulty nodes, and that RNM is more robust towards faulty nodes than GKL and SM.

We conclude the thesis with summary of results, explain open issues and discuss further research directions.

Abstract (English)

Keine Zusammenfassung vorhanden

The PDF-Document has been downloaded 14 times.