Nil-externality

  • Does not return an execution result or execution error
    • validation error => OK

Nilext-aware Replication

  • Normal (Paxos)
    • Write: 2RTT
    • Read: Read from master (1 RTT)
  • Nilext-aware
    • Client send request to all replicas
      • receive replies from super majority and master

Other approaches

  • Network Ordering
    • Special underlying network
  • Speculative Execution
    • Execute and rollback
  • Exploiting Commutativity

SKYROS

  • Update
    • Send to all replicas
    • Wait for supermajority f+⌈f/2⌉+1 with leader included
    • Replica write to Durability log and return
  • Background Ordering and Execution
    • Batch durability log
    • Leader adds to consensus log
    • Leader sends prepare to f followers, followers add to consensus log
    • Leader applies update and removes from durability log
    • Leader sends commit to followers
    • Leader applies update and removes from durability log
  • Read
    • If in durability log
      • adds all request from the d-log, wait for f followers to respond
      • Serve the read
    • Else
      • directly return data
  • Non-nilext Updates
    • Client sends to leader only
    • Leader add all and this update to consensus log
    • Wait for f followers => return

Recovery

  • Replica Fail
    • Mark status as recovering
    • Send recovery, wait for f+1 replies including leader from latest view
    • copy d-log, c-log
  • Master Fail
    • C-Log
      • Find latest log with largest view #
    • D-Log