5 ms·

Author here. Pleasantly surprised to see the article here. Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT d

Author here. Pleasantly surprised to see the article here. Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven't seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference. (To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).

riemannzeta 4y ago
Curious to know whether, in your opinion, the use of verifiable delay functions and proof of history represents a more reliable and scalable approach to decentralized time-ordering. https://solana.com/news/proof-of-history---a-clock-for-blockchain https://solana.com/news/proof-of-history---a-clock-for-block...
- lostcolony 4y ago
  Can't speak for op, but can speak as just an observer - probably not. Blockchains are ultimately CP systems, not AP. From that link - "Data can be inserted into the sequence by appending the data to the previous generated state. The state, input data, and count are all published. Appending the input causes all future output to change unpredictably." Meaning there is a single source of truth. That single source is decentralized (because blockchain), but it still requires a quorum to agree to accept a bit of data, and to treat the new state as the valid state. I.e., multiple competing parallel writes must be serialized across a network of computers, which is always more expensive than if they multiple competing parallel writes can be done in parallel. Lamport clocks and etc are AP. It fully expects nodes to make decisions autonomously, and to synchronize after the fact. And data can be lost without realizing it. (The above is all a bit of a simplification, but fundamentally, they're solving different problems)
  - riemannzeta 4y ago
    Yup. Different problem space! Thanks for laying it out clearly.
  - andreareina 4y ago
    Blockchains as commonly deployed seem to be more AP to me: you can get into split-brain and while there's a way to select the canonical form after the partition is healed, that's after the fact. Whereas e.g. Paxos won't even let you do anything without knowing it has quorum.
    - preseinger 3y ago
      alas, because blockchains allow open participation, there is no reliable definition of split-brain, or network membership, or anything at all, really because there is no canonical definition of the set of nodes which represent a source of truth for the state of the blockchain the blockchain state is a function of game theoretical (read: unreliable and non-deterministic) algorithms that assume the result provided a majority (typically 2/3) of participating nodes can be assumed to be valid they are I guess CP based on these assumptions (and others), but those assumptions are probabilistic, they absolutely can be violated, and those violations create forks of the chain which invalidate even the weakest consistency models and nobody seems to care the notion that blockchains are "trustless" is a complete fiction, all state necessarily exists in the context of some trusted authority, decentralization just means that this authority is not well defined, arbitrary from the perspective of its downstream consumers, unaccountable
      - lostcolony 3y ago
        Yeah, I should probably say "they're treated as CP systems", in that they purport CP guarantees, when in reality they adhere to almost none of them (but, they also adhere to none of the traditional expectations of an AP system, i.e., a way to heal partitions and restore some form of consistency).
- thoughtlede 4y ago
  Need more time to think this through. A few comments: 1. The problem space being solved in proof-of-history needs special mention. It assumes byzantine faults. (My article does not). 2. If I understood it correctly, the idea behind proof-of-history is that you perceive the flow of time in "windows". Each window is linked to the state of the previous window (ala blockchain) and has enough randomness built into it that predicting window attributes is a very-low-probability case. When a new event is generated you declare that event to be part of a certain window. You could not have fraudulently backdated your event because the future windows already considered the original future window state (i.e., the state before you inserted your event). You cannot future-date your event because you cannot predict the randomness. 3. At the outset, this is a clever idea. But you mentioned "scalable", I wonder how you would deal with the order of events that are rightfully binned to the same window. Wouldn't you end up with "concurrent events" and find yourself back at square one? 4. At some level, this design can be classified as a causal consistent system. In a non-byzantine world, causal consistent systems can afford network partitions. But in this world, you assume the systems have access to the window-ing system of time flow. Apologies if I grossly misinterpreted the article.
  - riemannzeta 4y ago
    Yes, 1 seems to be the most important difference, with 4 as one of its most important consequences. It's definitely intended to be a solution to Byzantine faults (or double payments as they would show up in practice if the transactions are financial!). I think your summary in 2 is accurate. The answer to scalability 3 seems to be that verifiable delay functions are always costly to solve the first time, but can be checked in parallel -- like a maze that takes time to solve the first time, but can be checked instantly simply by looking to see whether the solution crossed cross any walls. It seems to me like a reasonable technological solution to time-ordering transactions in a decentralized ledger subject to byzantine faults, but I'm not an expert here. It's at the core of the Solana layer 1 blockchain. Solana took it on the chin with the FTX collapse because FTX had chosen Solana as its main exchange and made a heavy investment in its ecosystem. Wondering whether that was an exogenous shock that makes Solana a relative good investment opportunity at the moment. The capability of doing verifications in parallel means verification of 100k transactions per second. Which is on par with what the credit card companies can do.
