Clarifications regarding Paxos and the paper Paxos Made Simple

Question

I read the paper named "Paxos made simple" but still got some confusions:

1. What does the "instances of paxos algorithm" refers to? does each instance indicate there is an input/command from external clients? and the paxos algorithm for each instance would be executed in parallel???

2. If there is only one "distinguished" proposer who is able to issue proposal, then what is the difference of paxos algorithm from 2-phase commit algorithm???

3. Where could we apply paxos algorithm in a real-world project?

It seems that the paper here gave more clear description: http://research.microsoft.com/pubs/64634/web-dsn-submission.pdf

Any more idea?

Answer 1

What does the "instances of paxos algorithm" refers to? does each instance indicate there is an input/command from external clients? and the paxos algorithm for each instance would be executed in parallel???

I answered the "instance" question in another question, so I will just summarize here.

Basically, it's like saying "an instance of a quicksort" to refer to one run of the algorithm. In the case of Paxos, instead of sorting a list, its choosing a value across multiple hosts. Multiple instances of paxos can/are be running in parallel. The participants have to be aware of this, so it is good it is mentioned explicitly.

If there is only one "distinguished" proposer who is able to issue proposal, then what is the difference of paxos algorithm from 2-phase commit algorithm???

The Distinguished Proposer is an optimization and is not a requirement for the algorithm. The Distinguished Proposer reduces the contention of two proposers leap-frogging prepare/accept messages, which is important if you want the instance to finish. In this model, a node forwards the request to the Distinguished Proposer instead of proposing for itself. If it thinks the Distinguished Proposer is dead then it just proposes for itself. (It does not have to be/it can never be 100% confident the Distinguished Proposer is dead).

Where could we apply paxos algorithm in real world/project?

First and foremost I use Paxos for leader election. For example, if I have several nodes that can do a task be a database Master, I use Paxos to a paxos instance to choose the master.

A secondary use case is as a strongly consistent database. The problem with this is it can be slow due to the number of messages required in a Paxos, so I don't use it for things that are better served by a different database. That is, I use it mostly for configuration. Take for example the database master leader election mentioned above. I store the result so nodes can query things like "who is the current database master?" Paxos also publishes its results, so in normal mode I just listen to this stream instead of actually querying.