2 Search Results for "Kaippallimalil, John"

Document
DOI: 10.4230/LIPIcs.DISC.2025.15
Asynchronous Latency and Fast Atomic Snapshot

Authors: João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
This paper introduces a novel, fast atomic-snapshot protocol for asynchronous message-passing systems. In the process of defining what "fast" means exactly, we spot a few interesting issues that arise when conventional time metrics are applied to long-lived asynchronous algorithms. We reveal some gaps in latency claims made in earlier work on snapshot algorithms, which hamper their comparative time-complexity analysis. We then come up with a new unifying time-complexity metric that captures the latency of an operation in an asynchronous, long-lived implementation. This allows us to formally grasp latency improvements of our atomic-snapshot algorithm with respect to the state-of-the-art protocols: optimal latency in fault-free runs without contention, short constant latency in fault-free runs with contention, the worst-case latency proportional to the number of active concurrent failures, and constant amortized latency.
Cite as

João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud. Asynchronous Latency and Fast Atomic Snapshot. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.DISC.2025.15,
  author =	{Bezerra, Jo\~{a}o Paulo and Freitas, Luciano and Kuznetsov, Petr and Rambaud, Matthieu},
  title =	{{Asynchronous Latency and Fast Atomic Snapshot}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.15},
  URN =		{urn:nbn:de:0030-drops-248326},
  doi =		{10.4230/LIPIcs.DISC.2025.15},
  annote =	{Keywords: Asynchronous systems, time complexity, atomic snapshot, crash faults}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.29
Linearizable Replicated State Machines With Lattice Agreement

Authors: Xiong Zheng, Vijay K. Garg, and John Kaippallimalil

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
This paper studies the lattice agreement problem in asynchronous systems and explores its application to building a linearizable replicated state machine (RSM). First, we propose an algorithm to solve the lattice agreement problem in O(log f) asynchronous rounds, where f is the number of crash failures that the system can tolerate. This is an exponential improvement over the previous best upper bound of O(f). Second, Faleiro et al have shown in [Faleiro et al. PODC, 2012] that combination of conflict-free data types and lattice agreement protocols can be applied to implement a linearizable RSM. They give a Paxos style lattice agreement protocol, which can be adapted to implement a linearizable RSM and guarantee that a command by a client can be learned in at most O(n) message delays, where n is the number of proposers. Later, Xiong et al in [Xiong et al. DISC, 2018] gave a lattice agreement protocol which improves the O(n) message delay guarantee to O(f). However, neither of the protocols is practical for building a linearizable RSM. Thus, in the second part of the paper, we first give an improved protocol based on the one proposed by Xiong et al. Then, we implement a simple linearizable RSM using our improved protocol and compare our implementation with an open source Java implementation of Paxos. Results show that better performance can be obtained by using lattice agreement based protocols to implement a linearizable RSM compared to traditional consensus based protocols.
Cite as

Xiong Zheng, Vijay K. Garg, and John Kaippallimalil. Linearizable Replicated State Machines With Lattice Agreement. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.OPODIS.2019.29,
  author =	{Zheng, Xiong and Garg, Vijay K. and Kaippallimalil, John},
  title =	{{Linearizable Replicated State Machines With Lattice Agreement}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.29},
  URN =		{urn:nbn:de:0030-drops-118158},
  doi =		{10.4230/LIPIcs.OPODIS.2019.29},
  annote =	{Keywords: Lattice Agreement, Generalized Lattice Agreement, Replicated State Machine, Consensus}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2020

  • Refine by Author
  • 1 Bezerra, João Paulo
  • 1 Freitas, Luciano
  • 1 Garg, Vijay K.
  • 1 Kaippallimalil, John
  • 1 Kuznetsov, Petr
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 Asynchronous systems
  • 1 Consensus
  • 1 Generalized Lattice Agreement
  • 1 Lattice Agreement
  • 1 Replicated State Machine
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact