If the block is urgent then issue an ack block.

Existing algorithms for payment systems, including the onesin [ 1, 6 , 11], are based on reliable broadcast (RB) [ 2] to disseminateblocks to other agents. RB is an abstraction that prevents Byzantineagents from equivocating, which in the context of a payment systemprevents Byzantine agents from doublespending

Contrary to current DAG-like structures that use hashesof content, a blocklace uses signed hashes from which theblock creator can be known. Not only this can aid dissemina-tion, by knowing which node is missing which blocks, butmore importantly, it can be used to detect equivocations andequivocators

In-deed, the blocklace-based Cordial Dissemination protocol [7,12] employs the fact that a 푝-block 푏 by a correct node 푝 ac-knowledges all the blocks known to 푝 at the time of blockcreation

To be a colluder, 푝 must violate liveness, as it must refuseindefinitely to accept blocks by correct agents that acknowl-edge 푞 as Byzantine.

Accept the block into the blocklace, resulting in all nodeseventually knowing that 푝 is Byzantine

node

Correct nodes create a new block in 퐵 using the identitiesof the set of maximals in 퐵 as predecessors. By definition,all the elements in this set are incomparable, forming anantichain. If that is not the case, the creator is Byzantine

and eventu-ally excluding any new blocks created by Byzantine agents

Extant approaches no not attempt to detect equivocations.Messages from Byzantine equivocators that are not rejectedas invalid are simply accepted and treated as if they wereconcurrent operations from different correct nodes.

A blocklace 퐵 is then isomorphic to a PO-Log from thepure-op framework, thus is also a pure-op CRDT

were max≺ (퐵) is the set of maximal blocks in 퐵 under the≺ relation, i.e., the blocks which are not pointed from anyother block in 퐵

Note that the virtual chain axiom holds for correct nodessince they create blocks in sequence and include each newblock in their blocklace

Thus, there are no “dangling pointers” in a blocklace: eachidentity in each set of predecessors of a block in a blocklaceidentifies a block in the blocklace.

Weassume that the identity (public key) of the node can be ex-tracted from its signature, e.g., using ECDSA.

We remark that even if two nodes 푝, 푞 ∈ Π hold identi-cal blocklaces, and each of these nodes creates a new blockwith the same payload and same set of predecessor blocks,and therefore with the same hash, block identities will bedifferent as the hash will be signed by the different privatekeys of 푝 and 푞.

An op-based CRDT is pure if mes-sages contain only the operation (including arguments, if any).

The possi-bility of a stable operation obsoleting a new arrival, in its causal future, is notconsidered, but this can easily be changed if some example shows its usefulness

Here we not only need this to happen but also that no further concur-rent messages may be delivered. Therefore, causal stability is a stronger notion,implying classic message stability

As such, a pure op-basedCRDT implementation is trivial: as when using the standard causal broadcast,the message returned from prepare, containing the operation, will arrive exactlyonce at each replica, it is enough to make effect consist simply in applying thereceived operation to the state, over a standard sequential datatype, i.e., definingfor any datatype operation o:

Commutative datatypes reflect a principle of permutation equivalence [11]stating that “If all sequential permutations of updates lead to equivalent states,then it should also hold that concurrent executions of the updates lead to equiv-alent states”

Op-based CRDTs can often have a simple and compact state since they can relyon the exactly-once delivery properties of the broadcast service, and thus donot have to explicitly handle non-idempotent operations.

I think this would modify your trust model. Say you trusted 10 peers. If one of them was malicious, then you have 1/10 malcious peers and the majority of nodes are good so you could identify the bad node. In the changes you propose, (if I understand correctly), the 1 malicious node, could then send you 100 more malicious nodes. So then you'd be connected to 101/110 malicious peers and the malicious peers would be the majority.

VectorSync [31] is an enhanced version of ChronoSync[35] which uses version vectors to make synchronisationbetween peers more efficient. Version vectors are more efficientin detection of inconsistencies, than simple message digests, asmentioned earlier. However, similarly to other proposals in thearea, VectorSync needs to realise a ‘leader-based membershipmanagement’ in order to deal with active members that updatethe state of the dataset.

