5 ms·

Taken from [0]: There is a problem in distributed computing that is sometimes called the Chinese Generals Problem, in which two generals have to come to a commo

Taken from [0]: There is a problem in distributed computing that is sometimes called the Chinese Generals Problem, in which two generals have to come to a common agreement on whether to attack or retreat, but can communicate only by sending messengers who might never arrive. I stole the idea of the generals and posed the problem in terms of a group of generals, some of whom may be traitors, who have to reach a common decision. I wanted to assign the generals a nationality that would not offend any readers. At the time, Albania was a completely closed society, and I felt it unlikely that there would be any Albanians around to object, so the original title of this paper was The Albanian Generals Problem. Jack Goldberg was smart enough to realize that there were Albanians in the world outside Albania, and Albania might not always be a black hole, so he suggested that I find another name. The obviously more appropriate Byzantine generals then occurred to me. [0] https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/ https://www.microsoft.com/en-us/research/publication/byzanti...

mikorym 7y ago
The original is a well known problem in logic which my lecturer touched on. If you have each general on a mountain and a valley between the two, then you have no way to know whether the other received the message. If you send back a confirmation, then you have no confirmation confirmation... etc. In my (at the time occasional) drunken state I may have thought every now and a again, after 13 confirmations of confirmations surely you can just attack! But alas, it all falls flat: You have no way of knowing the final confirmation, the one before that, etc. until you are back where you started. By the way, this only applies to lossy communication without feedback. A Whatsapp text syncronises via a server. As long as the server is up and confirms both sides, you can be quite sure the other side received the message. This is manifested these days in the form of the infamous blue ticks.
- hprotagonist 7y ago
  well, now you trust the server. Who might betray you :)
- peheje 7y ago
  How does a server fix the problem? The server still doesn't know whether the sender knows that the server received and acknowledged your message, so you might want an ack from server, but again, the server doesn't know if you received the ack, so you ack the ack, but again ...
  - zaarn 7y ago
    Basically, the server assumes that if the client has ACK'd the message, it can continue sending data. The client assumes that the server has received their ACK if it continues sending data. If no data is being sent, the connection is closed via timeout eventually.
    - celticninja 7y ago
      You are just back to the same problem, you need to trust a server. The server is the valley between the generals, you can't be sure what happens there. Do they get the message, or do they het an altered message, both of which will send blue ticks to indicate it has been read.
      - zzbzq 7y ago
        The server is also a general on a mountain
    - peheje 7y ago
      I am talking about the Two General's problem which I thought original commentator was referring to as the original problem. In this situation you are describing a server that wants to send a client a message, and both parties need to be sure that they are in agreement when to attack a common enemy they can't deal with alone because the message contains the attack plans and timestamp for attacks. Wikipedia has a good explanation: "The first general may start by sending a message "Attack at 0900 on August 4." However, once dispatched, the first general has no idea whether or not the messenger got through. This uncertainty may lead the first general to hesitate to attack due to the risk of being the sole attacker. To be sure, the second general may send a confirmation back to the first: "I received your message and will attack at 0900 on August 4." However, the messenger carrying the confirmation could face capture and the second general may hesitate, knowing that the first might hold back without the confirmation. Further confirmations may seem like a solution—let the first general send a second confirmation: "I received your confirmation of the planned attack at 0900 on August 4." However, this new messenger from the first general is liable to be captured, too. Thus it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through. " There is no solution, only a decreasingly smaller change of disagreement e.g. by sending many messages or keep acking each other x amount of rounds (there are other strategies). No timeouts, only death.
- jfkebwjsbx 7y ago
  A server solves nothing. You can never be sure if the other person has seen that you have seen...
- LeifCarrotson 7y ago
  This applies to lossy communication with or without feedback and with or without a server. Feedback is just another layer of confirmation messages. If the server is up and sends a confirmation message to one side, but the other side disconnects before receiving the confirmation message (or before sending the acknowledgement that it received the confirmation message), you have another Byzantine Generals problem. With a server, it's just a connection of 3 generals with the server in the middle, instead of a peer-to-peer connection.
