Byzantine Generals with Alternate Possibilities
Byzantine Consensus with Alternate Possibilities
Imagine several troupes of Byzantine soldiers stationed outside various corners of an enemy city–their generals need to agree via messenger whether to attack or retreat, but their may be enemy generals trying to sway the vote bypassing conflicting messages to the other generals. This is the problem that Byzantine consensus algorithms seek to solve. In a distributed, decentralized system, agreement must often be reached by all of the nodes of the system (like the generals) to solve a computational problem (whether to attack or retreat). In order for these nodes to agree, an algorithm must exist by which they can exchange values and reach a consensus amongst themselves even if some of the nodes of the system are traitorous (or misbehaving) and acting unpredictably. We will discuss the various methods to reach this Byzantine consensus given n nodes and t ≤ (n−1)/3 traitorous nodes. Since each consensus algorithm is designed specifically for a given set of inputs and contingent on a more generalized version, we will discuss how to reach consensus first over (a) a binary value, then over (b) a multitude of values, and finally over (c) a multitude of values given alternate possibilities. In the final algorithm, we will explore what will happen if a node has a set of acceptable and unacceptable values, providing more flexibility in reaching Byzantine consensus where there is not only one single acceptable output. Via mathematical proof, we will validate that such a Byzantine Generals with Alternate Possibilities algorithm exists and is provably valid provided that some constraints are put on the sets of acceptable and unacceptable values.
I encourage everybody to check out my presentation HERE and to check out my writeup HERE. In my writeup, I discuss a new algorithm that I created to solve the issue of BGAP variation 4 with minimal constraints and prove its validity through mathematical proof!
Thank you, everybody, for checking out my work!