# Keeping Calm

Coordination (consistency) is:
1. *slow*:
1. *tricky*: true, but not worst part

1) means that high levels of consistency rarely implemented, and
2) means that such implementations are incorrect

Coordination not always necessary:
- analogy of building overpass instead of stoplight.

deadlock detection: <img width=450 src=calm1.png>

- Not all deadlocks can be detected w/ local information
  - but any detected are *stable*.
- New information might reveal more deadlocks, but not invalidate ones
  already seen
  - No race conditions, or need for synchronization between machines.
------

garbage collection: <img width=450 src=calm2.png>

Can only toss based on *complete* information!
- incomplete info might imply object is orphaned
  - we toss
  - new information reveals a remote ptr to object
  - game over

## Monotonicity

Needs for coordination due to:
- engineering decisions (someone said no to overpass)
- *intrinsic* needs: GC relies on complete global information.

**Question**: *What is the family of problems that can be consistently
computed in a distributed fashion without coordination, and what
problems lie outside that family?*


Clues:
- deadlock detection depends on existance of a cyclic path
  - implies any detected cycles are valid deadlocks
  - though might be incomplete
- orphan detection depends on *non-existence* of a path.
  - implies complete information needed

The set of satisfying paths that exist is *monotonic* in information
received:

**Definition 1.** *A program P* is monotonic *if for any input sets
S,T where S ⊆ T , P(S) ⊆ P(T ).*

The set of paths that do *not* exist is non-monotonic.

**Theorem 1.** Consistency As Logical Monotonicity (CALM). *A
program has a consistent, coordination-free distributed implementation
if and only if it is monotonic.*

```
[The original] expression of CAP served its purpose, which was to open the minds of designers
to a wider range of systems and tradeoffs ...

The modern CAP goal should be to maximize combinations of consistency and availability that make
sense for the specific application. [14]
```

**Observation 1.** *Coordination-freeness is equivalent to availability under partition.*
- A coordination-free program is, by definition, available despite partitions.
- A program with coordination will stall when that coordination interrupted by partition.

(1) First, CAP is a **negative result over the space of all programs**:
CALM confirms this coarse result, but delineates at a finer
grain the negative and positive cases. *Monotone programs
can in fact satisfy all three of the CAP properties at once*;
non-monotone programs are the ones that cannot.

(2) The key insight in CALM is to focus on consistency from
the viewpoint of program outcomes rather than the traditional histories of storage mutation. The emphasis on the
program being computed shifts focus from implementation
to specification: it allows us to ask questions about what
computations are possible.   *hmm*


## Distributed Design Patterns

- assignment is nonmonotonic
  - later assignments might conflict w/ earlier decisions

*Immutable variables are monotonic.*

**CRDTs**:
- internal state a lattice that evolves monotonically according to
  partial order.
- two divergent replica can always be merged, even if they observe
  updates in different orders.

Examples:
- incrementing integers,
- confluent shopping carts
  - different browsers may add or subtract items, still converge
  - essentially a CRDT for *adds*, another for *deletess*, but neither commute with checkout
  



## Strategies

- use monotonic implementations
- keep coordination off critical path (wait until checkout to converge
  shopping cart)
- domain-aware *compensation for inconsistency* rather than prevent it
  - code checks for out-of-stock at checkout, gives a loyalty coupon


## Comments
- claude: no <a href="https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/">CAP proof</a> (Nancy Lynch), theorems are for proved assertions?  
- aaron: mention the relational algebra, which is indeed underlying relational databases

