# PAXOS

*Agree on a single result in network of unreliable processes.*

### Assumptions:
- non-byzantine (fail-stop) faults
- processors have arbitrary speed
- processors w/ stable storage may rejoin after failure

### Safety requirements:
- only a value that has been proposed may be chosen (non-triviality)
- only a single value chosen (consistency)
- process never learns a value is chosen unless it has been (correctness)
- *impossible*, at least for asynchronous systems (fischer '85)

### Roles
- clients
- proposers
- acceptors
- learners

### Invariants:
1. P1: Accept first proposal received
  - works even if only one
1. P2: If proposal w/ value v is chosen, *all higher-numbered chosen proposals choose v*

## Procedure:
1. Proposer issues PREPARE w/ proposal n and sends to requesters, returns:
   - **PROMISE never again to accept a proposal < n**, with
     - **highest number <n** it has accepted
     - Value **v** it has accepted previously
2. ACCEPT request w/ n, and value (possibly from prior proposal)
   - acceptor can accept a a proposal n iff it has not PROMISEd w/ num > n
   - response is ACCEPTED
   - Majority of ACCEPTED is the winner.  Safety proporties satisfied

Opt:
- don't respond to PREPARE w/ num less than one already seein in a PREPARE (cause won't accept it anyway)

Progress:
- not guaranteed because p and q can duel w/ ever-increasing n

### Paxos

```
  Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{null,null,null})
   |         |          |  |  |       |  |
   |         X--------->|->|->|       |  |  Accept!(1,V)
   |         |<---------X--X--X------>|->|  Accepted(1,V)
   |         |          |  |  |       |  |
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |
```
### Dueling Proposers
```
Client   Leader         Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|  |       |  |  Prepare(1)
   |      |<------------X--X  |       |  |  Promise(1})
   |                                  |  |
   |         X--------->|  |->|       |  |  Prepare(2)
   |         |<---------X  |--X       |  |  Promise(2)
   |                                  |  |
   |      X------------>|->|  |       |  |  Accept(1,  V1)
   |      |<------------X--X  |       |  |  NACK
   |      X------------>|->|  |       |  |  Prepare(3)
   |      |<------------X--X  |       |  |  Promise(3, {null, null, null})
   |                                  |  |
   |         X--------->|  |->|       |  |  Accept(2)
   |         |<---------X  |--X       |  |  NACK
   |         X--------->|  |->|       |  |  Prepare(4)
   |         |<---------X  |--X       |  |  Promise(4)
   |                                  |  |
   |      |  |          |  |  |       |  |  ... and so on ...
```

### Multi-Paxos (collapsed roles)
```
Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N, I, {Va, Vb})
   |         |  |  |
   |         X->|->|  Accept!(N, I, V)
   |         |<-X--X  Accepted(N, I)
   |<--------X  |  |  Response
   |         X  |  |
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N, I+1, W)
   |         |<-X--X  Accepted(N, I+1)
   |<--------X  |  |  Response
   |         |  |  |
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N, I+2, Z)
   |         |<-X--X  Accepted(N, I+2)
   |<--------X  |  |  Response
```

### 

---------------------------------------------------------------------



# Chubby

- explicitly talk about replicated log as base of dist systems


## Optimizations:
- multipaxos
- batching mult values in single instance
- master leases
- snapshots: log is record of steps to achieve a state
  - that state can be used to substitue for the log

## Multi-op
- guard: list of tests of various slots
- t_op: DB operations to execute if guard TRUE
- f_op: DB operations to execute if guard FALSE

---------------------------------------------------------------------


