Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

WPaxos: a wide area network Paxos protocol

muratbuffalo.blogspot.com

Post reply on HN
Print view View original

11–20 of 20 posts

Re: WPaxos: a wide area network Paxos protocol

#11

Post by matthelb »

ccleve wrote: post #8

It looks like the core of the idea is "object stealing". In most consensus algorithms you'll have a single leader, worldwide, that is in charge of sequencing all objects. Either that, or you partition objects across leaders and then coordinate across partitions. In this algorithm you have multiple leaders, where a leader can be in charge of a particular object temporarily by "stealing" it. This brings control to the…

I also haven't read through the technical report in detail, but in skimming through parts of it, it looks like WPaxos is supposed to provide linearizability. More specifically, the authors state that:

> WPaxos maintains separate logs for every object and provides per-object linearizability.

Linearizability is a composable correctness condition, so per-object linearizability implies that the composition of all the objects is linearizable. Thus, WPaxos does in fact provide a single total ordering of all operations. Nearly all of the replicated state machines via consensus protocols (Paxos, EPaxos, Mencius, Generalized Paxos, etc.) provide this same consistency level.

Re: WPaxos: a wide area network Paxos protocol

#12

Post by wickawic »

matthelb wrote: post #11
ccleve wrote: post #8

It looks like the core of the idea is "object stealing". In most consensus algorithms you'll have a single leader, worldwide, that is in charge of sequencing all objects. Either that, or you partition objects across leaders and then coordinate across partitions. In this algorithm you have multiple leaders, where a leader can be in charge of a particular object temporarily by "stealing" it. This brings control to the…

I also haven't read through the technical report in detail, but in skimming through parts of it, it looks like WPaxos is supposed to provide linearizability. More specifically, the authors state that: > WPaxos maintains separate logs for every object and provides per-object linearizability. Linearizability is a composable correctness condition, so per-object linearizability implies that the composition of all the obj…

Time to let my ignorance shine:

> Linearizability is a composeable correctness condition

So if all I know is that A1 precedes A2 and that B1 precedes B2, how do I make assertions about the ordering of A2 and B2? Is “linear” in the context that you are talking about more specific than “orderable”?

GP isn’t complaining that the algorithm is incorrect, just that it doesn’t have the property of being replayed or reversed in a deterministic way. Most applications don’t need this property, I am just trying to see if I’m missing a part of your argument.

Re: WPaxos: a wide area network Paxos protocol

#13

Post by matthelb »

wickawic wrote: post #12
matthelb wrote: post #11

Earlier quoted context omitted.

I also haven't read through the technical report in detail, but in skimming through parts of it, it looks like WPaxos is supposed to provide linearizability. More specifically, the authors state that: > WPaxos maintains separate logs for every object and provides per-object linearizability. Linearizability is a composable correctness condition, so per-object linearizability implies that the composition of all the obj…

Time to let my ignorance shine: > Linearizability is a composeable correctness condition So if all I know is that A1 precedes A2 and that B1 precedes B2, how do I make assertions about the ordering of A2 and B2? Is “linear” in the context that you are talking about more specific than “orderable”? GP isn’t complaining that the algorithm is incorrect, just that it doesn’t have the property of being replayed or reversed…

Maurice Herlihy and Jeanette Wing introduced linearizability back in 1990 [1]. It stipulates that the result of a concurrent execution of the system is equivalent to a result from a sequential execution where the order of the sequential execution respects the real-time order of operations in the concurrent execution.

In this context, you could probably use "linear" and "orderable" to mean the same thing. The idea is that, for any linearizable execution, there exists an equivalent total order of the operations. Because there exists a total order, if a client C1 sees A2 before B2 then a client C2 cannot see B2 before A2.

[1] https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

Re: WPaxos: a wide area network Paxos protocol

#14

Post by pests »

matthelb wrote: post #13
wickawic wrote: post #12

Earlier quoted context omitted.

Time to let my ignorance shine: > Linearizability is a composeable correctness condition So if all I know is that A1 precedes A2 and that B1 precedes B2, how do I make assertions about the ordering of A2 and B2? Is “linear” in the context that you are talking about more specific than “orderable”? GP isn’t complaining that the algorithm is incorrect, just that it doesn’t have the property of being replayed or reversed…

Maurice Herlihy and Jeanette Wing introduced linearizability back in 1990 [1]. It stipulates that the result of a concurrent execution of the system is equivalent to a result from a sequential execution where the order of the sequential execution respects the real-time order of operations in the concurrent execution. In this context, you could probably use "linear" and "orderable" to mean the same thing. The idea is…

You still haven't answered the question though.

The definition of linearizability is not in question.

The question is does this specific system we are discussing have global-linearizability or is there separate per-object (or some other bucketing method) linearizability.

Re: WPaxos: a wide area network Paxos protocol

#15

Post by matthelb »

pests wrote: post #14
matthelb wrote: post #13

Earlier quoted context omitted.

Maurice Herlihy and Jeanette Wing introduced linearizability back in 1990 [1]. It stipulates that the result of a concurrent execution of the system is equivalent to a result from a sequential execution where the order of the sequential execution respects the real-time order of operations in the concurrent execution. In this context, you could probably use "linear" and "orderable" to mean the same thing. The idea is…

