Coutesy of Robert Morris
------------

Recap
Sequential consistency: 
	* all read/write ops follow some total ordering
	* a read see the result of latest write (i.e. the write ordered before it)
	+ intuitive semantics
	- require lots of coordination among nodes (long latency operation)

	implementing sequential consistency:
	partition state space among servers
	[diagram] 

	S0    S1  (S0 serializes all ops w.r.t. object A, S1 serializes object B)

	C0    C1 (possibly w/ cache)

	Example coordination: synchronous replication, cache invalidation 

Many relaxed consistency models:
  Goal: better performance, less coordination
	Tradeoff: less intuitive semantics (more anomalies)

Today: Eventual consistency
	Same name has several meanings

For better performance, 
	* accept a write before being able to serialize it.
	* reads can return a (possibly) stale value than blocking for the latest value.

Anomalies!
  * write-write conflict
  * stale read
	* loss of causality

Desired properties:
	* Eventual convergence of state
	* Causality perserving 

Let's build a shared photo gallery
 gallery consists of many albums, each identified by an aid
 Each album (aid) contains an ordered list of photos each identified by a pid. 
 Operations: add album, add photo to album, delete photo etc.

Traditional approach: one server
  Server processes requests one at a time
  Server implicitly chooses order for concurrent requests

Why aren't we satisfied with central server?
 I want to operate on my gallery at the iPhone.
   I.e. storage replicated in every node.
   Modify on any node, as well as read.
 Periodic connectivity to net and other nodes.

Straw man 1: merge storage.
  What if there's a write-write conflict? Add two photos to the same album "at the same time"
   But we want automatic  conflict resolution.

Idea: update functions
  Have update be a function, not a new value.
	e.g. add pid to album w/ aid.
  Read current state of storage, decide best change.
  Function must be deterministic
    Otherwise nodes will get different answers

Challenge:
  A: add pid1 to album w/ aid
	B: add pid2 to album w/ aid
  X syncs w/ A, then B
  Y syncs w/ B, then A
  Will X show pid1 in front of pid2, and Y show pid2 in front of pid1?

Goal: eventual state convergence 

Idea: ordered update log
  Ordered list of updates at each node.
  Storage state is result of applying updates in order.
  Syncing == ensure both nodes have same updates in log.

How can nodes agree on update order?
  Update ID: <time T, node ID>
  Assigned by node that creates the update.
  Ordering updates a and b:
    a < b if a.T < b.T or (a.T = b.T and a.ID < b.ID)

Example:
 <10,A>: staff meeting at 10:00 or 11:00
 <20,B>: hiring meeting at 10:00 or 11:00
 What's the correct final outcome?
   the result of executing update functions in timestamp order
   staff at 10:00, hiring at 11:00

What's the status before any syncs?
  I.e. content of each node's storage state
  A: pid1 at 10th position for album aid
  B: pid2 at 10th position for album aid
  This is what A/B user will see before syncing.

Now A and B sync with each other
  Both now know the full set of updates
  Can each just run the new update function against its storage state?
    A: pid1 at 10th position, pid2 at 11th position
    B: pid2 at 10th position, pid1 at 10th position
  That's not the right answer!

Roll back and replay
  Re-run all update functions, starting from empty storage state
  Since A and B have same set of updates
    they will arrive at same final state
  We will optimize this in a bit

Displayed photo positions are "tentative"
  B's user saw a photo pid1 at 10th position, then it's changed to 11th position
  You never know if there's some other photo from nodes you haven't yet synced
    That will change the pid1's position yet again
  
Will update order be consistent with wall-clock time?
  Maybe A went first (in wall-clock time) with <10,A>
  Node clocks are not perfectly synchronized
  So B could then generates <9,B>
  B's meeting gets priority, even though A asked first

Will update order be consistent with causality?
  What if A adds a photo pid1, 
    then B sees it,
    then B deletes pid1
  Perhaps
    <10,A> add
    <9,B> delete -- B's clock is slow
  Now delete will be ordered before add!
    Unlikely to work
    Differs from wall-clock time case b/c system *knew* B had seen the add

