Hacker News Reader

Comment by lisper | Hacker News Reader

I was responding to this:

> You can't get exactly once delivery using proposed solution in general case because you can not have infinite memory for dedupe.

That is a specific criticism of a specific and highly oversimplified algorithm for de-duplication that I described purely for illustrative purposes, not as a suggestion for how de-duplication should actually be implemented. Actual implementation of de-duplication is much more complicated, but a solved problem that I didn't think I needed to rehash. A real implementation doesn't require infinite memory.

(Actually, even the naive algorithm doesn't require infinite memory, just unbounded memory. Those are not the same.)

View on HN

You certainly do need to rehash it or provide a link to it being solved without constraints on time window, msgs rates and msgs sizes. You also most certainly want to build it and provide it as service because no existing product claims this capability in unbounded case.

> 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.)

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

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.

Reply on news.ycombinator.com