You still haven't answered the question though. The definition of linearizability is not in question. The question is does this specific system we are discussing have global-linearizability or is there separate per-object (or some other bucketing method) linearizability.

Sorry, I was trying to give the GP more context for my initial comment.

As I said in my initial comment, the authors state that WPaxos provides per-object linearizability, which implies that it provides (to use your term, "global"-)linearizability.

Re: WPaxos: a wide area network Paxos protocol

#16

Post by grogers »

ccleve wrote: post #8

It looks like the core of the idea is "object stealing". In most consensus algorithms you'll have a single leader, worldwide, that is in charge of sequencing all objects. Either that, or you partition objects across leaders and then coordinate across partitions. In this algorithm you have multiple leaders, where a leader can be in charge of a particular object temporarily by "stealing" it. This brings control to the…

I agree to an extent, spanner showed that point in time global snapshots can be practical. But many (most?) applications are fine with just serializable transactions, they don't need the additional real-time preserving guarantee of strict serializability. So I expect to see more of this in the future where constraints are relaxed just slightly.

Re: WPaxos: a wide area network Paxos protocol

#17

Post by itcmcgrath »

matthelb wrote: post #15
pests wrote: post #14

Earlier quoted context omitted.

You still haven't answered the question though. The definition of linearizability is not in question. The question is does this specific system we are discussing have global-linearizability or is there separate per-object (or some other bucketing method) linearizability.

Sorry, I was trying to give the GP more context for my initial comment. As I said in my initial comment, the authors state that WPaxos provides per-object linearizability, which implies that it provides (to use your term, "global"-)linearizability.

It doesn't, the authors are calling this out to limit the scope of linearizability to per-object. You're thinking about strict serializability.

The authors mention that transactions can be implemented in a way to support this by including a first step to steal all objects needed by the transaction. I believe this would give you strict serializability at a global level, but does have trade-offs in needing to know all objects at the start of a transaction, and other implications on latency, etc from this step.

The authors also note they haven't implemented transactions yet.

Also worth noting that some of the extensions/optimizations, such as the mentioned 'locality adaptive object stealing optimization' won't work as described with multi-object transactions. I could see additional work to identify groups of objects, but this would be very workload specific and not suitable as a generic solution.

Re: WPaxos: a wide area network Paxos protocol

#18

Post by matthelb »

itcmcgrath wrote: post #17
matthelb wrote: post #15

Earlier quoted context omitted.

Sorry, I was trying to give the GP more context for my initial comment. As I said in my initial comment, the authors state that WPaxos provides per-object linearizability, which implies that it provides (to use your term, "global"-)linearizability.

It doesn't, the authors are calling this out to limit the scope of linearizability to per-object. You're thinking about strict serializability. The authors mention that transactions can be implemented in a way to support this by including a first step to steal all objects needed by the transaction. I believe this would give you strict serializability at a global level, but does have trade-offs in needing to know all…

I'm not thinking of strict serializability - I do actually mean linearizability.

My previous comments were referring to the basic algorithm presented as the main contribution of this paper in section 3. In this algorithm, "Every command accesses only one object o." With each operation applying to a single object and each object satisfying linearizability, the system as a whole will be linearizable.

The distinction between linearizability and strict serializability is somewhat subtle. I highly recommend this blog post [1] by Irene Zhang and this blog post [2] by Peter Bailis for some really great discussion on the subtleties involved.

[1] https://irenezhang.net/blog/2015/02/01/consistency.html

[2] http://www.bailis.org/blog/linearizability-versus-serializab...

Re: WPaxos: a wide area network Paxos protocol

#19

Post by ccleve »

matthelb wrote: post #18
itcmcgrath wrote: post #17

Earlier quoted context omitted.

It doesn't, the authors are calling this out to limit the scope of linearizability to per-object. You're thinking about strict serializability. The authors mention that transactions can be implemented in a way to support this by including a first step to steal all objects needed by the transaction. I believe this would give you strict serializability at a global level, but does have trade-offs in needing to know all…

I'm not thinking of strict serializability - I do actually mean linearizability. My previous comments were referring to the basic algorithm presented as the main contribution of this paper in section 3. In this algorithm, "Every command accesses only one object o." With each operation applying to a single object and each object satisfying linearizability, the system as a whole will be linearizable. The distinction be…

Perhaps we should step away from the terms "linearizability" and "serializability" and speak of global total ordering. That's what some other systems provide and this one doesn't. It's a valuable feature because it makes it possible to know the state of the system as of a snapshot in time.

Re: WPaxos: a wide area network Paxos protocol

#20

Post by matthelb »

ccleve wrote: post #19
matthelb wrote: post #18

Earlier quoted context omitted.

I'm not thinking of strict serializability - I do actually mean linearizability. My previous comments were referring to the basic algorithm presented as the main contribution of this paper in section 3. In this algorithm, "Every command accesses only one object o." With each operation applying to a single object and each object satisfying linearizability, the system as a whole will be linearizable. The distinction be…

Perhaps we should step away from the terms "linearizability" and "serializability" and speak of global total ordering. That's what some other systems provide and this one doesn't. It's a valuable feature because it makes it possible to know the state of the system as of a snapshot in time.

This is exactly what I was addressing in your initial comment! This system provides a global total ordering of operations. It's the whole point of a replicated state machine.

The ensuing conversation explored how/why the system provides a global total ordering.

Post reply on HN