4 ms·

I have always been puzzled as to why Brian Oki & Barbara Liskov's earlier (1988) "Viewstamped Replication" has been shadowed by Lamport's work. Isn't the RAFT t

I have always been puzzled as to why Brian Oki & Barbara Liskov's earlier (1988) "Viewstamped Replication" has been shadowed by Lamport's work. Isn't the RAFT that rocked Paxos's boat not a variant of their work? I would appreciate knowledgeable insights about this.

heavenlyblue 7y ago
Lamport’s work is much more general in nature. I have to admit it’s harder to follow for the same reason.
silasdavis 7y ago
I also don't understand this
bt848 7y ago
I don't know if raft "rocked" paxos's boat or not. It's a social phenomenon where Stanford people and their associates evangelize raft not because it is superior but just because it came from Stanford. People think raft is easier to implement but from my studies of available implementations the truth is it's actually just more likely that someone will Dunning-Krueger their way into believing they can implement it. There are a large number of defective raft implementations in the wild. There are almost no paxos implementations, correct or otherwise, making it harder to reason about its popularity and ergonomics. One thing is for sure: if you think you do not quite understand paxos then it is quite likely that you also do not understand raft, even though raft makes you feel like you might.
- kerkeslager 7y ago
  Raft also has a frequently-linked, simple visual explanation[1]. If that's at all accurate to what Raft is, that would certainly make Raft easier to understand than Paxos, although that's a function of the learning materials available, not anything inherently more understandable about the algorithm itself. I feel that I understand Raft and not Paxos, although currently that's simply because I haven't yet tried to understand Paxos. But the reason I am still interested in Paxos is that looking at Raft, it still seems like Raft has a bottleneck at the leader. Essentially, it looks like what makes this distributed consensus look simple is that only leader elections are actually distributed: the rest of the algorithm isn't distributed at all. When I get around to reading about Paxos I'm hoping it will be different. [1] https://raft.github.io/ https://raft.github.io/
  - dunkelheit 7y ago
    I find that the core of Paxos (the Synod protocol) is very easy to understand - it is literally just two exchanges of messages! The tricks that you need to add to go from the Synod protocol and get an actual production implementation of the replicated log are another matter, the original paper only hints about some of them. There is e.g. the Paxos Made Live paper (link: https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/paper2-1.pdf https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/paper...) that has more on this topic. BTW Paxos also has a leader - this is what makes these protocols efficient. They need only the linear number of messages instead of the quadratic "everybody talks to everybody" design.
    - vyodaiken 7y ago
      >BTW Paxos also has a leader - this is what makes these protocols efficient. That's the funny part of Paxos. Paxos is specifically sold as a multi-proposer protocol. The most subtle and hard to understand part of the protocol is the clever 2 phase proposal election with value inheritance. But it's all pointless because in order to make the system work you need a single coordinator you elect using timeouts or reliable message protocols.
    - kerkeslager 7y ago
      > BTW Paxos also has a leader - this is what makes these protocols efficient. They need only the linear number of messages instead of the quadratic "everybody talks to everybody" design. Okay, but again, this means that the leader is the bottleneck. In that case, I'd want the leader to be on beefier hardware than the other machines, and to not serve up any read requests, so all of its resources are devoted to leading. In order to accommodate this, you'd want to elect leaders from a pool of leaders which have the beefier hardware. And at that point, since you're only talking to the leaders when you write, rather than talk through to the leaders through the extra latency of the followers, just write to the leaders directly. And then at that point this looks suspiciously like the leaders are a sharded database and the followers are caches. Am I missing something?
  - chapium 7y ago
    Word on the street is if you really really try to understand Paxos you will find that its much more nuanced and complex than raft. Many have tried, but failed.
- achamayou 7y ago
  The Raft paper has a full section on understandability, and comes with a TLA+ spec. I am baffled that a serious effort at producing papers that are understandable and implementable is dismissed as a “social phenomenon”. Deliberately obscure papers are bad, sloppy science, not a clever signaling mechanism. As pointed out elsewhere in the conversation and indeed in revised editions of the Paxos paper, it does not even break new ground and is equivalent to the earlier view management protocol.
- vyodaiken 7y ago
  >There are almost no paxos implementations, correct or otherwise, making it harder to reason about its popularity and ergonomics. If I was cynical, I might guess that the purpose of Paxos these days is to generate expenses and technical failures for Google's competitors.
