6 ms·

The Two Generals Problem

95 points by ashitlerferad 4y ago

edko 4y ago
After both sides have gotten a given number of acknowledgement of the acknowledgement of the acknowledgement ... of the acknowledgement: isn't it obvious that the original message was delivered?
- JoelEinbinder 4y ago
  Yes but it’s not obvious that it’s obvious to the other person that it was delivered. And so on.
  - lostcolony 4y ago
    Yeah; ultimately no matter how many levels of acknowledgement, the other army's decision to attack is predicated on receiving an acknowledgement to the most recent message, not past ones (else you don't need an acknowledgement at all). There's an inductive principle at play; even at 100 levels deep it's the same problem as the original.
- DoctorOW 4y ago
  Part of the point of this thought experiment is to determine what the "given number" is since there isn't a mathematically correct answer.
  - lostcolony 4y ago
    Sort of; 1 is just as good as 100, since whether the other army is going to attack or not is still dependent on their receiving your Nth acknowledgement, and past acknowledgements don't change the confidence of its arrival. Which brings us to the relaxed case from the OP; make it so we only need one acknowledgement, and account for the confidence level of getting that one acknowledgement.
- Twisol 4y ago
  It only takes one round-trip for both sides to be confident that the first message was received. However, the second party can't be sure the first party knows they received the message without hearing an ACK from the first party. As far as they're concerned, the first party might think it's shouting into the void. This despite the first party (hypothetically) in fact receiving the second party's ACK. Both parties can never agree on the status of all messages, because you have to generate a new message in order for an old one to advance its state. TCP works on this principle, but because not all messages are semantically relevant to the application, it can generate extra messages to push semantically meaningful messages into the agreed-upon prefix. On the other hand, a TCP connection must always terminate with at least one message un-ACKed. The best we can do is guarantee that there are no more application-level messages in flight.
CubsFan1060 4y ago
Tom Scott did a nice video on this. https://youtu.be/IP-rGJKSZ3s https://youtu.be/IP-rGJKSZ3s
RcouF1uZ4gsC 4y ago
What is interesting is that a lot of hard problems can be solved by making the network more reliable. For example here is the writeup by Eric Brewer (of CAP fame) how Google is able to achieve CA (consistency and availability) in practice because of their reliable network architecture. https://cloud.google.com/blog/products/databases/inside-cloud-spanner-and-the-cap-theorem https://cloud.google.com/blog/products/databases/inside-clou... Along the same lines, notice that while the first message can be arbitrarily long (for example the time and date of the attack, maybe the strategy), the ACK is only a single bit. So in practice, Alice's message could be, "Attack on May 9th at Dawn, and as soon as you receive the message, set the hill behind you on fire." So no matter how good the enemy is at capturing messengers, if at least one messenger gets through, and Alice is able to notice whether the hill behind Bob is on fire, they will be able to coordinate successfully.
- hangonhn 4y ago
  Michael Stonebaker made a very similar argument as well: https://cacm.acm.org/blogs/blog-cacm/83396-errors-in-database-systems-eventual-consistency-and-the-cap-theorem/fulltext https://cacm.acm.org/blogs/blog-cacm/83396-errors-in-databas... Quote: "Let us now turn to cases where the CAP theorem might apply. Consider error 6 where a LAN partitions. In my experience, this is exceedingly rare, especially if one replicates the LAN (as Tandem did). Considering local failures (3, 4, 5, and 6), the overwhelming majority cause a single node to fail, which is a degenerate case of a network partition that is easily survived by lots of algorithms. Hence, in my opinion, one is much better off giving up P rather than sacrificing C. (In a LAN environment, I think one should choose CA rather than AP). Newer SQL OLTP systems (e.g., VoltDB and NimbusDB) appear to do exactly this."
- anamax 4y ago
  However, "Alice is able to notice" isn't a given. Yes, setting a hill on fire may be more likely to "get through" than sending a messenger in response, but there's still a chance that the fire won't be seen. And, if no messengers (from Alice) got through, you might decide to set the hill on fire anyway, not knowing how Alice will interpret that act. Yes, better networks help, but as long as they're short of perfect....