Moreover, after executing an inverse opera-tion like O2, the document state can no longer be properlyrepresented by the state vector, which is only capable ofrepresenting original normal editing operations

I get a new ClientID for every session, is there a way to make it static for a peer accessing the document?

Furthermore, due to its design, the garbage collector inYATA may break late join mechanisms. This is becausewhen a user is offline for a period longer than t seconds,it will still hold references to deleted operations, while on-line users who already performed certain removals do not.Therefore, YATA does not support garbage collection for asite while it is offline.

From our practical experi-ences and the use in production, such a delay is sufficientto ensure that content will be removed safely, without anylosses that may lead to inconsistencies

Conceptually, an insertion marked for deletioncan be garbage collected when all sites received the removeoperation and have in their internal representation the op-eration that is to be garbage collected

We denote an insert operation as ok (idk , origink , lef tk ,rightk , isDeletedk , contentk )

Upon its creation, the operation thus gets as-signed a unique identifier which is composed of the useridand the current operation counter

The downside ofthis approach is that a state vector must be transmittedwith every operation, where the size of the state vector isproportional to the number of users in a collaborative ses-sion.

COT has a simplified design, as only onetransformation function must be defined

The ideabehind COT is to save every received operation “as is” in adocument state and preprocess it afterwards given the op-eration context.

If you tried to join two lists together, but somebody has added a paragraph between them, your change becomes impossible to execute (you can't join nodes that aren't adjacent), so it is dropped.

Instead of a central server calling the shots, you could use a consensus algorithm like Raft to pick an arbiter. (But note that I have not actually tried this.)

Secondly, though most OT systems just represent changes as a series of insertions and deletions, mapping seems to require us to distinguish replacements from the corresponding delete/insert pair. When a replacement happens next to a given position, the position should never move across the replacement, regardless of whether you're mapping forward or backward. In order to be able to support this, CodeMirror's change representation is encoded as a series of replacements. (Insertions become replacements that don't delete anything, and deletions replacements that don't insert anything.)

This can be derived from a sequence of individual changes, but it seems like it'd be more pleasant if changes were directly kept in that shape.

When a client receives conflicting remote changes, it first undoes all its local pending changes, applies the remote changes, and then the transformed form of its local changes.

OT algorithms that support decentralized editing rather resemble CRDT algorithms

along with data (often a logical clock) embedded in the IDs

That is where CRDTs come in. They are another approach to convergence that, contrary to operational transformation, does provide a way for us mortals to reason about convergence.

And when you don't have a centralized party to determine the order in which changes get applied, you need, as far as I understand the literature, to keep data beyond the current document (“tombstones” that describe where deletions happened), to guarantee convergence.

Periodically try to send those to the server, which will either accept them or, if another client sent a change first, reject them because your changes start in a base document that doesn't match the current central document.

But it does drag in a lot of problems, even outside of the document convergence—peers have to store the document along with, depending on the technique used, its entire history.

Consistency models

Moreover, the ordering is effectively determined by the effects of the operations when they are generated

Consequently, the total order becomes application specific

The invocation of every operation is admissible in its execution state

The above CSM model requires that a total order of all objects in the system be specified

Second, it was defined as operation context-based pre- and post- transformation conditions for generic OT functions

The Awareness CRDT must only apply updates if the received clock is newer / larger than the currently known clock for that client

we always exchange the whole state of all locally known clients

This collaborator can then deserialize it back and generate an update which will contain all new changes performed since provided state vector

JSON-Schema with namespaces

It should be obvious by now that causal histories work but are not very compact

to work withother linearizations we have to build their respec-tive chronofolds.

Thatcosts O(N ) and from that perspective we mightbe tempted to store that mapping in a hash map

Next, it has to findthe op’s position in the weave and relink the linkedlist to include the new op at that position

Weave is the most natural data struc-ture for diffing and merging, but editing a weavealso requires splicing