dgacmu 7y ago
Viewstamped replication came first, and defined the same core replication mechanism as paxos. but it was presented in the context of a replicated database system, together with a bunch of other stuff. Lampport's analysis of the core algorithm caught people's eyes -- with some amount of marketing on his part, and possibly because it was much more clearly focused on just the consensus problem, which made it somewhat more friendly as a theoretical building block. The title of his talk not withstanding, lampport's turing award was not for Paxos: https://amturing.acm.org/award_winners/lamport_1205376.cfm https://amturing.acm.org/award_winners/lamport_1205376.cfm rather, he pioneered many of the fundamental techniques that underlie both viewstamped replication and Paxos (and a boatload of other things; it was a very well-deserved award!) But Barbara invented the actual consistent replication algorithm first. and yes, raft is in many ways a restatement of viewstamped replication. The thing that makes both of them a better pedagogical basis is that they present the common case of having a working master direct replication, and then handle the failure case explicitly. It ends up being exactly the same thing that multi paxos does, but for most people, it ends up being a much more intuitive way of thinking about the system and algorithm. Or, at least that's been my experience in teaching it for 15 years.
- eternalban 7y ago
  Thank you. That was informative. > But Barbara invented the actual consistent replication algorithm Do you know anything about Brian Oki's subsequent career? I was curious as to what he did after his VSR thesis and found a '93 paper of his (The Information Bus [1]). Interesting to see again he was a bit ahead of his time, this time anticipating 'Eventual Consistency'. [1]: http://www.cs.utah.edu/~retrac/cs7460/infobus.pdf http://www.cs.utah.edu/~retrac/cs7460/infobus.pdf