- 4y ago
sarchertech 4y ago
Author here. A while back the book I’m writing on computer networks made it to the top of HN. Someone in the comments asked me a question about things that programmers don’t know about networks that cause problems. The 2 Generals Problem was the first thing that popped into my head, so I decided to write this guest blog post about it.
- ublockiblock 4y ago
- blowski 4y ago
  I’m currently reading your book after the post. It’s well-written, I’m learning a lot, thanks.
  - sarchertech 4y ago
    You are very welcome! I'm glad you're enjoying it.
ohyoutravel 4y ago
Notably this is the first website I’ve seen ads on in a very long time thanks to a combination of Duck Duck Go and PiHole and various other things. I found the ads so objectionable and attention-grabbing that I updated my PiHole block lists and checked that it was still working. Turns out the ads are served from the same domain as the article, which is kinda neat. I didn’t finish the article because I went down an Ad-bashing rabbit hole though.
- travisjungroth 4y ago
  Interesting that ad companies find the value of sending from a different domain greater than the loss from ad blocking. Makes sense that the calculation would tip on a "weblog covering Linux Systems and DevSecOps"!
  - EdwardDiego 4y ago
    A large part of it is that the publisher is having to make code changes to do so, and as part of doing so, may as well set, and then forward cookies to your adtech company right? Assuming you're not in a GPDR country. Helps your advertiser still gain some info if the user is blocking the 3rd party cookies they'll try to render anyway. The drive to map 1st party cookies to 3rd party cookies to compensate for stricter default cookie blocking in non-Chrome browsers, and the generalised failure of doing so, is what drove Google's FLoC. Even though user targeted ads are generally pretty ineffective, advertisers are addicted to them.
  - dredmorbius 4y ago
    My understanding is that independent verification is more readily accomplished through third-party service. It's also more scalable --- ads to many sites are served through a single ad network rather than through site-by-site negotiations. Self-hosting may lead to sites gaming impressions data. Not that that's not also a problem with third-party hosting.
- 10x_contrarian 4y ago
  uBlock Origin has no problem blocking them. I thought domain-proxied ads were pretty common.
patrakov 4y ago
The pseudocode for the flight + hotel saga is quite long and messy and I would not immediately recognize that this exhausts all the possibilities that might go wrong. I am not sure here, but, instead of encoding the desired and actual states via "the current place in the program", maybe it would make sense to write this program as one big for-loop that looks at the desired state and the actual state (explicitly stored in the variables), then does exactly one step to move closer to the goal, and, based on the outcome, updates these variables? I.e. apply the transformation from https://en.wikipedia.org/wiki/Structured_program_theorem#Single-while-loop,_folk_version_of_the_theorem https://en.wikipedia.org/wiki/Structured_program_theorem#Sin...
- rocqua 4y ago
  How will the for loop decide between "try to book both the hotel and the flight" and "try to cancel both the hotel and the flight"?
  - patrakov 4y ago
    This will be kept in the desired_state variable.
chris_wot 4y ago
Trying to understand this: 1. Alice sends message to Bob to attack on Tuesday and 9am 2. Bob sends message to Alice confirming this is fine 3. Alice sends confirmation of confirmation to Bob 4. Bob sends confirmation of confirmation confirmation to Alice 5. Alice sends confirmation of the confirmation of the confirmation confirmation to Bob But at this point, Bob has realized there is a confirmation. Alice has realized there is a confirmation also. Surely this is sufficient?
- ebingdom 4y ago
  What if Bob never gets the confirmation from Alice in step 5? Or if Bob doesn't need it, why did Alice even send it?
- dahfizz 4y ago
  I was also confused by this. At a certain point, you are guaranteed that the other party got your original message.
  - travisjungroth 4y ago
    You can't have both parties be guaranteed the other party got the message at the same time.
  - goto11 4y ago
    Sure, but the point is that either army only attacks if they are 100% sure the other army also attacks. This is just not possible, since the last acknowledgement might have been intercepted by the enemy.