- Retric 7y ago
  Using a server just moves the problem to a different channel it does not remove it. You can design a practical protocol between two parties that actually works based on a large number of messages. Let’s say the generals can exchange 100 messages each of which has an independent 80% chance of message failure. That sounds really bad. However, if the protocol is I will attack after receiving 20 messages or I will flip a coin once for each message received and attack on the specific date if even a single head shows up. Now in your example if they receive 13 conformations they can assume there is at minimum a 99.98% chance the other party is going to attack. There are several ways to improve the protocol based on a host of factors. But, it really demonstrates the difference between theory and practice.
- kovek 7y ago
  I don’t see why they can’t agree after a second confirmation? Let’s say A first tells “7am” to B and after that they send eachother ACK. Let’s say this happens: A -1-> B A <-2- B A -3-> B A <-4- B If the rule is that the general sends a message back when he receives one, then, these 4 back and forth that I showed are only possible if this HAS happened: A —1-> B A <-2- B A -3-> B So we know that these 3 back and forth have happened. Also B knows that these 3 back and forth have happened, and A knows that 2 back and forths have happened. B knows B got the message because B got the message. A knows B got the message 1 because A got a confirmation (message 2). This is difficult for me but I convinced myself here. Please anyone prove me wrong!
  - jayd16 7y ago
    If A does not receive 4, it cannot know B received 3. If B did not receive 3 it can assume A did not receive 2. If A did not receive 2 then B should assume the attack is off If A thinks B is not attacking then A should not attack either.
    - umvi 7y ago
      But in this scenario A did receive 4, so it can assume B received 3. And in this scenario B received 3. Presumably A will keep sending 3 over and over using a timeout until it receives 4.
      - dwohnitmok 7y ago
        And what happens if B attacks before A receives the 4 (B did receive the 3 after all)?
        umvi 7y ago
        A attacks too, since, being a thinking human knows that he previously received 2. I think most humans would attack with a reasonable degree of confidence if they had gotten at least one ack in the past
- jayd16 7y ago
  It doesn't solve it. You can send a message and kill the connection before you get the ack or the read receipt and they'll still get the message.
SilasX 7y ago
Scott Adams created Elbobia as a fictional country, with both Eastern European and middle eastern traits, so he could make fun of a backward country without offending anyone. Interestingly, it feels like a cross of Estonia and Albania.

mikorym 7y ago

The original is a well known problem in logic which my lecturer touched on. If you have each general on a mountain and a valley between the two, then you have no way to know whether the other received the message. If you send back a confirmation, then you have no confirmation confirmation... etc. In my (at the time occasional) drunken state I may have thought every now and a again, after 13 confirmations of confirmations surely you can just attack! But alas, it all falls flat: You have no way of knowing the final confirmation, the one before that, etc. until you are back where you started. By the way, this only applies to lossy communication without feedback. A Whatsapp text syncronises via a server. As long as the server is up and confirms both sides, you can be quite sure the other side received the message. This is manifested these days in the form of the infamous blue ticks.

