3 ms·

This isn't about indefinite communication loss. Obviously no progress is possible in that case. The two generals' problem has nothing to do with a permanent fai

This isn't about indefinite communication loss. Obviously no progress is possible in that case. The two generals' problem has nothing to do with a permanent failure. I think there is a lot of literature out there if you're really interested in understanding and I'm happy to provide more links if you'd like.

lisper 2y ago
What makes you think the 2GP is relevant here? The 2GP has to do with coordination and consensus, not exactly-once delivery.
- shepherdjerred 2y ago
  The link I posted above explains the connection: https://blog.bulloak.io/post/20200917-the-impossibility-of-exactly-once/ https://blog.bulloak.io/post/20200917-the-impossibility-of-e... Particularly: > The sender cannot know if a message was delivered since transport is unreliable; thus, one or more acknowledgement messages are required. Moreover, the sender cannot distinguish between message delivery errors, acknowledgement delivery errors, or delays (either in processing or because or network unreliability). > The recipient is forced to send the acknowledgement only after the message is either processed (or persisted for processing) because an acknowledgement before processing would not work: if the recipient exhibits a fault before processing that would cause the loss of the message. > In the case that that acknowledgement is lost, the sender can’t know (due to lack of insight in the recipient’s state) whether the recipient failed before scheduling the message for processing (in essence losing the message) or if the recipient is just running a bit slow, or if the acknowledgement message was lost. Now, if the sender decides to re-deliver, then the recipient may end up receiving the message twice if the acknowledgement was dropped (for example). On the other hand, if the sender decides to not re-deliver, then the recipient may end up not processing the message at all if the issue was that the message wasn’t scheduled for processing.
  - lisper 2y ago
    This proof is flawed: "Let’s assume that a protocol exists which guarantees that a recipient receives a message from the sender once and only once. Such a protocol could then solve the two generals problem! Representing the time of the attack as the message, the first general (the sender) would only need to adhere to the protocol for the second general (recipient) to have received the attack time exactly one time. However, since we know that this is not possible, we also know that exactly once is not possible." The 2GP is not just the first general knowing that the second general received the message. The 2GP is the problem of achieving common knowledge between the two generals, i.e. it's not just that G1 needs to know that G2 got the message, it is that G2 needs to know that G1 knows that G2 got the message, and G1 needs to know that G2 knows that G1 knows that G2 got the message, and so on. Exactly-once delivery is possible. The only thing that is not possible is for the sender to know when the message has been received so that no duplicates are sent. But exactly-once delivery is not only possible, it's trivial. All you need to do is discard duplicates at the receiver.
    - shepherdjerred 2y ago
      > All you need to do is discard duplicates at the receiver. ...yes, which would be exactly once _processing_ but not exactly once _delivery_. Unless you're wanting to redefine "exactly once delivery" to mean "at least once delivery but I'm calling it exactly once because I have a strategy to cope with duplicate messages"
      - lisper 2y ago
        > exactly once _processing_ but not exactly once _delivery_ What exactly is the difference? What counts as "delivery"? How do you do "delivery" (on a computer) without doing at least some "processing"?
        shepherdjerred 2y ago
        Delivery is communication between two actors. Processing is what one actor (the receiver) does with a message. Communication is when two actors exchange a message. Communication is generally done over an unreliable medium because in practice there is no way to communicate without the potential of failure. 1. Exactly once communication between two actors over an unreliable medium is impossible. At the very least you have to account for the possibility of failure of the medium, so you might need to re-send messages. 2. At least once communication between two actors is possible -- just re-send a message until the receive acknowledges the message. 3. Because a message might be re-sent, the receiver must be able to cope with duplicate messages. This is what you're describing. This might be done by making message processing idempotent or tracking which messages you've seen before. In either case, you have achieve exactly once processing. That is, if a receiver is given the same message multiple times, only the first receive of the messages changes the state of the receiver. --- > But exactly-once delivery is not only possible, it's trivial. Considering that many in the field consider this problem to be impossible (or, at best, extremely difficult, e.g. https://www.confluent.io/blog/exactly-once-semantics-are-possible-heres-how-apache-kafka-does-it/ https://www.confluent.io/blog/exactly-once-semantics-are-pos...), this should be a huge red flag to yourself that you're missing something. Everyone has blind spots and that's okay, but hopefully you understand that there's a pretty big mismatch here. Alternatively, it's possible that this problem _really_ is trivial and you have some unique insight which means there's a great opportunity for you to write a paper or blog post.

