Paxos consistency

Question

I'm looking at the paxos family of protocols for solving consensus in a network of unreliable processors. I'm working through scenarios where processors fail, and I know I'm wrong, but I don't know why.

I have 3 machines with the state A.

1. One machine goes down.
2. The client requests a state change. Paxos works, and machines 2 and 3 have the state B.
3. The client requests a state change, prepare and promise phases are completed successfully.
4. A second machine goes down
5. The proposer sends an Accept Request message
6. The machine accepts the new value

At the end each machine has a different value: A, B and C.

I thought that Paxos can never left the system in a inconsistent state, I think that my problem is that I don't understand what Paxos safety properties really are.

Answer 1

In your example no client gets a confirmation that the value was written hence the system is in undefined state, but it is consistent with its history. To read a value a client should initiate a new round of Paxos. The main result of the "Paxos made simple" is that if a value was reported as chosen then any further rounds of Paxos will propose the same value.