2014 · 31 citations · 19 references
ComputingComputer ScienceComputer SystemsDistributed SystemsFault-tolerant SystemsFormal MethodsConcurrency ControlData ReplicationDistributed DatabasesFault Tolerance DesignReliable Distributed SystemsReliable System DesignBroadcastBroadcast Protocol DesignCorrectness ProofsData Replication ProtocolsDistributed ReplicationFault-tolerant Database SystemsReliability SpecificationTotal Order Broadcast
Fault-tolerant distributed systems often contain complex error handling code. Such code is hard to test or model-check because there are often too many possible failure scenarios to consider. As we will demonstrate in this paper, formal methods have evolved to a state in which it is possible to generate this code along with correctness guarantees. This paper describes our experience with building highly-available databases using replication protocols that were generated with the help of correct-by-construction formal methods. The goal of our project is to obtain databases with unsurpassed reliability while providing good performance. We report on our experience using a total order broadcast protocol based on Paxos and specified using a new formal language called Event ML. We compile Event ML specifications into a form that can be formally verified while simultaneously obtaining code that can be executed. We have developed two replicated databases based on this code and show that they have performance that is competitive with popular databases in one of the two considered benchmarks.
19
Consensus in the presence of partial synchrony
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer · Journal of the ACM · 1988 · 1.9K citations · Full text
Choice Reviews Online · 1995 · 1.8K citations
Gerwin Klein, Kevin Elphinstone, Gernot Heiser et al. · 2009 · 1.6K citations
Formal certification of a compiler back-end or
Xavier Leroy · 2006 · 652 citations