- hakuseki 4y ago
  I guess the idea is that Alice wants to be 100% certain that Bob will attack before she commits her own forces, and Bob similarly wants to be 100% certain that Alice will attack. This level of certainty is not achievable.
  - hakuseki 4y ago
dieselerator 4y ago
I previously heard this called "The Byzantine General's problem". I think there is a lot of discussion under that name. for example Back-To-Basic Reading: Byzantine Generals <https://news.ycombinator.com/item?id=13866732 https://news.ycombinator.com/item?id=13866732> The Byzantine Generals Problem (1982) [pdf] <https://news.ycombinator.com/item?id=8697029 https://news.ycombinator.com/item?id=8697029>
- Twisol 4y ago
  These are two different problems, actually! The Byzantine Generals problem is concerned with arbitrary failure: a node may not simply fall offline, but may start sending garbage or otherwise act non-cooperatively. The Two Generals problem is concerned with network reliability and common knowledge: both parties cannot agree on the state of all messages in a system (because you must send one to inform the other party about the status of an older message).
k2xl 4y ago
1. Alice sends “Bob attack on Friday. I will send this continously until I receive a message” 2. Bob sends “Got it. Do not send another message.” 3. Alice receives it and then stops sending messages. 4. Bob now knows Alice received the message as she has stopped sending messages. Ends. What am I missing?
- Twisol 4y ago
  In 4, Bob only knows that he has stopped receiving messages. Alice may still be sending messages, but a mysterious fissure has appeared between their camps, and their couriers keep falling in.
- OrkWard 4y ago
  Bob just can't receive message from Alice anymore. But he don't know whether it's caused by acknowledgement or all messagers from Alice was caught. Whatever it was a low probability depending on how hard can be for a messager to cross the city, but never centainty.
- rocqua 4y ago
  When does Bob decide to re-send "Got it. Do not send another message". I think Bob needs to keep sending his message until he is sure Alice received one of them. So step 2 becomes: Bob sends “Got it. Do not send another message.” continuously and step 4 becomes: Bob now knows Alice received the message as she has stopped sending messages, so Bob stops sending messages. Note that in this case, Alice does not need to wait for silence from Bob. She can consider her silence a sort of "unbreakable acknowledge", so she doesn't need an acknowledge. This is an interesting approach. It works to solve the problem with 99.9% certainty if one considers message failure an identically distributed independent event. (I.e. every message is a dice roll with chance p for failure) and the message rate can be considered roughly constant. Then after n 'message intervals' without receiving a message there is chance p^n that Alice received Bobs acknowledge. Picking n large enough gives arbitrary certainty. I wonder if this has a better message complexity than sending N acknowledges. I imagine it might have to do with latency. Certainly Bobs 'repeat rate' relative to Alice's 'repeat rate' also factors in. However, the big assumption here is that message failure is an independent event. As pointed out by others, if at some point the connection is completely severed, this approach will fail. Because in that case silence of the other side could be the result of communication failure.
galaxyLogic 4y ago
Isn't the solution to use phone and call the other party and agree during the conversation that both will attack? But how could using a phone (instead of telegram etc.) fundamentally change anything?
- mach1ne 4y ago
  It doesn't, not really. It ultimately just creates an illusion of agreement due to faster transmission.
  - IntrepidWorm 4y ago
    Right - the data are still being sent in packets, but the quantity and frequency of the data packets are such that the chance of miscommunication is reduced to near zero with even a modestly strong connection.
- bskrobisz 4y ago
  At the risk of being oblivious to humor: The point is the latency and loss of the message -- for a more red-team angle, suppose someone in the intervening space has captured the communicator and seized their phone? The story is an allegory (metaphor?) for the inherent unreliability of communications between any given pieces of real-world infrastructure and the problems that arise when that unreliability reaches critical thresholds.
- rocqua 4y ago
  The phone technically doesn't solve the problem, because phone connections can be flaky. The equivalent problem would be: you call the other party and say "I will attack at 9 am if you agree" and then you get a disconnection. Then to 'prevent that' you want an OK, but to get certainty (which is absurd in this case because of the latency and the low chance of failure) you should OK that OK. Repeat infinitely. There is one feature of phones that sort-of makes a phone more useful here. You can know whether your 'message' arrived. Because if the other side hung-up then you get a dial tone.
  - 4y ago