CRDT overheads and complexity are rooted inthe use of per-character ids and the need to mapthem to positions in the weave and the text

The top issue with a weave isthat it needs to be spliced on every edit (i.e. rewrit-ten in full), very much like a plain string

CT parent

for all β ∈ proc(R).

Atimestamp is an ordered pair t = ⟨n, α⟩ where α isthe author also denoted by auth(t), and n is theauthor’s index also denoted by andx(t).

Merged deltas work as follows

Fig. 2: A r e v i s i o n t r e e w i t h f o r w a r d a n d r e v e r s e d e l t a s .

increment: 2

For example, we can use it to inform observers of this model that its state has changed. Let's add that to our example, by calling cx.notify().

The handle doesn't truly own the state, but it can be used to access the state from its true owner, the AppContext.

If the subsequent frame contains the same text-font pair, the shaped glyphs get reused.

We experimented with Patrick Walton's Pathfinder crate, but it wasn't fast enough to achieve our performance goals

It's a tight deadline

A modern display's refresh rate ranges from 60 to 120 frames per second

but we may eventually introduce the ability to undo operations of collaborators

A shared global stack of edit operations isn't enough

Dr. Victor Grishchenko, Oleg Lebedev, Yuri Syrovetskiy and Nikita Prokopov

map_err

Tasks are the top-level futures that have been submitted to an executor.

OS threads don't require any changes to the programming model, which makes it very easy to express concurrency. However, synchronizing between threads can be difficult, and the performance overhead is large. Thread pools can mitigate some of these costs, but not enough to support massive IO-bound workloads.

Tasks are assumed to run concurrently, potentially by sharing a thread of execution.

block_on

Option<Arc<Node<T>>

Collects all the items from an iterator into a collection.

&mut

.iter().map

if t ≠ ref(t)

The whitened signature is the signature XORed with thesignatures of all unique famous witnesses in the received round.

If a pure function mutates some local data in order to produce an immutable return value, is that ok? It’s an interesting question. Clojure data structures use mutation every time you call, e.g. assoc, creating one or more arrays and mutating them, before returning them for immutable use thereafter. The reason is performance - you simply can’t get as fast using only pure functions and immutable data. Once constructed and shared however, being immutable and persistent is essential to robust programs. The things Clojure mutates internally are small, newly allocated arrays that constitute the internal nodes of its data structures. No one ever sees the arrays.

Once round r is settled, thefuture rounds will reshuffle, and the calculations for round r + 1 famous witnesseswill be done using the new stake record.

When wave 𝑤 completes (Line 34), we use the global perfectcoin to retrospectively elect some process and consider its vertexin the wave’s first round as the leader of wave 𝑤 (Line 35).

In a nutshell, the idea is to interpret the DAG as a wave-by-wave protocol and try to commit a randomly chosen single leadervertex in every wave.

