Comment by lisper
Only a naive implementation requires infinite memory. (And even then it's unbounded, not infinite.)
Only a naive implementation requires infinite memory. (And even then it's unbounded, not infinite.)
See my reply here: https://news.ycombinator.com/item?id=41619279
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.
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.
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.