MuffinFlavored 4y ago
> CRDTs > Conflict-free Replicated Data Types
- Twisol 4y ago
  FWIW, at this point, the initialism has kind of become the name. It's like POSIX -- I doubt a lot of people know what it stands for, but it doesn't matter, because there's only one POSIX and it's the portable operating system interface.
  - andreareina 4y ago
    Not expanding posix will get you a lot fewer blank-eyed stares than not expanding crdt (not that the expansion is particularly useful to someone not already in the space, but it's better than nothing) Apropos, there was an initialism that had "commutative" in it, was that also crdt or something else?
yonz 4y ago
Nice write up, have you looked at Conflict free replicated relations? We have been discussing Lamport clocks and CRDTs in the context of building local-first applications in our LocalFirstWeb discord https://lfw.dev https://lfw.dev. Causality approximated with temporal proximity is a nice way of putting it. I've been trying to wrap my mind around an append only DAG to represent user actions so that multi account, multiuser and multi device experiences can run offline and get to eventually consist state when synced.
- thoughtlede 4y ago
  I have implemented a JSON-like CRDT using this nice tutorial [1], which is a tree, but never an append-only DAG. I'm curious how two edges meeting the same vertex will make it difficult to resolve the conflict automatically? Is it that two users will create the same vertex (concurrently) with slightly different attributes, and attribute-merging requires human-in-the-loop? Of course if the DAG is not append-only, but supports, say, "moving" of edges/branches, it is a totally different problem. Martin has something to say about this [2]. [1] https://www.bartoszsypytkowski.com/operation-based-crdts-json-document/ https://www.bartoszsypytkowski.com/operation-based-crdts-jso... [2] https://martin.kleppmann.com/papers/move-op.pdf https://martin.kleppmann.com/papers/move-op.pdf
  - preseinger 4y ago
    > what will happen [if] we pick minimum values of the corresponding vector clock entries? The resulting vector clock will describe a point in (logical) time seen by both emitters. If we'll fold this minimum over all most recent timestamps received from all replicas, what we get is the timestamp that describes the point in time seen by everyone - so called stable timestamp. > > This timestamp serves us as a check point - since we know that all events prior to it have been acknowledged by all replicas. this is not correct, as there is no reliable definition of "all replicas" -- nothing ensures that all replicas in the system are represented in the accounting for a given entity
- michaelmure 4y ago
  You might be interested by git-bug and https://github.com/MichaelMure/git-bug/blob/master/doc/model.md https://github.com/MichaelMure/git-bug/blob/master/doc/model..., which seems to be exactly what you describe. (Disclaimer: author).
toomim 3y ago
This part isn't quite true: > Conflict-free replicated data types (CRDTs), which are cooperating data structures that can mutate data while being disconnected from each other, use logical clocks as their foundation to preemptively deal with conflicts. Not all CRDTs use logical clocks. You can implement a counter CRDT, for instance, without having to express when in time each edit occurred. It doesn't matter if +1 happened before -3. Both of those events just need to be added together in the end.

riemannzeta 4y ago

Curious to know whether, in your opinion, the use of verifiable delay functions and proof of history represents a more reliable and scalable approach to decentralized time-ordering. https://solana.com/news/proof-of-history---a-clock-for-blockchain https://solana.com/news/proof-of-history---a-clock-for-block...

lostcolony 4y ago
Can't speak for op, but can speak as just an observer - probably not. Blockchains are ultimately CP systems, not AP. From that link - "Data can be inserted into the sequence by appending the data to the previous generated state. The state, input data, and count are all published. Appending the input causes all future output to change unpredictably." Meaning there is a single source of truth. That single source is decentralized (because blockchain), but it still requires a quorum to agree to accept a bit of data, and to treat the new state as the valid state. I.e., multiple competing parallel writes must be serialized across a network of computers, which is always more expensive than if they multiple competing parallel writes can be done in parallel. Lamport clocks and etc are AP. It fully expects nodes to make decisions autonomously, and to synchronize after the fact. And data can be lost without realizing it. (The above is all a bit of a simplification, but fundamentally, they're solving different problems)
- riemannzeta 4y ago
  Yup. Different problem space! Thanks for laying it out clearly.
- andreareina 4y ago
  Blockchains as commonly deployed seem to be more AP to me: you can get into split-brain and while there's a way to select the canonical form after the partition is healed, that's after the fact. Whereas e.g. Paxos won't even let you do anything without knowing it has quorum.
  - preseinger 3y ago
    alas, because blockchains allow open participation, there is no reliable definition of split-brain, or network membership, or anything at all, really because there is no canonical definition of the set of nodes which represent a source of truth for the state of the blockchain the blockchain state is a function of game theoretical (read: unreliable and non-deterministic) algorithms that assume the result provided a majority (typically 2/3) of participating nodes can be assumed to be valid they are I guess CP based on these assumptions (and others), but those assumptions are probabilistic, they absolutely can be violated, and those violations create forks of the chain which invalidate even the weakest consistency models and nobody seems to care the notion that blockchains are "trustless" is a complete fiction, all state necessarily exists in the context of some trusted authority, decentralization just means that this authority is not well defined, arbitrary from the perspective of its downstream consumers, unaccountable
    - lostcolony 3y ago
      Yeah, I should probably say "they're treated as CP systems", in that they purport CP guarantees, when in reality they adhere to almost none of them (but, they also adhere to none of the traditional expectations of an AP system, i.e., a way to heal partitions and restore some form of consistency).
