Name
Abstract | ||
|---|---|---|
In recent years there has been interest in achieving application-level consistency criteria without the latency and availability costs of strongly consistent storage infrastructure. A standard technique is to adopt a vocabulary of commutative operations; this avoids the risk of inconsistency due to message reordering. Another approach was recently captured by the CALM theorem, which proves that logically monotonic programs are guaranteed to be eventually consistent. In logic languages such as Bloom, CALM analysis can automatically verify that programs achieve consistency without coordination. In this paper we present BloomL, an extension to Bloom that takes inspiration from both of these traditions. BloomL generalizes Bloom to support lattices and extends the power of CALM analysis to whole programs containing arbitrary lattices. We show how the Bloom interpreter can be generalized to support efficient evaluation of lattice-based code using well-known strategies from logic programming. Finally, we use BloomL to develop several practical distributed programs, including a key-value store similar to Amazon Dynamo, and show how BloomL encourages the safe composition of small, easy-to-analyze lattices into larger programs. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2391229.2391230 | SoCC |
Keywords | Field | DocType |
blooml generalizes bloom,consistent storage infrastructure,logic programming,calm theorem,bloom interpreter,logic language,arbitrary lattice,calm analysis,amazon dynamo,application-level consistency criterion,algebra,theorems,bloom,computer programming,lattice,distributed programming,eventual consistency | Monotonic function,Eventual consistency,Lattice (order),Commutative property,Computer science,Theoretical computer science,Interpreter,Logic programming,Vocabulary,Computer programming,Distributed computing | Conference |
Citations | PageRank | References |
42 | 1.27 | 32 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neil Conway | 1 | 458 | 21.46 |
| William R. Marczak | 2 | 274 | 12.55 |
| Peter Alvaro | 3 | 463 | 28.96 |
| Joseph M. Hellerstein | 4 | 14093 | 1651.14 |
| David Maier | 5 | 5639 | 1666.90 |