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!
Dude those are some gnarly proofs. Your prop on how the generals would have to create a plan to rid the “traders” had me hooked from the beginning. This was a very complex topic which could have been easy to get away from you, but the way you organized the presentation allowed me to stay on track and take in all the information. Great job man, wish it could have been presented in person, you would have killed it.
Extremely well done presentation, especially with the proofs. The mathematical reasoning was also easy to follow, even with such a complex topic. I think it would be interesting to see how this could play out in politics, like voting in that Senate for a bill to pass, which (as I understood it) would have some of the same ideas as the Byzantine Consensus; two results, with one party interested in making sure the other party doesn’t have enough say to sway the vote.
Hello! I thought your presentation was very impressive! I thought the Byzantine general application was an incredibly innovative use of the consensus concept you explained. You did a great job explaining things in a way so that someone like me who isn’t very familiar with computer algorithms could still follow along. I was totally blown away by all of those proofs! Not only did you do a ton of them, but you also explained them very well! Great job!
This was a great presentation! I’ve never heard about this before. You had a great abstract which hooked many people, including myself. The proofs seemed difficult, however, you explained them really well. This was very well done. I really like this concept and wish you could have presented it in person. Great job!
Excellent job! I’ve taken a lot of computer science courses so i’m fairly strong with following algorithms and you did a great job at making what could have been complex and difficult to understand, readily understandable. This was a really interesting topic too that i had no idea had mathematical implications like this. It always surprises me how applicable math is in settings like this; wherever there’s an algorithm, or even a plan for that matter, there’s probably some math behind it.
Very impressive. I’m not familiar with computer science, and I believe I was following but I also wish you could have presented it in person as everyone else mentioned! Really well done. I can’t verify the write up, but the fact that you came up with an alternate solution is really good work and shows us that you worked really hard on this topic.
First of all, I’d just like to appreciate how professional your blog post looks! It is very well put together and the abstract is very captivating. I was intrigued when you mentioned the applications of consensus. I know that the code accounts for a limited number of traitors, but I was wondering if given the proper computing power if it would be possible to find which nodes are the traitors? I was thinking about the cryptocurrency specifically and was wondering if it would be possible to track fraud through this avenue? Anyways, it was a great presentation that was easy to follow seeing as I have only taken one course in computer science. Thank you for putting in such detailed work as it truly made it easier to follow despite not being able to see the presentation in person!
@lundy this could likely be attained with private key encryption… if you require the programs to send their responses encrypted with a key that only behaving nodes are aware of, nodes that aren’t behaving because of rogue cannot can’t send bad values… as for nodes that refuse to respond, a timeout limit is the only way I could imagine at the moment, or asking other known responsive nodes if they’ve heard from the delayed node. No doubt, this could be much more complex if nodes start to communicate with each other to see if they’ve all received the same value from another node. With that strategy of intercommunication, you could triage liars that send conflicting values and cut off any node that none of the other nodes have heard from in a while.
Hello Cory, your presentation is very interesting. Even though you could not present it in person, you did a really good job. I think you make a good choice on that topic since you already have a computer science background. The topic is very complicated and the algorithm looks really complex but you explained it very well. I can tell you put so much effort into that presentation, nice work.
Wow! I remember how much I was struggling to understand the articles when we were working together. Yet, your presentation took such a difficult topic and made it easier to grasp. It’s clear how much work and time you have put into it. If only we were able to see you present it in person. Great job.
Incredible presentation! The way you organized your slides made a difficult topic easier to follow. And it is very impressive that you were able to make a new algorithm, very cool. Would’ve been very interesting for this to be presented in class, and so sorry we did not get that opportunity.
This might be one of the most interesting topics I’ve seen in math so far. I really like that you explained your proofs as you were doing them. That’s something that I wish everyone did (especially professors, lol). These remind me of real analysis proofs, where you need commentary from line to line or else you’ll get lost because there’s just so much to remember. Gotta agree with Jake – the math in here is gnarly. Awesome job working with a complex topic.
Hello, your presentation is very interesting. As it is written, I also think it is important concept for distributed computing, cybersecurity and blockchain. In real physical world, similar problems happened. If I considered too much, I cannot trust anyone. Mathematics and algorithm would give us reasonable solution, I felt from your presentation. Great job!