95 points by ashitlerferad 4y ago

edko 4y ago

After both sides have gotten a given number of acknowledgement of the acknowledgement of the acknowledgement ... of the acknowledgement: isn't it obvious that the original message was delivered?

JoelEinbinder 4y ago
Yes but it’s not obvious that it’s obvious to the other person that it was delivered. And so on.
- lostcolony 4y ago
  Yeah; ultimately no matter how many levels of acknowledgement, the other army's decision to attack is predicated on receiving an acknowledgement to the most recent message, not past ones (else you don't need an acknowledgement at all). There's an inductive principle at play; even at 100 levels deep it's the same problem as the original.
DoctorOW 4y ago
Part of the point of this thought experiment is to determine what the "given number" is since there isn't a mathematically correct answer.
- lostcolony 4y ago
  Sort of; 1 is just as good as 100, since whether the other army is going to attack or not is still dependent on their receiving your Nth acknowledgement, and past acknowledgements don't change the confidence of its arrival. Which brings us to the relaxed case from the OP; make it so we only need one acknowledgement, and account for the confidence level of getting that one acknowledgement.
Twisol 4y ago
It only takes one round-trip for both sides to be confident that the first message was received. However, the second party can't be sure the first party knows they received the message without hearing an ACK from the first party. As far as they're concerned, the first party might think it's shouting into the void. This despite the first party (hypothetically) in fact receiving the second party's ACK. Both parties can never agree on the status of all messages, because you have to generate a new message in order for an old one to advance its state. TCP works on this principle, but because not all messages are semantically relevant to the application, it can generate extra messages to push semantically meaningful messages into the agreed-upon prefix. On the other hand, a TCP connection must always terminate with at least one message un-ACKed. The best we can do is guarantee that there are no more application-level messages in flight.

CubsFan1060 4y ago

Tom Scott did a nice video on this. https://youtu.be/IP-rGJKSZ3s https://youtu.be/IP-rGJKSZ3s

RcouF1uZ4gsC 4y ago

What is interesting is that a lot of hard problems can be solved by making the network more reliable. For example here is the writeup by Eric Brewer (of CAP fame) how Google is able to achieve CA (consistency and availability) in practice because of their reliable network architecture. https://cloud.google.com/blog/products/databases/inside-cloud-spanner-and-the-cap-theorem https://cloud.google.com/blog/products/databases/inside-clou... Along the same lines, notice that while the first message can be arbitrarily long (for example the time and date of the attack, maybe the strategy), the ACK is only a single bit. So in practice, Alice's message could be, "Attack on May 9th at Dawn, and as soon as you receive the message, set the hill behind you on fire." So no matter how good the enemy is at capturing messengers, if at least one messenger gets through, and Alice is able to notice whether the hill behind Bob is on fire, they will be able to coordinate successfully.

hangonhn 4y ago
Michael Stonebaker made a very similar argument as well: https://cacm.acm.org/blogs/blog-cacm/83396-errors-in-database-systems-eventual-consistency-and-the-cap-theorem/fulltext https://cacm.acm.org/blogs/blog-cacm/83396-errors-in-databas... Quote: "Let us now turn to cases where the CAP theorem might apply. Consider error 6 where a LAN partitions. In my experience, this is exceedingly rare, especially if one replicates the LAN (as Tandem did). Considering local failures (3, 4, 5, and 6), the overwhelming majority cause a single node to fail, which is a degenerate case of a network partition that is easily survived by lots of algorithms. Hence, in my opinion, one is much better off giving up P rather than sacrificing C. (In a LAN environment, I think one should choose CA rather than AP). Newer SQL OLTP systems (e.g., VoltDB and NimbusDB) appear to do exactly this."
anamax 4y ago
However, "Alice is able to notice" isn't a given. Yes, setting a hill on fire may be more likely to "get through" than sending a messenger in response, but there's still a chance that the fire won't be seen. And, if no messengers (from Alice) got through, you might decide to set the hill on fire anyway, not knowing how Alice will interpret that act. Yes, better networks help, but as long as they're short of perfect....
4y ago