Our validity property requiresthat all messages broadcast by correct processes are eventually or-dered (with probability 1), whereas most Byzantine SMR protocols(i.g., [ 17, 37 , 43 ] require that in an infinite run, an infinite number ofdecisions are made, but some proposals by correct processes can beignored.

optimal qua-dratic communication

The message complexity is herebyimproved to O(n).

O(n log n)

set of each event z such that z isa self -ancestor of a round r unique famouswitness , and x is an ancestor of z but notof the self -parent of z

(d), one event (orange) is an ancestorof each of 4 intermediate events by different creators (red)

Amuch faster approach is to pick just a few events (vertices in the hashgraph),to be called witnesses, and define a witness to be famous if the hashgraphshows that most members received it fairly soon after it was created

x.famous ← UNDECIDED

If two events have the same received round, then they are sorted by theirreceived time

If Alice and Bob both have the same hashgraph, then theycan calculate a total order on the events according to any deterministic function ofthat hashgraph, and they will both get the same answer. Therefore, consensus isachieved, even without sending vote messages

When Bob sends an event to Carol, that sequence number can be calculated byCarol, so there is no need for Bob to actually send it over the internet

Only the state itself needs to bekept. It might be possible to do this every few minutes, so there will never be ahuge number of transactions and events stored. Only the consensus state itself. Ofcourse, a member is free to preserve the old events, transactions, and states, perhapsfor archive or audit purposes. But the system is still immutable and secure, evenif everyone discards that old information.

To defend against attackers whocan control the internet, there are periodic coin rounds where witnesses can votepseudorandomly. This means that even if an attacker can control all the messagesgoing over the internet to keep the votes carefully split, there is still a chancethat the community will randomly cross the 2n/3 threshold. And so agreement iseventually reached, with probability one.

The protocol might re-quire that Alice send those events in topological order, so Bob will always have anevent’s parents before receiving the event

to a random member

Issuing a Transaction: The client c1 composes and signs a transaction.Client c1 sends the transaction to the validators. If the inputs of the trans-action are not part of genesis, the client also sends the confirmations of theinputs to the validators.

Finally, the high communication complexity of the underlying protocols, i. e., consensus of shards, handling cross-shard transactions, and bootstrapping of participants to shards, can make the bandwidth become the bottleneck.

Furthermore, we show that against a somewhat adaptive adversary, sharding protocolsmust periodically compact the state updates (e. g., via checkpoints [26], cryptographic accumulators [7], zero-knowledgeproofs [6, 31] or other techniques [12, 19–21]); otherwise, the necessary bandwidth resources of each participantincrease infinitely in time, eventually exceeding the resources needed in a non-sharded blockchain

Additionally, we show that scalable sharding isimpossible if participants maintain (and verify) information on all other shards with which they execute cross-shardtransactions. This happens because the storage requirements become proportional to that of a non-sharded protocol.

To this end,Bob’s representative replica collects and aggregates CREDITmessages for the same incoming payment into a dependencycertificate for Bob’s xlog.

has messagecomplexity of O(N 2)

Astro guarantees total order within—but not across—xlogs

Essentially, preventing Alice from double-spending meanspreventing her from reusing sequence numbers. To do so, thebroadcast layer in Astro provides Byzantine resilience. Thisensures that a malicious client cannot broadcast two differentpayments with the same sequence number.

unlike consensus

Astro builds on the insight that consensus is unnecessary toprevent double-spending

Figure 1

While that prohibits applications thatneed a unique total ordering on conflicting transactions, likecryptocurrencies where double spending must be prevented

The gossip-about-gossip method allows for the history ofall the communications within an infrastructure to be reconstructed

None of these methods, though, includesdynamic membership, and this is a key differentiator in this paper

is proved in section 5 that if x and y are ondifferent branches of an illegal fork, then w can strongly see at most one of x andy, but not both.

If there are n members (n > 1), then an event w can strongly see an event x,if w can see more than 2n/3 events by different members, each of which can seex.

In other words, w can see x if x is known to it, and no forksby that creator are known to it

If Aliceis honest, she will calculate virtual votes for the virtual Bob that are honest. Evenif the real Bob is a cheater, he cannot attack Alice by making the virtual Bob voteincorrectly.

The otherancestor events (gray) are not stored in the red event, but theyare determined by all the hashes. The other self-ancestors (darkgray) are those reachable by sequences of self-parent links, and theothers (light gray) are not.

Most Byzantine fault tolerance protocols without aleader depend on members sending each other votes. So for n members to agreeon a single YES/NO question might require O(n2) voting messages to be sent overthe network, as every member tells every other member their vote. Some of theseprotocols require receipts on votes sent to everyone, making them O(n3). And theymay require multiple rounds of voting, which further increases the number of votingmessages sent.

It is sufficient to tell Carol that this event is the next one by Alice, and that itsother-parent is the third one by Bob. With appropriate compression, this can besent in very few bytes, adding only a few percent to the size of the message beingsent.

Alice will not send Carol the red event until Carol alreadyhas all its earlier ancestors

Instead of Alice signing a transaction she creates, she will sign theevent she creates to contain that transaction. Either way, she is only sending onesignature

Virtual voting - every member has a copy of the hashgraph, so Alice cancalculate what vote Bob would have sent her, if they had been runninga traditional Byzantine agreement protocol that involved sending votes.So Bob doesn’t need to actually her the vote.

Fairness - it should be difficult for a small group of attackers to unfairlyinfluence the order of transactions that is chosen as the consensus.

An algorithm for a single YES/NO decision can then be extended to decidinga total order on a set of transactions, which may further increase the vote traffic.

A proof-of-expired-timesystem [9] can avoid the wasted electricity (though perhaps not the cost of miningrigs) by using trusted hardware chips that delay for long periods, as if they weredoing proof-of-work computations.

It also means that itis necessary to slow down how fast blocks are mined, so that the community canjointly prune branches faster than new branches sprout. That is the purpose of theproof-of-work. By requiring that the miners solve difficult computation problemsto mine a block, it can ensure that the entire network will have sufficiently longdelays between mining events, on average

though at any time, if an honest memberrepeatedly sends messages to another member, the attackers must eventually allowone through

Example 9.3 (Bait-and-Switch Attack).

In the permissioned setting there is the following inter-esting line of research. The aim is to construct an atomicbroadcast protocol based on a combined encoding of thedata transmission history and voting on “leader blocks”.Such protocols allow the network participants to reach aconsensus on a total ordering of the received transactions,and this linearised output forms the ledger.

The main difference of our proposal to all the aforemen-tioned protocols is that consensus is found on the heaviestDAG without the need for a “linearisation” using any leaderselection. This reduces the purposes of blocks to data trans-mission and voting

These protocolsremove the bottleneck of data dissemination of the classicalNakamoto consensus by decoupling the data disseminationfrom the consensus finding

Blockchain-based protocols relyon a chain or “linearisation” of blocks that create a totalorder of transactions. These blocks have three purposes:leader election, data transmission and voting for ancestorblocks through the chain structure, see [34]. Each of theseaspects can be, individually or combined, addressed througha DAG-based component. The various proposals differ inhow and which of these components are replaced by a DAG.

Tangle 2.0Leaderless Nakamoto Consensus on the Heaviest DAG

However, as soon as a node from X changesits vote, the resulting situation is symmetric to the initialcondition

Upon receipt of the missing parent block,the past cone is now complete (unless their parents aremissing - in which case the node has to repeat this procedurerecursively).

Improvements are proposed,for example, in Hashgraph [41] and Aleph [42] and morerecently in Narwhal [43] based on the encoding of the “com-munication history” in the form of a DAG

Probabilistic. The units appended to the system are alwaysaccompanied by the risk of being reversed. The probability isinversely proportional to its cumulative confidence (includ-ing the forms of depth/score/weight etc). The confidence isobtained from the contributions of subsequent units.- Deterministic. The units, once attached to the system atsome point in time, will instantly and permanently get con-firmed so that they can never be removed from the system.

5.1 Properties Between BA and NC

Secondly, building smartcontracts or state transition applications rely on linear order

Each partici-pated node maintains a separate chain, and nodes mutually interactvia the gossip protocol. The node locally creates an event to recordthe history of received information

Graphchain, instead, introduces an incentivemechanism to maintain the graph. Transactions are required topost transaction fees as the offering for collection. That means eachtransaction must refer to a group of ancestor transactions to de-plete their deposit (fees) when verifying the validity. Meanwhile,ancestor transactions must have enough fees for collection. Feesare depleted by incoming transactions from the oldest ancestorsin paths to reach a prescribed total amount. High-fee transactionsattract powerful miners working in parallel for rapid confirmation,while low-fee transactions will finally be picked up by a small miner.Based on this design, Graphchain makes the current transactionsquickly become enshrined in the ancestry of all future transactions.

Specifically,the extension of the tangle follows the rule3 where one tip (pend-ing/unapproved transaction) is required to approve two ancestortransactions. Thus, users who issue a transaction will contributeto the security of the system.

several systems,both tie-breaking and conflict solving are integrated intothe extension rule. The consensus mechanism, by this way,reaches the agreement in one-step

Unlike the alternatives, HoneyBadgerBFTsimply does not care about the underlying network

A program withnon-monotonicity can be made consistent by including coordinationlogic at its points of order.

The most telling example fromSection 3.2 is the use of tombstoning for low-latency deletion. Inpractice, memory for tombstoned items must be reclaimed, so even-tually all machines need to agree to delete some items.

A related pattern in storage systems is the use of tombstones: specialdata values that mark a data item as deleted. Instead of explicitlyallowing deletion (a non-monotonic construct), tombstones maskedimmutable values with corresponding immutable tombstone val-ues.

CALM provides the formal framework forthe widespread intuition that we can indeed “work around CAP”in many cases, even if we violate traditional systems-level notionsof storage consistency.

This is the conclusion of the Dynamo design.In later work [18 ], we go further to make checkout monotonic inthis setting as well. : the checkout operation is enhanced with amanifest from the client of all its update message IDs that precededthe checkout message: replicas can delay processing of the checkoutmessage until they have processed all updates in the manifest

A keyinvariant of these coherence protocols is thateither 1) a cache line is not present in anycache, 2) a mutable copyis present in a single cache,or 3) the line is present in anynumber of caches but is immutable

