6 ms·

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 prot

by 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
      > hopefully you understand that there's a pretty big mismatch here Yep. But on the other hand, 1) I have a Ph.D. in CS, and 2) I have yet to see anyone in this thread actually produce a reference to a reliable source to back up the assertion that exactly-one delivery is impossible. Indeed, the one reference you provided has a headline "Exactly-Once Semantics Are Possible" so you are actually supporting my position here. Finally, I will point out something that should be obvious but apparently isn't: "exchanging a message" between computers over a network is a metaphor. There is not anything that is actually exchanged, no material transferred from one computer to another. There is only information sent in the form of electrical signals which results in state changes in the receiving system, so there is no clean boundary between "communication" and "what the receiver does with a message". Receiving a message in the context of a computer network is necessarily "doing something" with that message. There is no other way to "receive" a message.

by lisper 2y ago

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
    > hopefully you understand that there's a pretty big mismatch here Yep. But on the other hand, 1) I have a Ph.D. in CS, and 2) I have yet to see anyone in this thread actually produce a reference to a reliable source to back up the assertion that exactly-one delivery is impossible. Indeed, the one reference you provided has a headline "Exactly-Once Semantics Are Possible" so you are actually supporting my position here. Finally, I will point out something that should be obvious but apparently isn't: "exchanging a message" between computers over a network is a metaphor. There is not anything that is actually exchanged, no material transferred from one computer to another. There is only information sent in the form of electrical signals which results in state changes in the receiving system, so there is no clean boundary between "communication" and "what the receiver does with a message". Receiving a message in the context of a computer network is necessarily "doing something" with that message. There is no other way to "receive" a message.