Concurrent proposals

[jivimberg]

I've noticed that in your implementation of a replicated state machine the instance number is only advanced upon resolution.
So presumably clients can only issue a new proposal once the current one has been resolved.
Is there a simple way of adding support for multiple concurrent proposals?

[cocagne]

That's actually a fairly nuanced question. When you're doing multi-paxos without a dedicated leader, any client can attempt to propose the next value in the chain. Because it's an asynchronous system, each client could simultaneously attempt to propose a different value but Paxos guarantees that only one of them will be chosen. So right there you have multiple concurrent proposals. If you're using a lease-based master server where only the master is allowed to propose new values, the master server could aggregate multiple client proposals into a single value it then commits to the chain, so that'd be another way to support multiple concurrent proposals. Yet another way would be to split your replicated state into multiple, distinct multi-paxos chains. If you were creating a simple key-value system, for example, each key/value pair could use a separate chain so concurrent modifications to different keys wouldn't conflict and you'd always have consensus on what the value of any given key is. Multi-paxos itself is inherently serial. Each link in the chain must contain exactly one value and, generally speaking, each link must be resolved before choosing the value for the next can begin. That latter bit isn't strictly true since you could potentially have multiple links being modified at once but it'd take special application-level support to handle it correctly. For example, a replicated database might send the instructions : (insert,foo,bar), (delete,foo,bar),(insert,foo,baz). Inserting those into a replicated chain in any order will work just fine from a multi-paxos perspective but the proper sequencing will be essential to correct operation at the application level. Tom

…

On Fri, Dec 1, 2017 at 9:51 AM, Juan Ignacio Vimberg < ***@***.***> wrote: I've noticed that in your implementation of a replicated state machine the instance number is only advanced upon resolution. So presumably clients can only issue a new proposal once the current one has been resolved. Is there a simple way of adding support for multiple concurrent proposals? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#8>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABrLfJ7EnPTKW8E-V467FPzvgev5bcxXks5s8CBogaJpZM4QyiBC> .

[jivimberg]

Hi Tom,
Thanks for your detailed answer!

I was indeed talking about using a lease-based master multi-paxos. The idea of using distinct chains had never occurred to me, so thanks for the insight.

I was actually trying to implement something similar to the replicated state machine described by Lamport at Paxos Made Simple. The system described in that paper allows for multiple concurrent proposals. It does requires some extra care when a new node is promoted to master, and could leave you with gaps in the log.
About the order of the operations I think it could be decided at the master, and it could provide order guarantees only for operations the client has seen the response of.