At the core of this dissertation’s approach is this scalable commutativityrule: In anysituation where several operations commute—meaning there’s no wayto distinguish theirexecution order using the interface—theyhave a implementation that is conflict-free duringthoseoperations—meaning no corewrites acachelinethat was reador written byanother core.Empirically, conflict-free operations scale, so this implementation scales. Or, more concisely,whenever interface operations commute, theycan be implemented in a waythat scales.

Importantly, the external transaction determines valid modifiers of each state.

It isinflexible for a node to join or leave a workflow at any time since the config-uration of channels is fixed.

Moreover, interactions between channels rely on atrusted channel [3] or an atomic commit protocol [2], which either breaks thedecentralization or still treat the system as an entirety.

The configuration of a channel may be updated using achannel configuration update transaction. This transactioncontains a representation of the changes to be made to theconfiguration, as well as a set of signatures.

The relative ordering of aborted trans-actions is kept the same. As a result, every transaction cancommit eventually, since the first transaction in a batch al-ways commits and the position of an aborted transactionalways moves forward across batches

However, as the orderingbetween transactions is determined by consensus and fixedacross all nodes, we leverage this to permit both transactionsto write to different copies of the object, but subsequentlycommit only the first as determined by the ordering.

Hot Key Theorem. Let l be the average time between atransaction’s execution and its state transition commitment.Then the average effective throughput for all transactionsoperating on the same key is at most 1l .