Lamport logical clocks
  Want to timestamp events s.t.
    node observes E1, then generates E2, TS(E2) > TS(E1)
  Thus other nodes will order E1 and E2 the same way.
  Each node keeps a clock T
    increments T as real time passes, one second per second
    T = max(T, T'+1) if sees T' from another node
  Note properties:
    E1 then E2 on same node => TS(E1) < TS(E2)
    BUT
    TS(E1) < TS(E2) does not imply E1 came before E2

Logical clock solves add/delete causality example
  When B sees <10,A>,
    B will set its clock to 11, so
    B will generate <11,B> for its delete

Irritating that there could always be a long-delayed update with lower TS
  That can cause the results of my update to change
  Would be nice if updates were eventually "stable"
    => no changes in update order up to that point
    => results can never again change -- e.g. you know for sure pid1 is at position 10.
    => no need to re-run update function

How about a fully decentralized "commit" scheme?
  You want to know if update <10,A> is stable
  Have sync always send in log order -- "prefix property"
  If you have seen updates w/ TS > 10 from *every* node
    Then you'll never again see one < <10,A>
    So <10,A> is stable
  Why doesn't Bayou do something like this? (Bayou commits updates through designated primary replica)

How to sync?
  A sending to B
  Need a quick way for B to tell A what to send
  A has:
    <-,10,X>
    <-,20,Y>
    <-,30,X>
    <-,40,X>
  B has:
    <-,10,X>
    <-,20,Y>
    <-,30,X>
  At start of sync, B tells A "X 30, Y 20"
    Sync prefix property means B has all X updates before 30, all Y before 20
  A sends all X's updates after <-,30,X>, all Y's updates after <-,20,X>, &c
  This is a version vector -- it summarize log content
    It's the "F" vector in Figure 4
    A's F: [X:40,Y:20]
    B's F: [X:30,Y:20]

How did all this work out?
  Replicas, write any copy, and sync are good ideas
    Now used by both user apps *and* multi-site storage systems
  Requirement for p2p interaction is debatable
    iPhone apps seem to work fine by contacting server via cell-phone net
  Bayou introduced some very influential design ideas
    Update functions
    Ordered update log is the real truth, not the DB
    Allowed general purpose conflict resolution
  Bayou made good use of existing ideas
    Eventual consistency
    Logical clock


COPS [SOSP'11]

System setup:
	Multiple data centers, separated by long distance links
	Each data center has many nodes, storage state is fully replicated at each data center
Desired performance:
	Writes finish w/o waiting for remote sites (async. replication)
	Reads contact local site only

What's causal consistency?
	Systems that obey the following set of partial orders
	1. if op1 and op2 are in the single thread of execution and op1 is issued before op2, then op1 --> op2.
	   (On client1, op1: creates pid1, op2: adds pid1 to album aid. All nodes see the effect of op2 after op1) 2. If op2 reads the result written by op1, then op1--> op2
	   (On client1, op1: adds pid1 to album aid On client 2, op2: reads pid1 in album)
	3. if op1-->op2, op2-->op3, then op1-->op3
	   (On client 1, op1: adds pid1 to album aid On client 2, op2: reads pid1 in album, op3: deletes pid1. All nodes see op1--->op2--->op3, i.e. pid1 is deleted)

Does Bayou provide causal consistency? Is it scalable?

COPS' approach
  partition key-space among nodes
  explicitly keep track explicit dependencies (partial orders) for each write
	Site A performs a write, replicates it together with the dependencies to another site B
	Site B waits until the write's dependencies are satisfied in B before committing the write.


Client library
  put(key,value,context); //store current dependencies (in context) with write value
	value = get(key,context);  //add dependencies of get to context

					dependencies
	read x1; v0-->x1
	read w2; v0-->x1,w1-->w2
	write y1; v0-->x1,w1-->x2-->y1
	write z1; v0-->x1,w1-->x2-->y1-->z1

	Site A replicate z1 with dependency (v0,x1,w1,x2,y1) to site B.
	Site B performs a dependency check locally to wait for v0,x1,w1,x2,y1 to commit before committing z1.

	Optimize by exploiting transitivity, only the nearest dependencies is important
	read x1; ctx=x1
	read w2; ctx=x1,w2
	write y1; store (x1,w2) to value of y1, ctx=y1
	write z1; store (y1) to value of z1, ctx=z1


Anomalies under causal consistency 
  -- write-write conflict
	-- at site A: change ACL, add party photo, at site B: read old ACL, read party photo
  --