• Weakly consistent
  • May return conflicting data
    • (Will let clients know)
  • Supporting application-specific conflict detection and resolution

Example App

  • Meeting room scheduler
  • Users select several acceptable meeting times
  • Reservation may be “tentative”

System Model

  • Client write to any server
    • Server assign WriteID
  • Servers propagate writes during pair-wise contact
    • aka anti-entropy sessions

Dependency Check

  • Bayou_Write (update, dependency_check, mergeproc)
  • Write consist application-supplied query and expected result
    • unexpected result => conflict => apply merge procedures

Replica Consistency

  • Writes are performed in the same order at all servers
  • Conflict detection and merge procedures are deterministic
  • Servers need to know how to roll back tentative execution

Write Stability

  • Primary commit
  • Which server to choose as primary?
    • example
      • choose personal laptop as primary server for calendar
      • secretary keep secondary replica

Server Structure

  • Write log
    • Ordered Set
    • head ||commited||tenative|| tail
  • O vector
    • Timestamp of the last write from every other server that has been discarded
    • (reject old writes to prevent same writes)
  • Tuple store (where the real data is stored)
    • entry: |data|committed-bit|full-bit|

    When a Write is tentative, its effect appears in the full view but not in the committed view.

  • C, F vector
  • Undo log