Re:Proof of linearizability in Raft using Coq
by r0naa on Thursday August 06, 2015 @02:30PM
(#10018405)
Apologies to your research partner for leaving him out, it's edited! Congratulations on the proof by the way, I am looking forward to this week-end so I can have some time to appreciate it with more depth! :-)
[ Parent
| on HN ]
Re:Proof of linearizability in Raft using Coq
by dougws on Thursday August 06, 2015 @02:42PM
(#10018478)
Thanks! Let us know if you have any questions about the proof itself--unfortunately, it's not particularly well-documented, and Coq isn't super easy to read in the first place.
Re:Proof of linearizability in Raft using Coq
by notsony on Thursday August 06, 2015 @03:04PM
(#10018623)
Can you recommend and (1) books and (2) online lectures/courses on proofs which use Coq? Thanks!
Re:Proof of linearizability in Raft using Coq
by dougws on Thursday August 06, 2015 @03:15PM
(#10018693)
At this point, the standard intro text is Software Foundations [1]. I highly recommend it; it will teach you Coq and also probably make you a better programmer. After SF, Certified Programming with Dependent Types [2] gets more into the practice of proving serious programs correct. These books are both available online in the form of literate Coq files.
As far as online lectures, OPLSS [3] often has Coq lectures which are quite good.
[1] http://www.cis.upenn.edu/~bcpierce/sf/current/index.html
[2] http://adam.chlipala.net/cpdt/
[3] https://www.cs.uoregon.edu/research/summerschool/summer15/
Re:Proof of linearizability in Raft using Coq
by notsony on Thursday August 06, 2015 @03:47PM
(#10018913)
Thanks!
Re:Proof of linearizability in Raft using Coq
by whitten on Thursday August 06, 2015 @03:15PM
(#10018694)
What would be the process to show that another key-value pair system is able to satisfy all the specifications so it is comparable to vard ?
Re:Proof of linearizability in Raft using Coq
by dougws on Thursday August 06, 2015 @04:26PM
(#10019182)
One could imagine doing some kind of differential testing of another key-value store against vard to ensure that for a random but large number of requests, they return the same value. I'm not sure that doing that would gain you anything over using Jepsen [1], though. One could also imagine implementing another key-value store in Verdi and proving it equivalent to vard; reasons to do this might include using better data structures or serialization mechanisms, or a different consensus protocol. I'm not sure that this would require significantly less effort than proving this new key-value store (usrd? whittend? :)) correct from scratch, but I'd love to see someone do this!