sarchertech 4y ago

Author here. A while back the book I’m writing on computer networks made it to the top of HN. Someone in the comments asked me a question about things that programmers don’t know about networks that cause problems. The 2 Generals Problem was the first thing that popped into my head, so I decided to write this guest blog post about it.

ublockiblock 4y ago
blowski 4y ago
I’m currently reading your book after the post. It’s well-written, I’m learning a lot, thanks.
- sarchertech 4y ago
  You are very welcome! I'm glad you're enjoying it.

ohyoutravel 4y ago

Notably this is the first website I’ve seen ads on in a very long time thanks to a combination of Duck Duck Go and PiHole and various other things. I found the ads so objectionable and attention-grabbing that I updated my PiHole block lists and checked that it was still working. Turns out the ads are served from the same domain as the article, which is kinda neat. I didn’t finish the article because I went down an Ad-bashing rabbit hole though.

travisjungroth 4y ago
Interesting that ad companies find the value of sending from a different domain greater than the loss from ad blocking. Makes sense that the calculation would tip on a "weblog covering Linux Systems and DevSecOps"!
- EdwardDiego 4y ago
  A large part of it is that the publisher is having to make code changes to do so, and as part of doing so, may as well set, and then forward cookies to your adtech company right? Assuming you're not in a GPDR country. Helps your advertiser still gain some info if the user is blocking the 3rd party cookies they'll try to render anyway. The drive to map 1st party cookies to 3rd party cookies to compensate for stricter default cookie blocking in non-Chrome browsers, and the generalised failure of doing so, is what drove Google's FLoC. Even though user targeted ads are generally pretty ineffective, advertisers are addicted to them.
- dredmorbius 4y ago
  My understanding is that independent verification is more readily accomplished through third-party service. It's also more scalable --- ads to many sites are served through a single ad network rather than through site-by-site negotiations. Self-hosting may lead to sites gaming impressions data. Not that that's not also a problem with third-party hosting.
10x_contrarian 4y ago
uBlock Origin has no problem blocking them. I thought domain-proxied ads were pretty common.

patrakov 4y ago

The pseudocode for the flight + hotel saga is quite long and messy and I would not immediately recognize that this exhausts all the possibilities that might go wrong. I am not sure here, but, instead of encoding the desired and actual states via "the current place in the program", maybe it would make sense to write this program as one big for-loop that looks at the desired state and the actual state (explicitly stored in the variables), then does exactly one step to move closer to the goal, and, based on the outcome, updates these variables? I.e. apply the transformation from https://en.wikipedia.org/wiki/Structured_program_theorem#Single-while-loop,_folk_version_of_the_theorem https://en.wikipedia.org/wiki/Structured_program_theorem#Sin...

rocqua 4y ago
How will the for loop decide between "try to book both the hotel and the flight" and "try to cancel both the hotel and the flight"?
- patrakov 4y ago
  This will be kept in the desired_state variable.

chris_wot 4y ago

Trying to understand this: 1. Alice sends message to Bob to attack on Tuesday and 9am 2. Bob sends message to Alice confirming this is fine 3. Alice sends confirmation of confirmation to Bob 4. Bob sends confirmation of confirmation confirmation to Alice 5. Alice sends confirmation of the confirmation of the confirmation confirmation to Bob But at this point, Bob has realized there is a confirmation. Alice has realized there is a confirmation also. Surely this is sufficient?

ebingdom 4y ago
What if Bob never gets the confirmation from Alice in step 5? Or if Bob doesn't need it, why did Alice even send it?
dahfizz 4y ago
I was also confused by this. At a certain point, you are guaranteed that the other party got your original message.
- travisjungroth 4y ago
  You can't have both parties be guaranteed the other party got the message at the same time.
- goto11 4y ago
  Sure, but the point is that either army only attacks if they are 100% sure the other army also attacks. This is just not possible, since the last acknowledgement might have been intercepted by the enemy.
hakuseki 4y ago
I guess the idea is that Alice wants to be 100% certain that Bob will attack before she commits her own forces, and Bob similarly wants to be 100% certain that Alice will attack. This level of certainty is not achievable.
- hakuseki 4y ago

