Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Yes, you can have exactly-once delivery

blog.rongarret.info

Post reply on HN
Print view View original

131–140 of 140 posts

Re: Yes, you can have exactly-once delivery

#131

Post by lisper »

two_handfuls wrote: post #130
lisper wrote: post #108

Earlier quoted context omitted.

> solved without constraints on time window, msgs rates and msgs sizes But that is not what I am claiming.

The question was for the general case, so yes that is exactly what you are claiming in this thread. Here is the question again: "Well pretty confused. You can't get exactly once delivery using proposed solution in general case because you can not have infinite memory for dedupe."

Only a naive implementation requires infinite memory. (And even then it's unbounded, not infinite.)

Re: Yes, you can have exactly-once delivery

#132

Post by qaq »

lisper wrote: post #131
two_handfuls wrote: post #130

Earlier quoted context omitted.

The question was for the general case, so yes that is exactly what you are claiming in this thread. Here is the question again: "Well pretty confused. You can't get exactly once delivery using proposed solution in general case because you can not have infinite memory for dedupe."

Only a naive implementation requires infinite memory. (And even then it's unbounded, not infinite.)

You are going in circles so you claim you do have a solution for general case. It would be interesting to learn about details of such solution beyond it has different constraints compared to naive solution.

Re: Yes, you can have exactly-once delivery

#133

Post by two_handfuls »

qaq wrote: post #132
lisper wrote: post #131

Earlier quoted context omitted.

Only a naive implementation requires infinite memory. (And even then it's unbounded, not infinite.)

You are going in circles so you claim you do have a solution for general case. It would be interesting to learn about details of such solution beyond it has different constraints compared to naive solution.

Don't bother, it's clear we have a "doesn't fit in the margin" situation here.

Re: Yes, you can have exactly-once delivery

#134

Post by lisper »

two_handfuls wrote: post #133
qaq wrote: post #132

Earlier quoted context omitted.

You are going in circles so you claim you do have a solution for general case. It would be interesting to learn about details of such solution beyond it has different constraints compared to naive solution.

Don't bother, it's clear we have a "doesn't fit in the margin" situation here.

It's true that a complete solution doesn't fit easily into an HN comment. But one possibility is to send only one message at a time, and keep re-sending it until you receive an acknowledgement. Then send the next message. On the receiving side, deliver the first instance of the multiple copies you receive and discard the rest. (Send acknowledgements for all received instances of course.) This guarantees not only exactly-once delivery with only constant storage required at the receiver, but also in-order delivery. It's not particularly efficient, and it's not what you would want to do in real life, but it would work.

Re: Yes, you can have exactly-once delivery

#135

Post by lisper »

qaq wrote: post #132
lisper wrote: post #131

Earlier quoted context omitted.

Only a naive implementation requires infinite memory. (And even then it's unbounded, not infinite.)

You are going in circles so you claim you do have a solution for general case. It would be interesting to learn about details of such solution beyond it has different constraints compared to naive solution.

See my reply here: https://news.ycombinator.com/item?id=41619279

Re: Yes, you can have exactly-once delivery

#136

Post by srkiNZ »

lisper wrote: post #129
Filligree wrote: post #101

Earlier quoted context omitted.

Delivery is what happens when the signals cross from the wire into the network interface card. Depending on the layer you’re operating on, you might instead say it’s the call to recv, or the DMA transfer. The point is that it’s logically a memcpy with no further processing. Just a memcpy. The physical data transfer. It’s easy to build a reliable message-passing system on top of that, but any such system will either i…

> Delivery is what happens when the signals cross from the wire into the network interface card. If you look at this sibling comment [1] you will find someone who disagrees with your definition. [1] https://news.ycombinator.com/item?id=41601562 On your definition, yes, exactly-once delivery is not possible. But I think your definition is neither reasonable nor authoritative.

FWIW, I consider that definition to be both reasonable and (in the context of "distributed systems") authoritative.

Re: Yes, you can have exactly-once delivery

#137

Post by two_handfuls »

lisper wrote: post #134
two_handfuls wrote: post #133

Earlier quoted context omitted.

Don't bother, it's clear we have a "doesn't fit in the margin" situation here.

It's true that a complete solution doesn't fit easily into an HN comment. But one possibility is to send only one message at a time, and keep re-sending it until you receive an acknowledgement. Then send the next message. On the receiving side, deliver the first instance of the multiple copies you receive and discard the rest. (Send acknowledgements for all received instances of course.) This guarantees not only exac…

In the general case there is no bound on the number of clients.

Consider: When your client crashes, does it assume a new identity on restart? Because you didn't say that the sender saved its latest message in stable storage.

Re: Yes, you can have exactly-once delivery

#138

Post by lisper »

two_handfuls wrote: post #137
lisper wrote: post #134

Earlier quoted context omitted.

It's true that a complete solution doesn't fit easily into an HN comment. But one possibility is to send only one message at a time, and keep re-sending it until you receive an acknowledgement. Then send the next message. On the receiving side, deliver the first instance of the multiple copies you receive and discard the rest. (Send acknowledgements for all received instances of course.) This guarantees not only exac…

In the general case there is no bound on the number of clients. Consider: When your client crashes, does it assume a new identity on restart? Because you didn't say that the sender saved its latest message in stable storage.

> In the general case there is no bound on the number of clients.

Sure. So?

> When your client crashes, does it assume a new identity on restart?

Um, no? Is that really a serious question? Do you think computers in the real world lose their identity when they restart?

> Because you didn't say that the sender saved its latest message in stable storage.

I left out a lot of details that I assumed would be obvious and taken for granted. I didn't say, for example, that the intended recipient would be attached to the message either, but obviously that must be the case if there is more than one possible recipient. There are a zillion little details like that which I elided. A complete treatment would probably turn into a book because I'd have to start talking about things like atomicity, mutual exclusion, databases and transactions. But those are all red herrings.

Re: Yes, you can have exactly-once delivery

#139

Post by pyrolistical »

lisper wrote: post #114
mlyle wrote: post #88

Earlier quoted context omitted.

The piece makes a very simple distinction. Delivery is the property of a message showing up at a receiver, irrespective of the receiver making state changes. Processing is making state changes. You can't dedupe messages without some kind of state change. Your guards, writing down that a given message has been here before, have been delivered the message. An endpoint on a lossy medium has to cope with either (0 or 1)…

> The guards have "processed" the message for this purpose, and the fact that they can deliver it to you over a perfectly reliable channel is moot. No, it isn't, because the situation inside the fort is different than the situation outside. The odds of a courier being intercepted inside the fort are effectively zero. If your computational model includes a non-zero probability of failure "inside the fort" then you are…

No, one of the key ideas in distributed systems is the network is unreliable. It’s not bad actors “inside the fort” it’s just that messages get lost sometimes.

Internal switches can fail. There are countless reasons why packets will get lost

Re: Yes, you can have exactly-once delivery

#140

Post by lisper »

pyrolistical wrote: post #139
lisper wrote: post #114

Earlier quoted context omitted.

> The guards have "processed" the message for this purpose, and the fact that they can deliver it to you over a perfectly reliable channel is moot. No, it isn't, because the situation inside the fort is different than the situation outside. The odds of a courier being intercepted inside the fort are effectively zero. If your computational model includes a non-zero probability of failure "inside the fort" then you are…

No, one of the key ideas in distributed systems is the network is unreliable. It’s not bad actors “inside the fort” it’s just that messages get lost sometimes. Internal switches can fail. There are countless reasons why packets will get lost

"Inside the fort" is a metaphor for a single server, not anything involving a network.
Post reply on HN