vyodaiken 7y ago
I think the answer is that in the late 80s/90s, academic CS decided that the important topics in this area centered on completely asynchronous networks. The super famous, but trivial, FLP "theorem" gave a respectable foundation for work in the area (even though it pretty much says, you can't get anywhere with a completely asynchronous network). There was a lot of very interesting work prior to this period that was just discarded. For example Liskov's paper on using timeouts https://www.yodaiken.com/2018/07/16/practical-uses-of-synchronized-clocks-liskov/ https://www.yodaiken.com/2018/07/16/practical-uses-of-synchr... Viewstamps depends, implicitly, on timeouts. You send a message a number of times and if you don't get a response, you abort. In the completely asynchronous world, there is no way to do that.

heavenlyblue 7y ago

Lamport’s work is much more general in nature. I have to admit it’s harder to follow for the same reason.

silasdavis 7y ago

I also don't understand this

bt848 7y ago

I don't know if raft "rocked" paxos's boat or not. It's a social phenomenon where Stanford people and their associates evangelize raft not because it is superior but just because it came from Stanford. People think raft is easier to implement but from my studies of available implementations the truth is it's actually just more likely that someone will Dunning-Krueger their way into believing they can implement it. There are a large number of defective raft implementations in the wild. There are almost no paxos implementations, correct or otherwise, making it harder to reason about its popularity and ergonomics. One thing is for sure: if you think you do not quite understand paxos then it is quite likely that you also do not understand raft, even though raft makes you feel like you might.

kerkeslager 7y ago
Raft also has a frequently-linked, simple visual explanation[1]. If that's at all accurate to what Raft is, that would certainly make Raft easier to understand than Paxos, although that's a function of the learning materials available, not anything inherently more understandable about the algorithm itself. I feel that I understand Raft and not Paxos, although currently that's simply because I haven't yet tried to understand Paxos. But the reason I am still interested in Paxos is that looking at Raft, it still seems like Raft has a bottleneck at the leader. Essentially, it looks like what makes this distributed consensus look simple is that only leader elections are actually distributed: the rest of the algorithm isn't distributed at all. When I get around to reading about Paxos I'm hoping it will be different. [1] https://raft.github.io/ https://raft.github.io/
- dunkelheit 7y ago
  I find that the core of Paxos (the Synod protocol) is very easy to understand - it is literally just two exchanges of messages! The tricks that you need to add to go from the Synod protocol and get an actual production implementation of the replicated log are another matter, the original paper only hints about some of them. There is e.g. the Paxos Made Live paper (link: https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/paper2-1.pdf https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/paper...) that has more on this topic. BTW Paxos also has a leader - this is what makes these protocols efficient. They need only the linear number of messages instead of the quadratic "everybody talks to everybody" design.
  - vyodaiken 7y ago
    >BTW Paxos also has a leader - this is what makes these protocols efficient. That's the funny part of Paxos. Paxos is specifically sold as a multi-proposer protocol. The most subtle and hard to understand part of the protocol is the clever 2 phase proposal election with value inheritance. But it's all pointless because in order to make the system work you need a single coordinator you elect using timeouts or reliable message protocols.
  - kerkeslager 7y ago
    > BTW Paxos also has a leader - this is what makes these protocols efficient. They need only the linear number of messages instead of the quadratic "everybody talks to everybody" design. Okay, but again, this means that the leader is the bottleneck. In that case, I'd want the leader to be on beefier hardware than the other machines, and to not serve up any read requests, so all of its resources are devoted to leading. In order to accommodate this, you'd want to elect leaders from a pool of leaders which have the beefier hardware. And at that point, since you're only talking to the leaders when you write, rather than talk through to the leaders through the extra latency of the followers, just write to the leaders directly. And then at that point this looks suspiciously like the leaders are a sharded database and the followers are caches. Am I missing something?
- chapium 7y ago
  Word on the street is if you really really try to understand Paxos you will find that its much more nuanced and complex than raft. Many have tried, but failed.
achamayou 7y ago
The Raft paper has a full section on understandability, and comes with a TLA+ spec. I am baffled that a serious effort at producing papers that are understandable and implementable is dismissed as a “social phenomenon”. Deliberately obscure papers are bad, sloppy science, not a clever signaling mechanism. As pointed out elsewhere in the conversation and indeed in revised editions of the Paxos paper, it does not even break new ground and is equivalent to the earlier view management protocol.
vyodaiken 7y ago
>There are almost no paxos implementations, correct or otherwise, making it harder to reason about its popularity and ergonomics. If I was cynical, I might guess that the purpose of Paxos these days is to generate expenses and technical failures for Google's competitors.

dgacmu 7y ago

Viewstamped replication came first, and defined the same core replication mechanism as paxos. but it was presented in the context of a replicated database system, together with a bunch of other stuff. Lampport's analysis of the core algorithm caught people's eyes -- with some amount of marketing on his part, and possibly because it was much more clearly focused on just the consensus problem, which made it somewhat more friendly as a theoretical building block. The title of his talk not withstanding, lampport's turing award was not for Paxos: https://amturing.acm.org/award_winners/lamport_1205376.cfm https://amturing.acm.org/award_winners/lamport_1205376.cfm rather, he pioneered many of the fundamental techniques that underlie both viewstamped replication and Paxos (and a boatload of other things; it was a very well-deserved award!) But Barbara invented the actual consistent replication algorithm first. and yes, raft is in many ways a restatement of viewstamped replication. The thing that makes both of them a better pedagogical basis is that they present the common case of having a working master direct replication, and then handle the failure case explicitly. It ends up being exactly the same thing that multi paxos does, but for most people, it ends up being a much more intuitive way of thinking about the system and algorithm. Or, at least that's been my experience in teaching it for 15 years.

eternalban 7y ago
Thank you. That was informative. > But Barbara invented the actual consistent replication algorithm Do you know anything about Brian Oki's subsequent career? I was curious as to what he did after his VSR thesis and found a '93 paper of his (The Information Bus [1]). Interesting to see again he was a bit ahead of his time, this time anticipating 'Eventual Consistency'. [1]: http://www.cs.utah.edu/~retrac/cs7460/infobus.pdf http://www.cs.utah.edu/~retrac/cs7460/infobus.pdf

vyodaiken 7y ago

I think the answer is that in the late 80s/90s, academic CS decided that the important topics in this area centered on completely asynchronous networks. The super famous, but trivial, FLP "theorem" gave a respectable foundation for work in the area (even though it pretty much says, you can't get anywhere with a completely asynchronous network). There was a lot of very interesting work prior to this period that was just discarded. For example Liskov's paper on using timeouts https://www.yodaiken.com/2018/07/16/practical-uses-of-synchronized-clocks-liskov/ https://www.yodaiken.com/2018/07/16/practical-uses-of-synchr... Viewstamps depends, implicitly, on timeouts. You send a message a number of times and if you don't get a response, you abort. In the completely asynchronous world, there is no way to do that.