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?
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.
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.
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.
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.
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.
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."
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....
What if you need to serve 3rd world countries? Unreliable internet connection is the norm. A company with Google scale would encounter something like that.
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.
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.
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"!
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.
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.
Yeah, proxying adtech company resources through your own server is the latest in adtech's attempts to bypass ad blockers and 3rd party cookie blocking.
Using uBlock Origin here and see no ads on that page without going down any Ad-bashing rabbit hole. Sure, I always have trouble ordering stuff online but not seeing ads is all worth it.
I have uBlock origin, too - and still see the Ads on this page. Strange. [Edit] Correction: After Refresh (loading the page a second time), the Ad is gone.
I appreciate the commenter’s honesty in stating they didn’t read it at least. Sorry for the author who has nice comments below that most people won’t get to read. Great article.
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#Sin...
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.
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.
Alice and Bob must each choose an actual policy for how many confirmations they need before they actually commit to attack. We can number the messages like this:
1. Alice's first message
2. Bob's first message
3. Alice's second message
4. Bob's second message
...
Alice's policy can only commit to attack after receiving some even-indexed message n. Bob can only commit to attack after receiving some odd-indexed message m. So n and m cannot possibly be equal. Therefore the possibility exists that a message fails between n and m, and either Alice or Bob ends up attacking without the other's support.
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).
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.
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.
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.
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.
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.
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.
51 comments
[ 3.4 ms ] story [ 110 ms ] threadWhich 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.
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.
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-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.
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."
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....
The 2 Generals Problem was the first thing that popped into my head, so I decided to write this guest blog post about it.
I didn’t finish the article because I went down an Ad-bashing rabbit hole though.
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.
Self-hosting may lead to sites gaming impressions data. Not that that's not also a problem with third-party hosting.
I'm so glad to be out of that market.
Granted, most sites become unusable.
We really need some cooperative filtering and/or deep learning approach for ads.
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#Sin...
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?
Alice and Bob must each choose an actual policy for how many confirmations they need before they actually commit to attack. We can number the messages like this:
1. Alice's first message 2. Bob's first message 3. Alice's second message 4. Bob's second message ...
Alice's policy can only commit to attack after receiving some even-indexed message n. Bob can only commit to attack after receiving some odd-indexed message m. So n and m cannot possibly be equal. Therefore the possibility exists that a message fails between n and m, and either Alice or Bob ends up attacking without the other's support.
for example
Back-To-Basic Reading: Byzantine Generals <https://news.ycombinator.com/item?id=13866732>
The Byzantine Generals Problem (1982) [pdf] <https://news.ycombinator.com/item?id=8697029>
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?
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.
But how could using a phone (instead of telegram etc.) fundamentally change anything?
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.
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.