lisper 2y ago

What makes you think the 2GP is relevant here? The 2GP has to do with coordination and consensus, not exactly-once delivery.

shepherdjerred 2y ago
The link I posted above explains the connection: https://blog.bulloak.io/post/20200917-the-impossibility-of-exactly-once/ https://blog.bulloak.io/post/20200917-the-impossibility-of-e... Particularly: > The sender cannot know if a message was delivered since transport is unreliable; thus, one or more acknowledgement messages are required. Moreover, the sender cannot distinguish between message delivery errors, acknowledgement delivery errors, or delays (either in processing or because or network unreliability). > The recipient is forced to send the acknowledgement only after the message is either processed (or persisted for processing) because an acknowledgement before processing would not work: if the recipient exhibits a fault before processing that would cause the loss of the message. > In the case that that acknowledgement is lost, the sender can’t know (due to lack of insight in the recipient’s state) whether the recipient failed before scheduling the message for processing (in essence losing the message) or if the recipient is just running a bit slow, or if the acknowledgement message was lost. Now, if the sender decides to re-deliver, then the recipient may end up receiving the message twice if the acknowledgement was dropped (for example). On the other hand, if the sender decides to not re-deliver, then the recipient may end up not processing the message at all if the issue was that the message wasn’t scheduled for processing.
- lisper 2y ago
  This proof is flawed: "Let’s assume that a protocol exists which guarantees that a recipient receives a message from the sender once and only once. Such a protocol could then solve the two generals problem! Representing the time of the attack as the message, the first general (the sender) would only need to adhere to the protocol for the second general (recipient) to have received the attack time exactly one time. However, since we know that this is not possible, we also know that exactly once is not possible." The 2GP is not just the first general knowing that the second general received the message. The 2GP is the problem of achieving common knowledge between the two generals, i.e. it's not just that G1 needs to know that G2 got the message, it is that G2 needs to know that G1 knows that G2 got the message, and G1 needs to know that G2 knows that G1 knows that G2 got the message, and so on. Exactly-once delivery is possible. The only thing that is not possible is for the sender to know when the message has been received so that no duplicates are sent. But exactly-once delivery is not only possible, it's trivial. All you need to do is discard duplicates at the receiver.
  - shepherdjerred 2y ago
    > All you need to do is discard duplicates at the receiver. ...yes, which would be exactly once _processing_ but not exactly once _delivery_. Unless you're wanting to redefine "exactly once delivery" to mean "at least once delivery but I'm calling it exactly once because I have a strategy to cope with duplicate messages"
    - lisper 2y ago
      > exactly once _processing_ but not exactly once _delivery_ What exactly is the difference? What counts as "delivery"? How do you do "delivery" (on a computer) without doing at least some "processing"?
      - shepherdjerred 2y ago
        Delivery is communication between two actors. Processing is what one actor (the receiver) does with a message. Communication is when two actors exchange a message. Communication is generally done over an unreliable medium because in practice there is no way to communicate without the potential of failure. 1. Exactly once communication between two actors over an unreliable medium is impossible. At the very least you have to account for the possibility of failure of the medium, so you might need to re-send messages. 2. At least once communication between two actors is possible -- just re-send a message until the receive acknowledges the message. 3. Because a message might be re-sent, the receiver must be able to cope with duplicate messages. This is what you're describing. This might be done by making message processing idempotent or tracking which messages you've seen before. In either case, you have achieve exactly once processing. That is, if a receiver is given the same message multiple times, only the first receive of the messages changes the state of the receiver. --- > But exactly-once delivery is not only possible, it's trivial. Considering that many in the field consider this problem to be impossible (or, at best, extremely difficult, e.g. https://www.confluent.io/blog/exactly-once-semantics-are-possible-heres-how-apache-kafka-does-it/ https://www.confluent.io/blog/exactly-once-semantics-are-pos...), this should be a huge red flag to yourself that you're missing something. Everyone has blind spots and that's okay, but hopefully you understand that there's a pretty big mismatch here. Alternatively, it's possible that this problem _really_ is trivial and you have some unique insight which means there's a great opportunity for you to write a paper or blog post.