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).
> 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.
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.
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.
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].
> 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
> CRDT: Replicated state machines allow for generic fault tolerant systems. It does this by having consensus on append to a command log. But if the commands are commutative, those could be applied in any order. There is subset on optimizations on paxos for concurrent commutative commands, called Generalized Paxos. In the extreme case, if all operations are commutative, then you have this nice situation where you don't need consensus. And replicas can converge on the same state, eventually. These data structures with commutative operations are called CRDT.
My thoughts on how clocks, sync and CRDT are related. Not an authority on the subject, so could be quite wrong.
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.
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?
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.
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.
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.
net TPS for by a distributed and BFT system is going to be bottlenecked by the cost of information exchange between participating nodes, which is a function of protocol design and, ultimately, network bandwidth/latency
any basic server-class hardware can saturate normal network capabilities with no special effort: a single core, a few hundreds of megabytes of system memory, is all you need to push 1Gbps, probably even 10Gbps
but solana defines hardware requirements for validator nodes https://docs.solana.com/running-validator/validator-reqs that stipulate, at minimum, 12 physical cores, 128GB of RAM, and independent PCIe NVME SSDs for specific types of persisted state
even accounting for the additional work you need to do in a trustless/open/BFT/etc. protocol, these requirements are orders of magnitude beyond what should be necessary, and pretty clearly indicate that solana is very much at the "naive prototype" stage, technically
also, fwiw, solana is not doing the claimed theoretical maximum ~700k TPS, or even 100K TPS, but just 3k TPS, as reported by https://explorer.solana.com
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)
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.
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
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).
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).