Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho

Ken Birman; Sagar Jha; Mae Milano; Lorenzo Rosa; Weijia Song; Edward Tremel

doi:10.1007/978-3-031-44274-2_14

Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho

Ken Birman, Sagar Jha, Mae Milano, Lorenzo Rosa, Weijia Song, Edward Tremel

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Our work centers on a programming style in which a system separates data movement from control-data exchange, streaming the former over hardware-implemented reliable channels, while using a new form of distributed shared memory to manage the latter. Protocol decisions and control actions are expressed as monotonic predicates over the control data guarding protocol actions. Provable invariants about the protocol are expressed as effectively-common knowledge, which can be derived from the monotonic predicates in effect during a particular membership epoch. The methodology enables a natural style of code that is easy to reason about, and it runs efficiently on modern hardware. We used this approach to create Derecho, an optimal Paxos-based data replication library that sets performance records, and we believe it is broadly applicable to the construction of reliable distributed systems on high-bandwidth networks.

Original language	English (US)
Title of host publication	Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings
Editors	Shlomi Dolev, Baruch Schieber
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	172-190
Number of pages	19
ISBN (Print)	9783031442735
DOIs	https://doi.org/10.1007/978-3-031-44274-2_14
State	Published - 2023
Event	25th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2023 - Jersey City, United States Duration: Oct 2 2023 → Oct 4 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14310 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2023
Country/Territory	United States
City	Jersey City
Period	10/2/23 → 10/4/23

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-44274-2_14

Cite this

Birman, K., Jha, S., Milano, M., Rosa, L., Song, W., & Tremel, E. (2023). Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho. In S. Dolev, & B. Schieber (Eds.), Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings (pp. 172-190). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14310 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-44274-2_14

Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho. / Birman, Ken; Jha, Sagar; Milano, Mae et al.
Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings. ed. / Shlomi Dolev; Baruch Schieber. Springer Science and Business Media Deutschland GmbH, 2023. p. 172-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14310 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Birman, K, Jha, S, Milano, M, Rosa, L, Song, W & Tremel, E 2023, Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho. in S Dolev & B Schieber (eds), Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14310 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 172-190, 25th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2023, Jersey City, United States, 10/2/23. https://doi.org/10.1007/978-3-031-44274-2_14

Birman K, Jha S, Milano M, Rosa L, Song W, Tremel E. Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho. In Dolev S, Schieber B, editors, Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 172-190. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-44274-2_14

Birman, Ken ; Jha, Sagar ; Milano, Mae et al. / Invited Paper : Monotonicity and Opportunistically-Batched Actions in Derecho. Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings. editor / Shlomi Dolev ; Baruch Schieber. Springer Science and Business Media Deutschland GmbH, 2023. pp. 172-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0d4a0eae0c2c440d970dd5ac0ed80a60,

title = "Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho",

abstract = "Our work centers on a programming style in which a system separates data movement from control-data exchange, streaming the former over hardware-implemented reliable channels, while using a new form of distributed shared memory to manage the latter. Protocol decisions and control actions are expressed as monotonic predicates over the control data guarding protocol actions. Provable invariants about the protocol are expressed as effectively-common knowledge, which can be derived from the monotonic predicates in effect during a particular membership epoch. The methodology enables a natural style of code that is easy to reason about, and it runs efficiently on modern hardware. We used this approach to create Derecho, an optimal Paxos-based data replication library that sets performance records, and we believe it is broadly applicable to the construction of reliable distributed systems on high-bandwidth networks.",

author = "Ken Birman and Sagar Jha and Mae Milano and Lorenzo Rosa and Weijia Song and Edward Tremel",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 25th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2023 ; Conference date: 02-10-2023 Through 04-10-2023",

year = "2023",

doi = "10.1007/978-3-031-44274-2_14",

language = "English (US)",

isbn = "9783031442735",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "172--190",

editor = "Shlomi Dolev and Baruch Schieber",

booktitle = "Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Invited Paper

T2 - 25th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2023

AU - Birman, Ken

AU - Jha, Sagar

AU - Milano, Mae

AU - Rosa, Lorenzo

AU - Song, Weijia

AU - Tremel, Edward

PY - 2023

Y1 - 2023

N2 - Our work centers on a programming style in which a system separates data movement from control-data exchange, streaming the former over hardware-implemented reliable channels, while using a new form of distributed shared memory to manage the latter. Protocol decisions and control actions are expressed as monotonic predicates over the control data guarding protocol actions. Provable invariants about the protocol are expressed as effectively-common knowledge, which can be derived from the monotonic predicates in effect during a particular membership epoch. The methodology enables a natural style of code that is easy to reason about, and it runs efficiently on modern hardware. We used this approach to create Derecho, an optimal Paxos-based data replication library that sets performance records, and we believe it is broadly applicable to the construction of reliable distributed systems on high-bandwidth networks.

AB - Our work centers on a programming style in which a system separates data movement from control-data exchange, streaming the former over hardware-implemented reliable channels, while using a new form of distributed shared memory to manage the latter. Protocol decisions and control actions are expressed as monotonic predicates over the control data guarding protocol actions. Provable invariants about the protocol are expressed as effectively-common knowledge, which can be derived from the monotonic predicates in effect during a particular membership epoch. The methodology enables a natural style of code that is easy to reason about, and it runs efficiently on modern hardware. We used this approach to create Derecho, an optimal Paxos-based data replication library that sets performance records, and we believe it is broadly applicable to the construction of reliable distributed systems on high-bandwidth networks.

UR - http://www.scopus.com/inward/record.url?scp=85174519519&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85174519519&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-44274-2_14

DO - 10.1007/978-3-031-44274-2_14

M3 - Conference contribution

AN - SCOPUS:85174519519

SN - 9783031442735

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 172

EP - 190

BT - Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Proceedings

A2 - Dolev, Shlomi

A2 - Schieber, Baruch

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 2 October 2023 through 4 October 2023

ER -

Invited Paper: Monotonicity and Opportunistically-Batched Actions in Derecho

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this