# Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS

## Contributions:

- causal+
- linearizable within cluster
  - replicated keys using `chain replication`
- causal across clusters
  - bolt-on-ish
- use of explicit dependencies (before bolt-on)
- get (read) transactions


![arch](copsArch.png)

## COPS

- individual accesses
- explicit tracking of dependences
  - *nearest*
  - contexts (threads, or explicit)
  - Lamport Clocks
     - version is CLOCK.nodeID
       - convergent, not necessarily eventual

![deps](copsDeps.png)

- "context" implemented incrementally as set of nearest neighbors
  - read: 
    - return value added to context
  - write: 
    - context added to write
    - context zero'd out
	- context set to new write
- propagated with writes to remote clusters
- write installed at new cluster by
  - `depCheck()`s to owner of each write in "nearest"
  - `depCheck()` blocks until true
  - `depCheck()` re-issued on time-out

## COPS-GT

*causal not always enough*

### Straightforward problems
Alice
```
s0: ACL == "world"
p0:"all is good"

s1: change ACL to exclude Boss
p2: "hate my job"
```
Assume reads implemented by ACL check followed by read

Boss:
- check security: see s0, which includes Boss
- read returns p2
- Alice is fired

*TOCTOU* vulnerability (time-of-check-to-time-of-use)

### Another implementation
Might consider re-implementing library to issue GETs in reverse order, checking "nearest" as you go
- works for above example (p2 depends on s1)

But if Alice adds a few more actions:
```
p3: delete last post
s2: add Boss back to ACL
```

...the reverse order doesn't help
- could return p2, s2  (both possibly latest version, causally consistent individually when issued)


### A causally-consistent set of reads
s0, p0:  "world" / "all is good"
s1, p0:  "no-boss" / "all is good"
s1, p2:  "no-boss" / "hate job"
s1, p3:  "no-boss" / "all is good"
s2, p3:  "world" / "all is good"


## GT implementation
- "all dependences"
  - really means one-per-key that have been locally modified
  - "nearest" still big win over this because there might be *many* keys
- individual writes not coordinated
- by keeping **all** dependences, not just nearest
- clearly need GC

![deps](copsGT.png)


## Notes
- Kaitlyn - just measured against themselves
- Elliot - ALPS
- Huayang - CAP, what does paxos give up?
- Nikhil - when not convergent?