hprotagonist 7y ago
well, now you trust the server. Who might betray you :)
peheje 7y ago
How does a server fix the problem? The server still doesn't know whether the sender knows that the server received and acknowledged your message, so you might want an ack from server, but again, the server doesn't know if you received the ack, so you ack the ack, but again ...
- zaarn 7y ago
  Basically, the server assumes that if the client has ACK'd the message, it can continue sending data. The client assumes that the server has received their ACK if it continues sending data. If no data is being sent, the connection is closed via timeout eventually.
  - celticninja 7y ago
    You are just back to the same problem, you need to trust a server. The server is the valley between the generals, you can't be sure what happens there. Do they get the message, or do they het an altered message, both of which will send blue ticks to indicate it has been read.
    - zzbzq 7y ago
      The server is also a general on a mountain
  - peheje 7y ago
    I am talking about the Two General's problem which I thought original commentator was referring to as the original problem. In this situation you are describing a server that wants to send a client a message, and both parties need to be sure that they are in agreement when to attack a common enemy they can't deal with alone because the message contains the attack plans and timestamp for attacks. Wikipedia has a good explanation: "The first general may start by sending a message "Attack at 0900 on August 4." However, once dispatched, the first general has no idea whether or not the messenger got through. This uncertainty may lead the first general to hesitate to attack due to the risk of being the sole attacker. To be sure, the second general may send a confirmation back to the first: "I received your message and will attack at 0900 on August 4." However, the messenger carrying the confirmation could face capture and the second general may hesitate, knowing that the first might hold back without the confirmation. Further confirmations may seem like a solution—let the first general send a second confirmation: "I received your confirmation of the planned attack at 0900 on August 4." However, this new messenger from the first general is liable to be captured, too. Thus it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through. " There is no solution, only a decreasingly smaller change of disagreement e.g. by sending many messages or keep acking each other x amount of rounds (there are other strategies). No timeouts, only death.
jfkebwjsbx 7y ago
A server solves nothing. You can never be sure if the other person has seen that you have seen...
LeifCarrotson 7y ago
This applies to lossy communication with or without feedback and with or without a server. Feedback is just another layer of confirmation messages. If the server is up and sends a confirmation message to one side, but the other side disconnects before receiving the confirmation message (or before sending the acknowledgement that it received the confirmation message), you have another Byzantine Generals problem. With a server, it's just a connection of 3 generals with the server in the middle, instead of a peer-to-peer connection.
Retric 7y ago
Using a server just moves the problem to a different channel it does not remove it. You can design a practical protocol between two parties that actually works based on a large number of messages. Let’s say the generals can exchange 100 messages each of which has an independent 80% chance of message failure. That sounds really bad. However, if the protocol is I will attack after receiving 20 messages or I will flip a coin once for each message received and attack on the specific date if even a single head shows up. Now in your example if they receive 13 conformations they can assume there is at minimum a 99.98% chance the other party is going to attack. There are several ways to improve the protocol based on a host of factors. But, it really demonstrates the difference between theory and practice.
kovek 7y ago
I don’t see why they can’t agree after a second confirmation? Let’s say A first tells “7am” to B and after that they send eachother ACK. Let’s say this happens: A -1-> B A <-2- B A -3-> B A <-4- B If the rule is that the general sends a message back when he receives one, then, these 4 back and forth that I showed are only possible if this HAS happened: A —1-> B A <-2- B A -3-> B So we know that these 3 back and forth have happened. Also B knows that these 3 back and forth have happened, and A knows that 2 back and forths have happened. B knows B got the message because B got the message. A knows B got the message 1 because A got a confirmation (message 2). This is difficult for me but I convinced myself here. Please anyone prove me wrong!
- jayd16 7y ago
  If A does not receive 4, it cannot know B received 3. If B did not receive 3 it can assume A did not receive 2. If A did not receive 2 then B should assume the attack is off If A thinks B is not attacking then A should not attack either.
  - umvi 7y ago
    But in this scenario A did receive 4, so it can assume B received 3. And in this scenario B received 3. Presumably A will keep sending 3 over and over using a timeout until it receives 4.
    - dwohnitmok 7y ago
      And what happens if B attacks before A receives the 4 (B did receive the 3 after all)?
      - umvi 7y ago
        A attacks too, since, being a thinking human knows that he previously received 2. I think most humans would attack with a reasonable degree of confidence if they had gotten at least one ack in the past
jayd16 7y ago
It doesn't solve it. You can send a message and kill the connection before you get the ack or the read receipt and they'll still get the message.

SilasX 7y ago

Scott Adams created Elbobia as a fictional country, with both Eastern European and middle eastern traits, so he could make fun of a backward country without offending anyone. Interestingly, it feels like a cross of Estonia and Albania.