Two Generals' Problem
Encyclopedia
In computing, the Two Generals' Problem is a thought experiment
meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. It is related to the more general Byzantine Generals' Problem (though published long before that later generalization) and appears often in introductory classes about computer networking (particularly with regard to the Transmission Control Protocol
), though it can also apply to other types of communication. It is also an important concept in epistemic logic
, and the importance of common knowledge
. Some authors refer to this as the Two Armies Problem or the Coordinated Attack Problem.
, each led by a general
, are preparing to attack a fortified city. The armies are encamped near the city, each on its own hill. A valley separates the two hills, and the only way for the two generals to communicate is by sending messenger
s through the valley. Unfortunately, the valley is occupied by the city's defenders and there's a chance that any given messenger sent through the valley will be captured. Note that while the two generals have agreed that they will attack, they haven't agreed upon a time for attack before taking up their positions on their respective hills.
The two generals must have their armies attack the city at the same time in order to succeed. They must thus communicate with each other to decide on a time to attack and to agree to attack at that time, and each general must know that the other general knows that they have agreed to the attack plan. Because acknowledgement of message receipt
can be lost as easily as the original message, a potentially infinite series of messages is required to come to consensus.
The thought experiment involves considering how they might go about coming to consensus. In its simplest form one general (referred to as the "first general" below) is known to be the leader, decides on the time of attack, and must communicate this time to the other general. The requirement that causes the "problem" is that both generals must attack at the agreed-upon time to succeed. Having a solitary general attack is considered a disastrous failure. The problem is to come up with algorithms that the generals can use, including sending messages and processing received messages, that can allow them to correctly conclude:
Note that it is quite simple for the generals to come to an agreement on the time to attack. One successful message with a successful acknowledgement suffices for that. The subtlety of the Two Generals' Problem is in the impossibility of designing algorithms for the generals to use to safely agree to the above statement.
Knowing this, the second general may send a confirmation back to the first: "I received your message and will attack at 0900 on August 4." However, what if the confirmation messenger were captured? The second general, knowing that the first will hesitate without the confirmation, may himself hesitate.
A solution might seem to be to have the first general send a second confirmation: "I received your confirmation of the planned attack at 0900 on August 4." However, what if that messenger were captured? It quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that both generals agree the message was delivered and that the enemy did not alter any of the messages.
, where each node
represents a run of the protocol up to a specified point. The roots are labeled
with the possible starting messages, and the children of a node N are labeled
with the possible next messages after N. Leaf nodes represent runs in which the
protocol terminates after sending the message the node is labeled with. The
empty forest represents the protocol that terminates before sending any message.
Let P be a protocol that solves the Two Generals' problem. Then, by a
similar argument to the one used for fixed-length protocols above, P' must also solve
the Two Generals' problem, where P' is obtained from P by removing all
leaf nodes. Since P is finite, it follows that the protocol represented by the
empty forest solves the Two Generals' problem. But clearly it does not,
contradicting the existence of P.
of the communication
s channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received. Alternatively the first general could send a stream of messages and the second general could send acknowledgments to each, with each general feeling more comfortable with every message received. As seen in the proof, however, neither can be certain that the attack will be coordinated. There's no algorithm that they can use (e.g. attack if more than four messages are received) which will be certain to prevent one from attacking without the other. Also, the first general can send a marking on each message saying it is message 1, 2, 3 ... of n. This method will allow the second general to know how reliable the channel is and send an appropriate number of messages back to ensure a high probability of at least one message being received. If the channel can be made to be reliable, then one message will suffice and additional messages do not help. The last is as likely to get lost as the first.
This problem was given the name the Two Generals Paradox by Jim Gray in 1978 in "Notes on Data Base Operating Systems" starting on page 465. This reference is widely given as a source for the definition of the problem and the impossibility proof, though both were published previously as above.
Thought experiment
A thought experiment or Gedankenexperiment considers some hypothesis, theory, or principle for the purpose of thinking through its consequences...
meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. It is related to the more general Byzantine Generals' Problem (though published long before that later generalization) and appears often in introductory classes about computer networking (particularly with regard to the Transmission Control Protocol
Transmission Control Protocol
The Transmission Control Protocol is one of the core protocols of the Internet Protocol Suite. TCP is one of the two original components of the suite, complementing the Internet Protocol , and therefore the entire suite is commonly referred to as TCP/IP...
), though it can also apply to other types of communication. It is also an important concept in epistemic logic
Epistemic logic
Epistemic modal logic is a subfield of modal logic that is concerned with reasoning about knowledge. While epistemology has a long philosophical tradition dating back to Ancient Greece, epistemic logic is a much more recent development with applications in many fields, including philosophy,...
, and the importance of common knowledge
Common knowledge (logic)
Common knowledge is a special kind of knowledge for a group of agents. There is common knowledge of p in a group of agents G when all the agents in G know p, they all know that they know p, they all know that they all know that they know p, and so on ad infinitum.The concept was first introduced in...
. Some authors refer to this as the Two Armies Problem or the Coordinated Attack Problem.
Definition
Two armiesArmy
An army An army An army (from Latin arma "arms, weapons" via Old French armée, "armed" (feminine), in the broadest sense, is the land-based military of a nation or state. It may also include other branches of the military such as the air force via means of aviation corps...
, each led by a general
General
A general officer is an officer of high military rank, usually in the army, and in some nations, the air force. The term is widely used by many nations of the world, and when a country uses a different term, there is an equivalent title given....
, are preparing to attack a fortified city. The armies are encamped near the city, each on its own hill. A valley separates the two hills, and the only way for the two generals to communicate is by sending messenger
Runner (war)
A runner was a soldier responsible for passing on messages between fronts during war. This was arguably the most dangerous job of all, since these soldiers obviously had to leave the safety of a trench, bunker or any other kind of shelter in order to move from one front to the other. One example is...
s through the valley. Unfortunately, the valley is occupied by the city's defenders and there's a chance that any given messenger sent through the valley will be captured. Note that while the two generals have agreed that they will attack, they haven't agreed upon a time for attack before taking up their positions on their respective hills.
The two generals must have their armies attack the city at the same time in order to succeed. They must thus communicate with each other to decide on a time to attack and to agree to attack at that time, and each general must know that the other general knows that they have agreed to the attack plan. Because acknowledgement of message receipt
Acknowledgement (data networks)
In data networking, an acknowledgment is a signal passed between communicating processes or computers to signify acknowledgment, or receipt of response, as part of a communications protocol...
can be lost as easily as the original message, a potentially infinite series of messages is required to come to consensus.
The thought experiment involves considering how they might go about coming to consensus. In its simplest form one general (referred to as the "first general" below) is known to be the leader, decides on the time of attack, and must communicate this time to the other general. The requirement that causes the "problem" is that both generals must attack at the agreed-upon time to succeed. Having a solitary general attack is considered a disastrous failure. The problem is to come up with algorithms that the generals can use, including sending messages and processing received messages, that can allow them to correctly conclude:
- Yes, we will both attack at the agreed-upon time.
Note that it is quite simple for the generals to come to an agreement on the time to attack. One successful message with a successful acknowledgement suffices for that. The subtlety of the Two Generals' Problem is in the impossibility of designing algorithms for the generals to use to safely agree to the above statement.
Illustrating the problem
The first general may start by sending a message "Let us attack at 0900 on August 4." However, once dispatched, the first general has no idea whether or not the messenger got through. Any amount of uncertainty may lead the first general to hesitate to attack, since if the second general does not also attack at that time, the city's garrison will repel the advance, leading to the destruction of that attacking general's forces.Knowing this, the second general may send a confirmation back to the first: "I received your message and will attack at 0900 on August 4." However, what if the confirmation messenger were captured? The second general, knowing that the first will hesitate without the confirmation, may himself hesitate.
A solution might seem to be to have the first general send a second confirmation: "I received your confirmation of the planned attack at 0900 on August 4." However, what if that messenger were captured? It quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that both generals agree the message was delivered and that the enemy did not alter any of the messages.
For deterministic protocols with a fixed number of messages
Suppose there is any fixed-length sequence of messages, some successfully delivered and some not, that suffice to meet the requirement of shared certainty for both generals to attack. In that case there must be some minimal non-empty subset of the successfully delivered messages that suffices (at least one message with the time/plan must be delivered). Consider the last such message that was successfully delivered in such a minimal sequence. If that last message had not been successfully delivered then the requirement wouldn't have been met, and one general at least (presumably the receiver) would decide not to attack. From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been delivered. Therefore the general sending that last message will still decide to attack (since the protocol is deterministic). We've now constructed a circumstance where the purported protocol leads one general to attack and the other not to attack - contradicting the assumption that the protocol was a solution to the problem.For nondeterministic and variable-length protocols
Such a protocol can be modeled as a labeled finite forestTree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
, where each node
represents a run of the protocol up to a specified point. The roots are labeled
with the possible starting messages, and the children of a node N are labeled
with the possible next messages after N. Leaf nodes represent runs in which the
protocol terminates after sending the message the node is labeled with. The
empty forest represents the protocol that terminates before sending any message.
Let P be a protocol that solves the Two Generals' problem. Then, by a
similar argument to the one used for fixed-length protocols above, P' must also solve
the Two Generals' problem, where P' is obtained from P by removing all
leaf nodes. Since P is finite, it follows that the protocol represented by the
empty forest solves the Two Generals' problem. But clearly it does not,
contradicting the existence of P.
Engineering approaches
A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertaintyUncertainty
Uncertainty is a term used in subtly different ways in a number of fields, including physics, philosophy, statistics, economics, finance, insurance, psychology, sociology, engineering, and information science...
of the communication
Communication
Communication is the activity of conveying meaningful information. Communication requires a sender, a message, and an intended recipient, although the receiver need not be present or aware of the sender's intent to communicate at the time of communication; thus communication can occur across vast...
s channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received. Alternatively the first general could send a stream of messages and the second general could send acknowledgments to each, with each general feeling more comfortable with every message received. As seen in the proof, however, neither can be certain that the attack will be coordinated. There's no algorithm that they can use (e.g. attack if more than four messages are received) which will be certain to prevent one from attacking without the other. Also, the first general can send a marking on each message saying it is message 1, 2, 3 ... of n. This method will allow the second general to know how reliable the channel is and send an appropriate number of messages back to ensure a high probability of at least one message being received. If the channel can be made to be reliable, then one message will suffice and additional messages do not help. The last is as likely to get lost as the first.
History
The Two Generals' Problem and its impossibility proof was first published by E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber in 1975 in "Some Constraints and Trade-offs in the Design of Network Communications", where it is described starting on page 73 in the context of communication between two groups of gangsters.This problem was given the name the Two Generals Paradox by Jim Gray in 1978 in "Notes on Data Base Operating Systems" starting on page 465. This reference is widely given as a source for the definition of the problem and the impossibility proof, though both were published previously as above.