7 ms·
The Bloom Clock
- jonititan 7y agoThis is an intriguing paper. This seems highly related to proof of work algorithms in blockchain systems. Working out which events happened and at what time.
- tgtweak 7y agoOr distributed databases that are vulnerable to clock skew.
- heavenlyblue 7y ago>> This seems highly related to proof of work algorithms in blockchain systems. Working out which events happened and at what time. This is not a byzantine algorithm so it's got nothing to do with proof of work.
- jonititan 7y agoJust because it's not Byzantine doesn't mean it might not be relevant to proof of work algorithms where one of the challenges is understanding when work was completed relative to other components.
- heavenlyblue 7y agoYou might as well say the flap of the wings of a butterfly in Africa may later become the cause a hurricane in the US.
- filmfact 7y agoIsn’t this a hyperloglog?
- smudgymcscmudge 7y agoI’ve only read the abstract, but I think this does ordering where hyperloglog does presence.
- mfatica 7y agoHyperloglog is an algorithm for approximating distinct elements in a set. This is focused on keeping time.
- JD557 7y agoI think understand the advantages of using a vector clock instead of a timestamp and the advantages of a bloom clock vs vector clocks. But since a bloom clock can sometimes return an incorrect order of events (false positives), wouldn't using the timestamp be a simpler solution on most cases that can allow some unordered events?
- irwt 7y agoAuthor of the paper here. Imagine it like this, if your bloom filter overlaps by a lot an incoming bloom filter, what you can do is go over your logs, find the bloom filter closest by increments to the incoming bloom filter, and then compare them. If the events are not comparable, i.e. concurrent, you will know it immediately. If they are comparable, your false positive rate now will be extremely low (because you picked the bloom filter in your logs that is closest to the one you received).
- jashmenn 7y agoIt's important to keep in mind that the reason we use vector clocks in the first place is because timestamps also can return the incorrect order of events because of time drift, delivery times, etc.
- irwt 7y agoHi everybody. I'm the author of the paper. Let me know if you have any questions or comments.
- vermorel 7y agoInteresting perspective! Do you have any insights whether it would work - or could be modified to work - under adversarial behavior? I.e. assuming that a fraction of the nodes are byzantine.
- irwt 7y agoVery good question. I will have to think about it. Will get back to you later.
- inflatableDodo 7y ago>"Whenever I go to a conference and I discover that there will be a presentation about Byzantine fault tolerance, I always feel an immediate, unshakable sense of sadness, kind of like when you realize that bad things can happen to good people, or that Keanu Reeves will almost certainly make more money than you over arbitrary time scales. Watching a presentation on Byzantine fault tolerance is similar to watching a foreign film from a depressing nation that used to be controlled by the Soviets — the only difference is that computers and networks are constantly failing instead of young Kapruskin being unable to reunite with the girl he fell in love with while he was working in a coal mine beneath an orphanage that was atop a prison that was inside the abstract concept of World War II." James Mickens, 'The Saddest Moment' - https://scholar.harvard.edu/files/mickens/files/thesaddestmoment.pdf https://scholar.harvard.edu/files/mickens/files/thesaddestmo... edit - further wisdom; James Mickens, Associate Professor, Authority On All Things, Harvard - https://mickens.seas.harvard.edu/wisdom-james-mickens https://mickens.seas.harvard.edu/wisdom-james-mickens
- reallydude 7y ago> or that Keanu Reeves will almost certainly make more money than you over arbitrary time scales. Wtf? Reeves is a rather kind man who had some horrific life tragedies and yet managed a successful career (with no scandal). Why would I be sad about that?
- magnamerc 7y agoI feel like this could be useful in DAG data structures.
- deleted 7y ago[deleted]