7 ms·

Hi everybody. I'm the author of the paper. Let me know if you have any questions or comments.

by irwt 7y ago

vermorel 7y ago
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.
- irwt 7y ago
  Very 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?
      - inflatableDodo 7y ago
        He's being funny. "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.
        Angostura 7y ago
        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.
api 7y ago
I'd love a summary "hackers' explanation" if you have time, or a link to some good sample code.
- arberavdullahu 7y ago
  You can find sample code here: https://github.com/arberiii/Bloom-clock https://github.com/arberiii/Bloom-clock
remcob 7y ago
> 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.
- irwt 7y ago
  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.
madmax96 7y ago
Hi! My concern is: >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. Do you have thoughts on this problem?
- adrianmonk 7y ago
  Do the other nodes already have a copy of the bloom filter? If so, could you send an incremental update? You've only changed the bloom filter in K places corresponding to your K hash functions, so seems like you could send a list of the changes you made. (Disclaimer: I haven't read the paper, so I might be way off here.)
  - madmax96 7y ago
    Even with that strategy you need N messages. 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.
    - irwt 7y ago
      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.
showdead 7y ago
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?
- irwt 7y ago
  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 https://haslab.uminho.pt/cbm/files/dbloom.pdf), instead of a normal counting bloom filter.
jbapple 7y ago
Are you familiar with hybrid logical time systems like " HybridTime - Accessible Global Consistency with High Clock Uncertainty" (http://users.ece.utexas.edu/~garg/pdslab/david/hybrid-time-tech-report-01.pdf http://users.ece.utexas.edu/~garg/pdslab/david/hybrid-time-t...) or "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" (https://cse.buffalo.edu/tech-reports/2014-04.pdf https://cse.buffalo.edu/tech-reports/2014-04.pdf)? I'd be interested in reading what you view as the tradeoffs between Bloom clocks and these systems.
- rkallos 7y ago
  I really like the Logical Physical Clocks paper. I'm glad you mentioned it :) There's also Hybrid Vector Clocks which seem to accomplish the same goal as Bloom clocks: https://pdfs.semanticscholar.org/2f05/8c7bfe3ddce90f9715842b2b3a915b1e0862.pdf https://pdfs.semanticscholar.org/2f05/8c7bfe3ddce90f9715842b... http://drops.dagstuhl.de/opus/volltexte/2016/6677/pdf/LIPIcs-OPODIS-2015-34.pdf http://drops.dagstuhl.de/opus/volltexte/2016/6677/pdf/LIPIcs...
- irwt 7y ago
  Thanks for the links. I will read them during the upcoming days and hopefully find some time to write a blog or something. This looks pretty cool.
0xdeadbeefbabe 7y ago
Thanks for sharing the paper. I have a general question, is it best to update the clock after the event or just before or does it matter? How often do the nodes communicate?
- irwt 7y ago
  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.
akashakya 7y ago
> 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.
- zeeboo 7y ago
  They're equivalent representations of the same value. There's no need to propagate anything to anyone.
  - akashakya 7y ago
    Ahh. You are right. I misread the (3)[....] notation. Its not reset but just different representation.
5649884 7y ago
Hi, Are you aware of https://hal.archives-ouvertes.fr/hal-01527110 https://hal.archives-ouvertes.fr/hal-01527110 ? This looks quite similar.
pjscott 7y ago
This is such an elegant idea that I literally laughed with joy for a few seconds when I read the abstract. You made my morning.
- irwt 7y ago
  I'm happy you liked it :)
karlmcguire 7y ago
Thanks for writing this. 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. [1]: https://arxiv.org/abs/1512.00727 https://arxiv.org/abs/1512.00727

Hi everybody. I'm the author of the paper. Let me know if you have any questions or comments.

by irwt 7y ago

Hi everybody. I'm the author of the paper. Let me know if you have any questions or comments.

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.

irwt 7y ago
Very 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?
    - inflatableDodo 7y ago
      He's being funny. "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.
      - Angostura 7y ago
        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.

api 7y ago

I'd love a summary "hackers' explanation" if you have time, or a link to some good sample code.

arberavdullahu 7y ago
You can find sample code here: https://github.com/arberiii/Bloom-clock https://github.com/arberiii/Bloom-clock

remcob 7y ago

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

irwt 7y ago
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.

madmax96 7y ago

Hi! My concern is: >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. Do you have thoughts on this problem?

adrianmonk 7y ago
Do the other nodes already have a copy of the bloom filter? If so, could you send an incremental update? You've only changed the bloom filter in K places corresponding to your K hash functions, so seems like you could send a list of the changes you made. (Disclaimer: I haven't read the paper, so I might be way off here.)
- madmax96 7y ago
  Even with that strategy you need N messages. 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.
  - irwt 7y ago
    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.

showdead 7y ago

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?

irwt 7y ago
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 https://haslab.uminho.pt/cbm/files/dbloom.pdf), instead of a normal counting bloom filter.

jbapple 7y ago

Are you familiar with hybrid logical time systems like " HybridTime - Accessible Global Consistency with High Clock Uncertainty" (http://users.ece.utexas.edu/~garg/pdslab/david/hybrid-time-tech-report-01.pdf http://users.ece.utexas.edu/~garg/pdslab/david/hybrid-time-t...) or "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" (https://cse.buffalo.edu/tech-reports/2014-04.pdf https://cse.buffalo.edu/tech-reports/2014-04.pdf)? I'd be interested in reading what you view as the tradeoffs between Bloom clocks and these systems.

rkallos 7y ago
I really like the Logical Physical Clocks paper. I'm glad you mentioned it :) There's also Hybrid Vector Clocks which seem to accomplish the same goal as Bloom clocks: https://pdfs.semanticscholar.org/2f05/8c7bfe3ddce90f9715842b2b3a915b1e0862.pdf https://pdfs.semanticscholar.org/2f05/8c7bfe3ddce90f9715842b... http://drops.dagstuhl.de/opus/volltexte/2016/6677/pdf/LIPIcs-OPODIS-2015-34.pdf http://drops.dagstuhl.de/opus/volltexte/2016/6677/pdf/LIPIcs...
irwt 7y ago
Thanks for the links. I will read them during the upcoming days and hopefully find some time to write a blog or something. This looks pretty cool.

0xdeadbeefbabe 7y ago

Thanks for sharing the paper. I have a general question, is it best to update the clock after the event or just before or does it matter? How often do the nodes communicate?

irwt 7y ago
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.

akashakya 7y ago

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

zeeboo 7y ago
They're equivalent representations of the same value. There's no need to propagate anything to anyone.
- akashakya 7y ago
  Ahh. You are right. I misread the (3)[....] notation. Its not reset but just different representation.

5649884 7y ago

Hi, Are you aware of https://hal.archives-ouvertes.fr/hal-01527110 https://hal.archives-ouvertes.fr/hal-01527110 ? This looks quite similar.

pjscott 7y ago

This is such an elegant idea that I literally laughed with joy for a few seconds when I read the abstract. You made my morning.

irwt 7y ago
I'm happy you liked it :)

karlmcguire 7y ago

Thanks for writing this. 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. [1]: https://arxiv.org/abs/1512.00727 https://arxiv.org/abs/1512.00727