In this series I practice reading computer science papers by following a modified set of steps outlined in the guide: How to read and understand a scientific paper: a guide for non-scientists. If your reaction to this post is ‘eh, just read the paper’, then this post isn’t for you ;)
Why Should I Read The Byzantine Generals Problem?
The research in this paper allows blockchain technology, ensures military radar installation reliability, and enables the design of distributed, fault-tolerant CPU processors. Not only is the research widely used in many interesting ways, but the paper uses the amusing military analogy of a group of separated generals trying to agree on a battle plan. The paper is a fun intro into academic papers.
The Byzantine Generals Problem pdf
My Breakdown:
Begin by reading the introduction, not the abstract
The broad problem is: how to create a network of components that can come to consensus when some nodes in the network may be sending conflicting and false information to the other nodes. We desire a solution where the “loyal” nodes perform the correct action.
Identify the BIG QUESTION
The BIG QUESTION is: how to create a network of nodes that decides on a common plan of action when some nodes are sending false information.
The big question is posed abstractly as: how can many generals decide on a plan when some generals are traitors sending false information and all generals can only communicate via messages to each other.
Identify the SPECIFIC QUESTION(S)
The SPECIFIC QUESTIONS are more simple:
- IC1: Ensure a single “general node” is able to send an order for all loyal “lieutenant nodes” to follow
- IC2: All loyal lieutenant nodes follow the order if the general is loyal
These two conditions are called the interactive consistency conditions.
Solving this specific question will unlock the solution to the more complicated scenario with multiple nodes all communicating with each other.
Determine Outline
- Abstract
- Introduction
- Problem definition with forgeable (unsigned) messages
- Proof with forgeable (unsigned) messages
- Proof with unforgeable (signed) messages
- Proof for an incomplete graph with forgeable (unsigned) messages
- Proof for an incomplete graph with unforgeable (signed) messages
- The application of the previous proofs to build reliable systems that calculate solutions across multiple processors
- Conclusion
Identify the approach
The approach is a set of logical, inductive proofs.
Explain any diagrams/charts
Fig 1 and Fig 2 illustrate how it is impossible for one commander and two lieutenants to come to consensus with unsigned messages when one of the three is a traitor.
Fig 3 and Fig 4 show the oral (unsigned) communication paths of one commander and three lieutenants, represented by OM(1). Fig 3 shows the paths of a traitorous lieutenant, and how the other lieutenants can simply do whatever the majority of inputs recommend. Fig 4 shows the traitorous commander, and how all three lieutenants need to fall back to their default behavior, as there is no clear winning majority.
Fig 5 illustrates passing signed messages with one commander and two lieutenants, represented by SM(1). Each message gets appended to the end, so a traitorous commander is revealed by sending different messages to each lieutenant.
Fig 7 is not 3-regular because the central node has more than 3 connecting paths.
Explain the recommended solution/algorithm/theory/proofs
-
The original problem, stated as two interactivity conditions:
- IC1: All loyal lieutenants obey the same order
- IC2: All lieutenant nodes follow the order if the general is loyal
-
They refer the reader to a previous proof that 3 nodes cannot be solved. They claim a proof by contradiction that therefore no solution exists for fewer than 3m+1 nodes where m is the traitor node count.
-
Inductive proof with forgeable (unsigned) messages - requires 3m+1 nodes where m is the traitor node count. * Assumptions: - A1. Every message is sent correctly - A2. The receiver of a message knows who sent it - A3. The absence of a message can be detected
-
Inductive proof with unforgeable (signed) messages - requires only m+2 generals where m is the traitor general count
- Assumptions:
- A4(a). No message can be forged by another node
- A4(b). Any node can verify the signature chain
- Assumptions:
-
Proof for an incomplete graph with forgeable (unsigned) messages - requires at least 3m+1 generals where m is the count of traitors and each node on the graph has 3m connections. (aka 3m-regular). Therefore a 3m+1 network must be completely connected.
-
Proof for an incomplete graph with unforgeable (signed) messages - requires at least m+d-1 generals where m is the count of traitors and d is the graph diameter (longest shortest distance between two generals)
Read the conclusion/discussion/interpretation section
The authors conclude that all known solutions to the Byzantine Generals problem are inherently expensive in time and number of messages sent between nodes. They do suspect that nodes could combine messages for reduced total message transfer, but they leave that as an unanswered question.
Now, go back to the beginning and read the abstract
The abstract summarizes the results: with unsigned messages, fewer than one-third of the nodes can be traitors. For signed messages, any number of nodes can be traitorous.
What do other researchers say about this paper?
This paper seems to have become a canonical source of proofs for the problem.
My Notes
While originally written for radar defense installations, blockchain technologies appear to be based off the research in this paper. They operate with signed messages being semi-unforgeable because of the difficulty to recreate the history, so it is a combination of the signed and unsigned. Messages are forgeable, but it is so computationally expensive to do so that it is effectively impossible.
The proofs in this paper are fun because they are an applied version of what I have been studying in Software Foundations. Before I read this paper, the exercises in Software Foundations seemed dry and isolated from reality. The skill of proof writing has come alive as the fundamental underpinning for world-changing technologies like blockchain! Very fun stuff.
