The Two Generals Problem

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"!

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.

> Turns out the ads are served from the same domain as the article, which is kinda neat.

We really need some cooperative filtering and/or deep learning approach for ads.

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.

I'm so glad to be out of that market.

uBlock Origin has no problem blocking them. I thought domain-proxied ads were pretty common.

It's probably because the ads are in-house from the root domain and not 3rd party ads with a bunch of tracking nonsense.

I usually avoid most ads by defaulting NoScript to not allow anything to be 'run', not even noscript elements.

Granted, most sites become unusable.

This comment chain at the top of a good article is more annoying than the ads were in the article.

I’m currently reading your book after the post. It’s well-written, I’m learning a lot, thanks.

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.

Michael Stonebaker made a very similar argument as well: 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."

Say the enemy captures the messenger and sets the hill on fire? Bob never receives the message so Alice attacks alone.

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....

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).

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?

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.

I was also confused by this. At a certain point, you are guaranteed that the other party got your original message.

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"?

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.

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.

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.

Part of the point of this thought experiment is to determine what the "given number" is since there isn't a mathematically correct answer.

Yes but it’s not obvious that it’s obvious to the other person that it was delivered. And so on.

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.

It doesn't, not really. It ultimately just creates an illusion of agreement due to faster transmission.

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.