dieselerator 4y ago

I previously heard this called "The Byzantine General's problem". I think there is a lot of discussion under that name. for example Back-To-Basic Reading: Byzantine Generals <https://news.ycombinator.com/item?id=13866732 https://news.ycombinator.com/item?id=13866732> The Byzantine Generals Problem (1982) [pdf] <https://news.ycombinator.com/item?id=8697029 https://news.ycombinator.com/item?id=8697029>

Twisol 4y ago
These are two different problems, actually! The Byzantine Generals problem is concerned with arbitrary failure: a node may not simply fall offline, but may start sending garbage or otherwise act non-cooperatively. The Two Generals problem is concerned with network reliability and common knowledge: both parties cannot agree on the state of all messages in a system (because you must send one to inform the other party about the status of an older message).

k2xl 4y ago

1. Alice sends “Bob attack on Friday. I will send this continously until I receive a message” 2. Bob sends “Got it. Do not send another message.” 3. Alice receives it and then stops sending messages. 4. Bob now knows Alice received the message as she has stopped sending messages. Ends. What am I missing?

Twisol 4y ago
In 4, Bob only knows that he has stopped receiving messages. Alice may still be sending messages, but a mysterious fissure has appeared between their camps, and their couriers keep falling in.
OrkWard 4y ago
Bob just can't receive message from Alice anymore. But he don't know whether it's caused by acknowledgement or all messagers from Alice was caught. Whatever it was a low probability depending on how hard can be for a messager to cross the city, but never centainty.
rocqua 4y ago
When does Bob decide to re-send "Got it. Do not send another message". I think Bob needs to keep sending his message until he is sure Alice received one of them. So step 2 becomes: Bob sends “Got it. Do not send another message.” continuously and step 4 becomes: Bob now knows Alice received the message as she has stopped sending messages, so Bob stops sending messages. Note that in this case, Alice does not need to wait for silence from Bob. She can consider her silence a sort of "unbreakable acknowledge", so she doesn't need an acknowledge. This is an interesting approach. It works to solve the problem with 99.9% certainty if one considers message failure an identically distributed independent event. (I.e. every message is a dice roll with chance p for failure) and the message rate can be considered roughly constant. Then after n 'message intervals' without receiving a message there is chance p^n that Alice received Bobs acknowledge. Picking n large enough gives arbitrary certainty. I wonder if this has a better message complexity than sending N acknowledges. I imagine it might have to do with latency. Certainly Bobs 'repeat rate' relative to Alice's 'repeat rate' also factors in. However, the big assumption here is that message failure is an independent event. As pointed out by others, if at some point the connection is completely severed, this approach will fail. Because in that case silence of the other side could be the result of communication failure.

galaxyLogic 4y ago

Isn't the solution to use phone and call the other party and agree during the conversation that both will attack? But how could using a phone (instead of telegram etc.) fundamentally change anything?

mach1ne 4y ago
It doesn't, not really. It ultimately just creates an illusion of agreement due to faster transmission.
- IntrepidWorm 4y ago
  Right - the data are still being sent in packets, but the quantity and frequency of the data packets are such that the chance of miscommunication is reduced to near zero with even a modestly strong connection.
bskrobisz 4y ago
At the risk of being oblivious to humor: The point is the latency and loss of the message -- for a more red-team angle, suppose someone in the intervening space has captured the communicator and seized their phone? The story is an allegory (metaphor?) for the inherent unreliability of communications between any given pieces of real-world infrastructure and the problems that arise when that unreliability reaches critical thresholds.
rocqua 4y ago
The phone technically doesn't solve the problem, because phone connections can be flaky. The equivalent problem would be: you call the other party and say "I will attack at 9 am if you agree" and then you get a disconnection. Then to 'prevent that' you want an OK, but to get certainty (which is absurd in this case because of the latency and the low chance of failure) you should OK that OK. Repeat infinitely. There is one feature of phones that sort-of makes a phone more useful here. You can know whether your 'message' arrived. Because if the other side hung-up then you get a dial tone.
- 4y ago