Implementation, validation, and experimental evaluation of a self-stabilizing Byzantine-tolerant multivalued consensus algorithm

Abstract

Distributed computing has been in the foreground for decades, with distributed systems having numerous applications. Due to their architecture, one fundamental problem that these systems often need to solve is the consensus problem. To accomplish that, the nodes of such a system must cooperate to decide on a value. A significant percentage of the system nodes should agree on the same value. An impediment to this is that it should expect some of these nodes to act arbitrarily, deviating from their expected behavior, leading to the whole system deciding on an invalid value during consensus. These nodes are called Byzantine or faulty, and their malicious act may happen because of some internal software or hardware malfunction or a malware attack. A fundamental property of distributed systems is that their non-faulty nodes can achieve consensus in the presence of Byzantine nodes. Another property of a Distributed System is Self Stabilization and how the system behaves to handle errors. Such self-stabilizing systems can automatically recover from arbitrary transient faults, violating the system operation assumptions. Examples of such faults might be simple bit-flips in state variables or messages, but with the code left induct. In this thesis, a self-stabilizing Multivalued consensus algorithm is implemented, validated, and experimentally evaluated in the presence of up to t Byzantine processes, where t < n/3, with n being the total number of processes. Consensus is performed on an asynchronous message-passing network using the Go programming language and the ZeroMQ message library. Experiments are performed on a local workstation and the Emulab testbed platform.