Interesting 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.
>"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."
> 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?
"I always feel an immediate, unshakable sense of sadness" - presents a personal and serious context - "kind of like when you realize that bad things can happen to good people," - reinforces the seriousness and invites the reader to join the writer in worthy feelings of moral empathy - "or that Keanu Reeves will almost certainly make more money than you over arbitrary time scales." - then punctures it with base motive of bitter jealousy, so you get conflicted by the two very different versions of sadness being presented as the same thing.
Structurally, it is not far off Shakespeare's lawyer joke from King Henry VI;
JACK - when I am king,– as king I will be,–
ALL - God save your majesty!
JACK - I thank you, good people:– there shall be no money; all shall eat and drink on my score; and I will apparel them all in one livery, that they may agree like brothers, and worship me their lord.
DICK. - The first thing we do, let's kill all the lawyers.
This explanation however, has probably stopped it from being funny ever again, for which I humbly apologise.
The problem with the joke is that, it depends on choosing as a target a figure who can be widely reviled. It's a good joke, but it doesn't work when the target is fluffy kittens or Keanu Reeves.
The paper talks about dynamic networks where nodes are being added or removed. If m and k are fixed, does it set an effective upper bound on the number of nodes? How do you address the possibility of multiple nodes having colliding hash values?
Excellent question. I did not address this in the paper, but I probably should have. The upper-bound you mentioned technically does not happen directly because of the nodes, but because of the increased "rate of events" (which can either happen because of the increase of nodes, or because already existing nodes suddenly create more events). Depending on m and k, there will be a rate of events that will cause things to mess up. I'm still brainstorming about this, but I believe we could fix this issue if we'd use a scalable counting bloom filter (https://haslab.uminho.pt/cbm/files/dbloom.pdf), instead of a normal counting bloom filter.
> one can increment a single value outside the bloom filter to keep the values in the bloom filter low. Example: Instead of storing bloom filter [4,3,3,5,7,4,3,3,5], one could store it as (3)[1,0,0,2,4,1,0,0,2].
CMIIW, This only works if it's guaranteed that the reset (transition from high values to low) is propagated to all the nodes.
Which is not the case in a distributed system. Like, if a node is not reachable for a long time and every other node is reset except this one then its possible to have a state in which we can have false negatives.
I'd love to hear your input on a possible application for this. I'm not sure if you're aware, but Counting Bloom Filters are useful as space efficient counters in LFU cache admission/eviction [1].
I'm wondering if bloom clocks would be a good data structure for a space efficient LRU admission/eviction. Full LRU uses a linked list and sampled LRU just uses random sampling, but my intuition is that bloom clocks might perform similarly or better than sampled LRU...
The difficult part will be dealing with concurrency. I suppose it'd be easy to treat threads as "nodes", but not all languages have the luxury of thread-local storage (Go), so I'll cross that bridge when I get there.
Anyways, I'm going to test it out later - thought you might be interested in my thoughts on a possible use.
> Each time a node has an internal event, it hashes that event with k hash functions and increments its bloom filter.
Isn't this effectively the same as generating k random indices? In other words, would the bloom filter work equally well if we pick k random indices to update?
In regular bloom filters this won't work because we want identical elements to collide, but here that doesn't appear to be a concern. I can see how we might want identical nodes to collide (i.e. have the same node use the same indices over and over), but that is not what is going on.
Imagine that node A and B are in sync (they have the same bloom filter). If A sends a new event to B, B can check if A's new event really results in that new bloom filter. You basically have a cryptographic proof that an event really happened at that moment. If the hashes of an event point to different indices, you know that something is wrong.
Edit: Typo.
>Each time a node has an internal event, it hashes that event with k hash functions and increments its bloom filter. It then sends that bloom filter to all other nodes.
I would suspect that the cost of broadcasting the bloom filter to the network would generally outweigh the cost of serializing a vector clock and sending it to a single node. It seems that this step in the algorithm is critical to this approach.
You are right, broadcasting is not a good strategy. I did not really explain the event sharing part in the paper, but as long as everyone multicasts the logical clocks, things should be scalable.
With 64 bits per clock component you can record a billion events per second (literally) for a very long time (as in billions of seconds) before needing to coordinate a clock reset. With 20,000 nodes and a MTU of 1250 bytes you'd only need 128 packets with a traditional vector clock -- contrast this to the (minimum) of 20,000 packets with the Bloom clock. That effect on the network is definitely significant.
Issues like dynamic node membership are interesting, but in practice many useful distributed algorithms that use vector clocks have to carefully control membership anyway. Membership changes are probably rarer than the events tracked by vector clocks. Having a special case for membership in most circumstances treats the network better than sending N messages per event.
EDIT: in other words, suppose you encode each of the N components of the vector clock with E bits. Suppose each packet can contain P bits. As long as (E/P) < 1, the number of messages sent in the system is lower with vector clocks.
Your argument about N messages per event is wrong though. You don't have to broadcast logical clocks to every other node necessarily, that's another issue. As long as every node in the system multicasts the logical clocks, the system-wide clocks will still "move forward" together.
The internal update order shouldn't really matter, as long as you send the right logical clock to other nodes. Communication depends on the system. Imagine the bloom clock a timestmap for your messages. Whenever you send a message, you will send the timestamp with it.
I 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?
Author 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).
It'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.
This 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.
Just 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.
