The abstract discusses the style in terms of in-process concurrent execution, but does anyone know of similar research for distributed systems? While I’m aware of CRDT’s and the associated literature, one thing that has been a source of bugs, just because it’s easy to forget, is relations in an eventually consistent system. It’s not uncommon to have one key map to a manifest of other keys to read for a particular value, but you don’t have a guarantee of those other keys being there either. 99.99% of the time this works just fine, but unless you’ve designed your software around it, that small percentage could bite. I suppose casual consistency could be used here.
I would rather use a transactional system for managing references in cases that the entire reference chain has to be present, because you either need to delay reads or induce a ton of failures and/or latency when you descend into a reference tree that has non-accessible elements, requiring another traversal attempt on an earlier version of the root node (assuming your references form an immutable DAG, and stale data is useful) any time a traversal is attempted before consistency is reached. This isn’t as horrible when you can tolerate partial results. If you do require more, you may be better off at least starting with leaves and working your way up, similar to shadow paging, and requiring some consistency threshold be crossed before moving to the next level.
In cases where you have to be tolerant of lots of failures AND require an entire reference chain for it to be useful, I think you need to rely on wall-time in some way to delay non-referred reads (only the root should be delayed explicitly) if you want to try to shield clients from retrying on earlier versions after failed partial traversals.
The manifest solution I described is somewhat common in key-value stores where you want to limit which part of the keyspace is actually mutable.
I think you need to rely on wall-time in some way to delay non-referred reads
As I typed the initial question I realized that causal consistency solves the problem. Wall-time would not solve the problem given long-tail behaviour.
Looking forward to reading!
The abstract discusses the style in terms of in-process concurrent execution, but does anyone know of similar research for distributed systems? While I’m aware of CRDT’s and the associated literature, one thing that has been a source of bugs, just because it’s easy to forget, is relations in an eventually consistent system. It’s not uncommon to have one key map to a manifest of other keys to read for a particular value, but you don’t have a guarantee of those other keys being there either. 99.99% of the time this works just fine, but unless you’ve designed your software around it, that small percentage could bite. I suppose casual consistency could be used here.
I would rather use a transactional system for managing references in cases that the entire reference chain has to be present, because you either need to delay reads or induce a ton of failures and/or latency when you descend into a reference tree that has non-accessible elements, requiring another traversal attempt on an earlier version of the root node (assuming your references form an immutable DAG, and stale data is useful) any time a traversal is attempted before consistency is reached. This isn’t as horrible when you can tolerate partial results. If you do require more, you may be better off at least starting with leaves and working your way up, similar to shadow paging, and requiring some consistency threshold be crossed before moving to the next level.
In cases where you have to be tolerant of lots of failures AND require an entire reference chain for it to be useful, I think you need to rely on wall-time in some way to delay non-referred reads (only the root should be delayed explicitly) if you want to try to shield clients from retrying on earlier versions after failed partial traversals.
The manifest solution I described is somewhat common in key-value stores where you want to limit which part of the keyspace is actually mutable.
As I typed the initial question I realized that causal consistency solves the problem. Wall-time would not solve the problem given long-tail behaviour.