thoughtlede 4y ago
Need more time to think this through. A few comments: 1. The problem space being solved in proof-of-history needs special mention. It assumes byzantine faults. (My article does not). 2. If I understood it correctly, the idea behind proof-of-history is that you perceive the flow of time in "windows". Each window is linked to the state of the previous window (ala blockchain) and has enough randomness built into it that predicting window attributes is a very-low-probability case. When a new event is generated you declare that event to be part of a certain window. You could not have fraudulently backdated your event because the future windows already considered the original future window state (i.e., the state before you inserted your event). You cannot future-date your event because you cannot predict the randomness. 3. At the outset, this is a clever idea. But you mentioned "scalable", I wonder how you would deal with the order of events that are rightfully binned to the same window. Wouldn't you end up with "concurrent events" and find yourself back at square one? 4. At some level, this design can be classified as a causal consistent system. In a non-byzantine world, causal consistent systems can afford network partitions. But in this world, you assume the systems have access to the window-ing system of time flow. Apologies if I grossly misinterpreted the article.
- riemannzeta 4y ago
  Yes, 1 seems to be the most important difference, with 4 as one of its most important consequences. It's definitely intended to be a solution to Byzantine faults (or double payments as they would show up in practice if the transactions are financial!). I think your summary in 2 is accurate. The answer to scalability 3 seems to be that verifiable delay functions are always costly to solve the first time, but can be checked in parallel -- like a maze that takes time to solve the first time, but can be checked instantly simply by looking to see whether the solution crossed cross any walls. It seems to me like a reasonable technological solution to time-ordering transactions in a decentralized ledger subject to byzantine faults, but I'm not an expert here. It's at the core of the Solana layer 1 blockchain. Solana took it on the chin with the FTX collapse because FTX had chosen Solana as its main exchange and made a heavy investment in its ecosystem. Wondering whether that was an exogenous shock that makes Solana a relative good investment opportunity at the moment. The capability of doing verifications in parallel means verification of 100k transactions per second. Which is on par with what the credit card companies can do.

MuffinFlavored 4y ago

> CRDTs > Conflict-free Replicated Data Types

Twisol 4y ago
FWIW, at this point, the initialism has kind of become the name. It's like POSIX -- I doubt a lot of people know what it stands for, but it doesn't matter, because there's only one POSIX and it's the portable operating system interface.
- andreareina 4y ago
  Not expanding posix will get you a lot fewer blank-eyed stares than not expanding crdt (not that the expansion is particularly useful to someone not already in the space, but it's better than nothing) Apropos, there was an initialism that had "commutative" in it, was that also crdt or something else?

yonz 4y ago

Nice write up, have you looked at Conflict free replicated relations? We have been discussing Lamport clocks and CRDTs in the context of building local-first applications in our LocalFirstWeb discord https://lfw.dev https://lfw.dev. Causality approximated with temporal proximity is a nice way of putting it. I've been trying to wrap my mind around an append only DAG to represent user actions so that multi account, multiuser and multi device experiences can run offline and get to eventually consist state when synced.

thoughtlede 4y ago
I have implemented a JSON-like CRDT using this nice tutorial [1], which is a tree, but never an append-only DAG. I'm curious how two edges meeting the same vertex will make it difficult to resolve the conflict automatically? Is it that two users will create the same vertex (concurrently) with slightly different attributes, and attribute-merging requires human-in-the-loop? Of course if the DAG is not append-only, but supports, say, "moving" of edges/branches, it is a totally different problem. Martin has something to say about this [2]. [1] https://www.bartoszsypytkowski.com/operation-based-crdts-json-document/ https://www.bartoszsypytkowski.com/operation-based-crdts-jso... [2] https://martin.kleppmann.com/papers/move-op.pdf https://martin.kleppmann.com/papers/move-op.pdf
- preseinger 4y ago
  > what will happen [if] we pick minimum values of the corresponding vector clock entries? The resulting vector clock will describe a point in (logical) time seen by both emitters. If we'll fold this minimum over all most recent timestamps received from all replicas, what we get is the timestamp that describes the point in time seen by everyone - so called stable timestamp. > > This timestamp serves us as a check point - since we know that all events prior to it have been acknowledged by all replicas. this is not correct, as there is no reliable definition of "all replicas" -- nothing ensures that all replicas in the system are represented in the accounting for a given entity
michaelmure 4y ago
You might be interested by git-bug and https://github.com/MichaelMure/git-bug/blob/master/doc/model.md https://github.com/MichaelMure/git-bug/blob/master/doc/model..., which seems to be exactly what you describe. (Disclaimer: author).

toomim 3y ago

This part isn't quite true: > Conflict-free replicated data types (CRDTs), which are cooperating data structures that can mutate data while being disconnected from each other, use logical clocks as their foundation to preemptively deal with conflicts. Not all CRDTs use logical clocks. You can implement a counter CRDT, for instance, without having to express when in time each edit occurred. It doesn't matter if +1 happened before -3. Both of those events just need to be added together in the end.