News for hackers. Stuff that matters.
Re:The space between theory and practice in distributed systems by chubot on Sunday August 10, 2014 @01:34PM (#8160198)
If FLP says consensus is impossible with one faulty process, and faults happen all the time in practice, how are real systems built with consensus?

Good question. I think the answer is that you don't build large systems using consensus; you bootstrap large systems with very small systems using consensus. The very small systems are reasonably assumed to have no Byzantine faults (i.e. just like you more or less rely on a single database server not to have faults).

All the systems I know of that use consensus are meant to be small, e.g. run on 5 machines or so (and of course the membership is fixed). Google's Chubby, Yahoo's ZooKeeper, and similar systems like doozer and etcd all work like this.

Consensus doesn't "scale" anyway (the latency isn't bearable). If you only have 5 machines, the likelihood of Byzantine faults over a reasonably long time period is low. The main problem you will see is your own software bugs (i.e. not bugs due to faulty CPU, memory, disks, switches, etc.).

Re:The space between theory and practice in distributed systems by dgacmu on Sunday August 10, 2014 @04:22PM (#8160616)
Apparently Marc is right about the need for more of this - the answer is that the kind of nasty timing of message losses that can render consensus impossible don't happen, by and large, for very long in practice. It's not necessary to have Byzantine failures to prevent consensus, it's a consequence of the arbitrary network behavior allowed in an asynchronous communications model.

I should add this question to one of my exams and see if my students get it right. I'll be a little grumpy if they don't, but it's a great question. :)

Re:The space between theory and practice in distributed systems by chubot on Sunday August 10, 2014 @07:14PM (#8161117)
What's an example of "timing of message losses" that would make consensus impossible? I didn't think say Paxos depended on any such assumptions.

I suppose you can mathematically construct some kind of non-total message loss such that Paxos would never make progress. But that kind of message loss won't persist forever in a real system... it would basically be message loss with knowledge of the algorithm?

Re:The space between theory and practice in distributed systems by grogers on Sunday August 10, 2014 @08:05PM (#8161264)
Racing proposers cause paxos to fail to converge.

A: Prepare(1)

B: Prepare(2)

A: Accept(1, Va) # fails.

A: Prepare(3)

B: Accept(2, Vb) # fails.

Etc... In practice randomized backoffs when this happens causes it to converge extremely fast, but the exact right situation COULD cause it to delay forever. Don't lose sleep over it though.

Re:The space between theory and practice in distributed systems by chubot on Sunday August 10, 2014 @08:44PM (#8161352)
Yeah that is basically what I was imagining, but there's no failure condition that matches that in reality. You might get unlucky and fail to converge for 10 iterations, but not for say 10,000.

It is sort of Byzantine in that the "system" is inserting very specific message losses with knowledge of the algorithm.