20746

some questions about paxos

Question:

i am confused by the value chose by proposer. use a example to explain. If now a proposer wants to lock a file, then it will send that l1 is the processer_number, and v1 is the value of "lock the file", and acceptors accept it. than the proposer wants to unlock the file, and sends (l2 > l1)that v2 is the value of "unlock the file", after that, acceptor return the last value and proposer picks it and send again.

in this example, v2 is lost? or what is the real process in this example? also, these are two rounds or one round? how to deal with the round?

Answer1:

Paxos is not an atomic register; once a value is chosen by Paxos, it CANNOT change.

First, notice your lock is a <strong>finite state machine</strong>:

on_lock .-----------. | | +------+---+ +--v-----+ | UNLOCKED | | LOCKED |<--- start +------^---+ +--+-----+ | | `-----------' on_unlock

Paxos could be used to decide a <em>sequence of transitions;</em> but each new transition must be decided in a new Paxos instance.

I suggest taking a look at some of the other paxos questions around StackOverflow:

<ul><li><a href="https://stackoverflow.com/questions/14435646/paxos-value-choice" rel="nofollow">paxos value choice</a></li> <li><a href="https://stackoverflow.com/questions/10791825/implementation-of-paxos-algorithm" rel="nofollow">implementation of Paxos algorithm</a></li> <li><a href="https://stackoverflow.com/questions/5850487/questions-about-paxos-implementation" rel="nofollow">Questions about Paxos implementation</a></li> </ul>

Answer2:

We need to describe a lock protocol that we can use Paoxs to run in order to understand when multiple values are available and to see the outcome of choosing a value.

The lock is a cell holding a lock token value in the format L={T,P}, where P is the process holding the lock and T is the time the process took the lock. To acquire the lock a client sends V={Lc,Ln} where Lc is what it thinks is the current lock token and Ln={T',P'} is the new lock token it wants to set. A special token Nil can be sent to unlock the lock. The new token is not set if the message does not state a correct Lc that matches the current token. This compare-and-swap (CAS) prevents a delayed unlock message from being mistakenly applied. It also works to timeout a lock when clients can steal it; if two processes send two racing messages {L1,L2} and {L1,L3} only one can succeed. A process learns if it's operation succeeded by inspecting the returned value which is the lock value L. A process can query the lock value by sending {Nil,Nil} which is a "do nothing" CAS that unlocks an open lock; but which returns who owns the lock if the lock is closed.

Writes must pass through the leader. If a node knows it is not the leader it should redirect the client to the leader. If node does not know who is leader it should throw an error and the client should pick another node at random. If the node thinks it is the leader it can only respond to the client when it is sure that a majority of nodes have accepted the new value. This is because Paxos ensures that a value accepted by a majority has been made durable by the cluster. If a node was leading, then does not hear a majority of acceptances, it cannot respond to the client. It may be isolated from the other nodes. The other nodes may have a newly elected leader. This also applies to {Nil,Nil} queries which need a majority of acceptances to confirm the leader is still the leader to tell the client the current lock value. Eventually the node should hear if a new leader exists else timeout trying to get the value accepted by a majority. It should then either redirect the client to the new leader else return an error to the client.

Now we can consider multiple values during leader failover. Client A sends a valid CAS update V1 which should succeed to the leader node X of a three node cluster. Node X sends accept(N1,V1) to itself and nodes Y and Z. It accepts its own value and also gets an acceptance from Y but the network drops the message to Z. Then node X goes dark and stops issuing any messages for a while. It may be dead or stalled but we don't yet know. It had seen a majority of X,Y but is now a mysterious Schrödinger's cat either dead or alive until we see another message from it to know its fate. This is where Paxos chooses to use collaboration to get a consistent and correct outcome no matter what happens next.

After a while node Z times out as it has not heard from a leader in too long. It issues propose(N2) to itself and the other nodes. It gets back promise(N2,V1) from node Y and promise(N2,empty) from itself. It has a majority Y,Z and can lead. Only node X knows that value V1 had been accepted by a majority and whether the client has been told it's CAS succeeded; but it is silent. Node Z has to make a conservative choice. If it were to assume X is dead it may be wrong: node X may be alive and may have told the client the operation succeeded. Node Z must collaborate and finish the partial work of the last leader by leading with V1 as its first value. So it sends accept(N2,V1) to all three nodes. Now it does not matter if node X is dead or alive or had told the client the operation succeeded or not. In all cases the locking protocol will not be violated and the client will find out it has the lock eventually if it retries upon error; it does not see nor care what proposal nor which node committed the work.

Recommend

  • jQuery - .Ready fires on div tag not in the page
  • ConcurrentHashMap read while resizing
  • Using mod_rewrite, how do I force the path and query string to be all lower case?
  • How to create a Plone 4 group who's sole purpose is to manage users?
  • What happens when you initialize a parameter? C++
  • linear combinations in python/numpy
  • stop image from moving when reaching the border of a container
  • Xpath how to get element by index AND attribute
  • What products support 3-digit region subtags, e.g., es-419 for Latin-American Spanish?
  • Delete ARP entry on Windows CE 6.0 CF.NET 2.0
  • How to restrict number of concurrent processes?
  • Comparing elements in two lists when keeping duplicates is desired in Python
  • Replace any string in columns with 1
  • d3js: time scaling and “1901”
  • Adding Client Certifcate to Service Fabric
  • f:param to composite components
  • IDX10503: Signature validation failed
  • oauth2client.client.HttpAccessTokenRefreshError: invalid_grant: Invalid JWT
  • Syntax error near unexpected token 'elif'
  • How to use tag-it
  • Telegram bot API - Inline bot getting Error 400 while trying to answer inline query
  • read values from form post in jquery or javascript
  • Passing “get” parameters doesn't work, parameter not visible in the link
  • Center align outputs in ipython notebook
  • Spring Cloud Microservice Architecture Confusion
  • Thread safety of a fluent like class using clone() and non final fields
  • custom UITableViewCell with image for highlighting
  • Transactional Create with Validation in ServiceStack Redis Client
  • Handling un-mapped Rest path
  • PHP - How to update data to MySQL when click a radio button
  • Sending data from AppleScript to FileMaker records
  • vba code to select only visible cells in specific column except heading
  • Convert array of 8 bytes to signed long in C++
  • Font Awesome Showing Box instead of Icons
  • Properly structure and highlight a GtkPopoverMenu using PyGObject
  • Understanding cpu registers
  • Is it possible to post an object from jquery to bottle.py?
  • Recursive/Hierarchical Query Using Postgres
  • Running Map reduces the dimensions of the matrices
  • Python/Django TangoWithDjango Models and Databases