DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2024.10

Vertical Atomic Broadcast and Passive Replication

Authors: Manuel Bravo, Gregory Chockler, Alexey Gotsman, Alejandro Naser-Pastoriza, and Christian Roldán

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

Atomic broadcast is a reliable communication abstraction ensuring that all processes deliver the same set of messages in a common global order. It is a fundamental building block for implementing fault-tolerant services using either active (aka state-machine) or passive (aka primary-backup) replication. We consider the problem of implementing reconfigurable atomic broadcast, which further allows users to dynamically alter the set of participating processes, e.g., in response to failures or changes in the load. We give a complete safety and liveness specification of this communication abstraction and propose a new protocol implementing it, called Vertical Atomic Broadcast, which uses an auxiliary service to facilitate reconfiguration. In contrast to prior proposals, our protocol significantly reduces system downtime when reconfiguring from a functional configuration by allowing it to continue processing messages while agreement on the next configuration is in progress. Furthermore, we show that this advantage can be maintained even when our protocol is modified to support a stronger variant of atomic broadcast required for passive replication.

Cite as

Manuel Bravo, Gregory Chockler, Alexey Gotsman, Alejandro Naser-Pastoriza, and Christian Roldán. Vertical Atomic Broadcast and Passive Replication. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bravo_et_al:LIPIcs.DISC.2024.10,
  author =	{Bravo, Manuel and Chockler, Gregory and Gotsman, Alexey and Naser-Pastoriza, Alejandro and Rold\'{a}n, Christian},
  title =	{{Vertical Atomic Broadcast and Passive Replication}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.10},
  URN =		{urn:nbn:de:0030-drops-212363},
  doi =		{10.4230/LIPIcs.DISC.2024.10},
  annote =	{Keywords: Reconfiguration, consensus, replication}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2019.42

A Categorical Account of Replicated Data Types

Authors: Fabio Gadducci, Hernán Melgratti, Christian Roldán, and Matteo Sammartino

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract

Replicated Data Types (RDTs) have been introduced as a suitable abstraction for dealing with weakly consistent data stores, which may (temporarily) expose multiple, inconsistent views of their state. In the literature, RDTs are commonly specified in terms of two relations: visibility, which accounts for the different views that a store may have, and arbitration, which states the logical order imposed on the operations executed over the store. Different flavours, e.g., operational, axiomatic and functional, have recently been proposed for the specification of RDTs. In this work, we propose an algebraic characterisation of RDT specifications. We define categories of visibility relations and arbitrations, show the existence of relevant limits and colimits, and characterize RDT specifications as functors between such categories that preserve these additional structures.

Cite as

Fabio Gadducci, Hernán Melgratti, Christian Roldán, and Matteo Sammartino. A Categorical Account of Replicated Data Types. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gadducci_et_al:LIPIcs.FSTTCS.2019.42,
  author =	{Gadducci, Fabio and Melgratti, Hern\'{a}n and Rold\'{a}n, Christian and Sammartino, Matteo},
  title =	{{A Categorical Account of Replicated Data Types}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.42},
  URN =		{urn:nbn:de:0030-drops-116042},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.42},
  annote =	{Keywords: Replicated data type, Specification, Functorial characterisation}
}

Search Results

Documents authored by Roldán, Christian

Vertical Atomic Broadcast and Passive Replication

Abstract

Cite as

A Categorical Account of Replicated Data Types

Abstract

Cite as

Thanks for your feedback!

Could not send message