With this optimization, TAPIR can now accept: (1) readsof past versions, as long as the read timestamp precedes thewrite timestamp of the next version, and (2) writes in thepast (per the Thomas Write Rule [45]), as long as the writetimestamp follows the read timestamp of the previous versionand precedes the write timestamp of the next version.

A peer checks if a sufficient number of valid endorsingpeer signatures, based on the endorsement policy, have been col-lected (Validation System Chaincode (VSCC) validation)

Table 1: Notations for sets

Optionally, the clientmay check the validity of the endorsing peers signatures and theconsistency between the read/write set received from differentpeers.

The client collects the endorsing peers responses andsends them to the ordering service nodes

First, wedeliberately do not send transaction read-write sets to theorderers, only transaction IDs. Second, we chose to keep toFabric’s design goal of allocating different tasks to differenttypes of nodes, so our orderers do not examine the contents ofthe read and write sets

Arguably, the use of BFT protocols in permissionedblockchains is not as important as in permissionless sys-tems because all participants are known and incentivizedto keep the system running in an honest manner.

(a) to achieve con-sensus on the transaction order

Transactions follow an execute-order-commit flowpattern instead of the common order-execute-commit pattern.Client transactions are first executed in a sandbox to determinetheir read-write sets, i.e., the set of keys read by and writtento by the transaction. Transactions are then ordered by anordering service, and finally validated and committed to theblockchain

