column

I do declare: consensus in a logic language

Authors:

Peter Alvaro,

Tyson Condie,

Neil Conway,

Joseph M. Hellerstein,

Russell SearsAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 43, Issue 4

Pages 25 - 30

https://doi.org/10.1145/1713254.1713261

Published: 27 January 2010 Publication History

Get Access

Abstract

The Paxos consensus protocol can be specified concisely, but is notoriously difficult to implement in practice. We recount our experience building Paxos in Overlog, a distributed declarative programming language. We found that the Paxos algorithm is easily translated to declarative logic, in large part because the primitives used in consensus protocol specifications map directly to simple Overlog constructs such as aggregation and selection. We discuss the programming idioms that appear frequently in our implementation, and the applicability of declarative programming to related application domains.

References

[1]

T.D. Chandra, R. Griesemer, and J. Redstone. Paxos made live: An engineering perspective. In PODC, pages 398--407, 2007.

Digital Library

Google Scholar

[2]

M.J. Fischer. The consensus problem in unreliable distributed systems (A brief survey). In Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, pages 127--140, 1983.

Digital Library

Google Scholar

[3]

J. Gray. The transaction concept: virtues and limitations (invited paper). In Proceedings of the Seventh International Conference on Very Large Data Bases, pages 144--154, 1981.

Digital Library

Google Scholar

[4]

J. Kirsch and Y. Amir. Paxos for system builders. Technical Report CNDS-2008-2, Johns Hopkins University, 2008.

Digital Library

Google Scholar

[5]

L. Lamport. "Sometime" is sometimes "not never": on the temporal logic of programs. In Proceedings of the 7th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 174--185, 1980.

Digital Library

Google Scholar

[6]

L. Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133--169, 1998.

Digital Library

Google Scholar

[7]

L. Lamport. Paxos made simple. SIGACT News, 32(4):51--58, December 2001.

Google Scholar

[8]

B.T. Loo, T. Condie, J.M. Hellerstein, P. Maniatis, T. Roscoe, and I. Stoica. Implementing declarative overlays. In SOSP, 2005.

Digital Library

Google Scholar

[9]

D. Maziéres. Paxos made practical. http://www.scs.stanford.edu/~dm/home/papers/paxos.pdf, January 2007.

Google Scholar

[10]

C. Mohan, B. Lindsay, and R. Obermarck. Transaction management in the R* distributed database management system. ACM TODS, 11(4):378--396, 1986.

Digital Library

Google Scholar

[11]

S. Mullender, editor. Distributed Systems. Addison-Wesley, second edition, 1993.

Google Scholar

[12]

R.D. Prisco, B.W. Lampson, and N.A. Lynch. Revisiting the paxos algorithm. In Proceedings of the 11th International Workshop on Distributed Algorithms, pages 111--125, 1997.

Digital Library

Google Scholar

[13]

R. Sears and E. Brewer. Stasis: Flexible transactional storage. In OSDI, pages 29--44, 2006.

Digital Library

Google Scholar

[14]

B. Szekely and E. Torres. A Paxon evaluation of P2. http://klinewoods.com/papers/p2paxos.pdf.

Google Scholar

Cited By

View all

Chen HWu CZhao ARaghothaman MNaik MLoo B(2023)Synthesizing Formal Network Specifications From Input-Output ExamplesIEEE/ACM Transactions on Networking10.1109/TNET.2022.320855131:3(994-1009)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3208551
Liu Y(2018)Logic programming applicationsDeclarative Logic Programming10.1145/3191315.3191326(519-548)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1145/3191315.3191326
Ma LYang WHuo YZhong Y(2018)Research on access control model of social network based on distributed logicFuture Generation Computer Systems10.1016/j.future.2017.11.04183:C(173-182)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1016/j.future.2017.11.041
Show More Cited By

Recommendations

How to declare an imperative

How can we integrate interaction into a purely declarative language? This tutorial describes a solution to this problem based on a monad. The solution has been implemented in the functional language Haskell and the declarative language Escher. ...
Towards data-aware constraints in declare
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied Computing

In recent years, declarative, constraint-based approaches have been proposed to model loosely-structured business processes, mediating between support and flexibility. A notable example is the Declare framework, equipped with a graphical declarative ...
Understanding Declare models: strategies, pitfalls, empirical results

Declarative approaches to business process modeling are regarded as well suited for highly volatile environments, as they enable a high degree of flexibility. However, problems in understanding and maintaining declarative process models often impede ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 43, Issue 4

January 2010

105 pages

ISSN:0163-5980

DOI:10.1145/1713254

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 January 2010

Published in SIGOPS Volume 43, Issue 4

Check for updates

Qualifiers

Column

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
287
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen HWu CZhao ARaghothaman MNaik MLoo B(2023)Synthesizing Formal Network Specifications From Input-Output ExamplesIEEE/ACM Transactions on Networking10.1109/TNET.2022.320855131:3(994-1009)Online publication date: Jun-2023
Liu Y(2018)Logic programming applicationsDeclarative Logic Programming10.1145/3191315.3191326(519-548)Online publication date: 1-Sep-2018
Ma LYang WHuo YZhong Y(2018)Research on access control model of social network based on distributed logicFuture Generation Computer Systems10.1016/j.future.2017.11.04183:C(173-182)Online publication date: 1-Jun-2018
(2018)Declarative Logic ProgrammingundefinedOnline publication date: 1-Sep-2018
Alvaro PConway NHellerstein JMaier D(2017)BlazesACM Transactions on Database Systems10.1145/311021442:4(1-31)Online publication date: 27-Oct-2017
Liu YStoller SLin B(2017)From Clarity to Efficiency for Distributed AlgorithmsACM Transactions on Programming Languages and Systems10.1145/299459539:3(1-41)Online publication date: 26-May-2017
Ma LLeng PZhong YYang W(2017)Research on semantic of updatable distributed logic and its application in access controlJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.12.006103(104-112)Online publication date: May-2017
Drăgoi CHenzinger TZufferey D(2016)PSync: a partially synchronous language for fault-tolerant distributed algorithmsACM SIGPLAN Notices10.1145/2914770.283765051:1(400-415)Online publication date: 11-Jan-2016
Drăgoi CHenzinger TZufferey DBodik RMajumdar R(2016)PSync: a partially synchronous language for fault-tolerant distributed algorithmsProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837650(400-415)Online publication date: 11-Jan-2016
Bodik RMajumdar R(2016)Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming LanguagesundefinedOnline publication date: 11-Jan-2016
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

How to declare an imperative

Towards data-aware constraints in declare

Understanding Declare models: strategies, pitfalls, empirical results