Furthermore, it doesn’t say that every reorderinghas indistinguishable results on a given implementation;it requires instead that every reordering is allowed bythe specification to have indistinguishable results.

But as noted above, a partial order like happens-before is iso-morphic to a join semi-lattice! That means that we can capture theCmRDT log as a CvRDT. One simple way to do this is to hold theDAG corresponding to the partial order: this is simply a “grow-only”set—whose only operation is add—which holds edges of a DAG.Each directed edge connects two operations, and indicates that theoperations happened in the order of the edge. (Another solutionwould be to use CvRDTs for vector clocks.) A natural query oversuch a CvRDT is to “play the log”: i.e. produce a topological sort ofthe log and apply the operations in the resulting order.

Instead of explicitly allowing deletion (a non-monotonic construct), tombstones mask immutable values with corresponding immutable tombstone values.

deletion (a non-monotonic construct)

Unfortunately, neither the add nor delete operation commutes with checkout—if a checkout message arrives before some insertions into either the Added or Deleted sets, those insertions will be lost.

As a traditional approach to avoid such "race conditions," we might bracket every non-monotonic delete operation with a global coordination to agree on which add requests come before it. Can we do better?

However, this powerful abstractioncomes with a hefty cost: concurrent transactions must coordinate inorder to prevent read/write conflicts that could compromise equiv-alence to a serial execution.

we only consider a singleset of invariants per database rather than per-operation invariants

we explic-itly require more information from the application in the form ofinvariants (Kung and Papadimitriou [38] suggest this is informationis required for general-purpose non-serializable yet safe execution.)

However, we are not aware of related work that dis-cusses when coordination is strictly required to enforce a given set ofinvariants

or safety (e.g., the CRDT OR-Set does not—by itself—enforce invariants, such as ensuring that no employee belongs totwo departments), and are therefore not sufficient to guarantee cor-rectness for all applications

This means that, inour payroll example, we can provide coordination-free support forconcurrent salary increments but not concurrent salary decrements

To avoid variants of these anomalies, many optimistic, coordination-free database designs have proposed the use of abstract data types(ADTs), providing merge functions for a variety of uses such ascounters, sets, and maps [19, 44, 50, 58] that ensure that all updatesare reflected in final database state.

However, the reliance on invariants also has drawbacks. I-confluence analysis only guards against violations of any providedinvariants. If invariants are incorrectly or incompletely specified, anI-confluent database system may violate application-level correct-ness.

If two indepen-dent decisions to commit can result in invalid converged state, thenreplicas must coordinate in order to ensure that only one of the deci-sions is to commit.

Theorem 1 establishes I-confluence as a necessary and sufficientcondition for invariant-preserving, coordination-free execution

A system is globally I-valid iff all replicas alwayscontain I-valid state

A system is convergent iff, for each pair of servers,in the absence of new writes to the servers and in the absence ofindefinite communication delays between the servers, the serverseventually contain the same versions for any item they both store

invariants, orpredicates over replica state: I : D →{true,f alse}

On a wide-area network, delay is lower-bounded bythe speed of light (worst-case on Earth, around 75ms, or about 13operations per second [9]). Under network partitions [13], as delaytends towards infinity, these penalties lead to unavailability [9, 28]

The classic answer to maintain-ing application-level invariants is to use serializable isolation: ex-ecute each user’s ordered sequence of operations, or transactions,such that the end result is equivalent to some sequential execu-tion [15, 30, 53].

Given knowledge of application transactions and correctness crite-ria (e.g., invariants), it is often possible to avoid this coordination(by executing some transactions without coordination, thus pro-viding availability, low latency, and excellent scalability) whilestill preserving those correctness criteria.3. Invariant confluence offers a necessary and sufficient conditionfor this correctness-preserving, coordination-free execution.

Serializable transactions preserve application correctness at thecost of always coordinating between conflicting reads and writes.

In this paper, we address the central question inherent in this trade-off: when is coordination strictly necessary to maintain application-level consistency? To do so, we enlist the aid of application pro-grammers to specify their correctness criteria in the form of invari-ants.