DROPS

Document

DOI: 10.4230/LIPIcs.TIME.2023.11

Detecting Causality in the Presence of Byzantine Processes: The Synchronous Systems Case

Authors: Anshuman Misra and Ajay D. Kshemkalyani

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)

Abstract

Detecting causality or the happens before relation between events in a distributed system is a fundamental building block for distributed applications. It was recently proved that this problem cannot be solved in an asynchronous distributed system in the presence of Byzantine processes, irrespective of whether the communication mechanism is via unicasts, multicasts, or broadcasts. In light of this impossibility result, we turn attention to synchronous systems and examine the possibility of solving the causality detection problem in such systems. In this paper, we prove that causality detection between events can be solved in the presence of Byzantine processes in a synchronous distributed system. The positive result holds for unicast, multicast, as well as broadcast modes of communication. We prove the result by providing an algorithm. Our solution uses the Replicated State Machine (RSM) approach and vector clocks.

Cite as

Anshuman Misra and Ajay D. Kshemkalyani. Detecting Causality in the Presence of Byzantine Processes: The Synchronous Systems Case. In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.TIME.2023.11,
  author =	{Misra, Anshuman and Kshemkalyani, Ajay D.},
  title =	{{Detecting Causality in the Presence of Byzantine Processes: The Synchronous Systems Case}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.11},
  URN =		{urn:nbn:de:0030-drops-191017},
  doi =		{10.4230/LIPIcs.TIME.2023.11},
  annote =	{Keywords: Byzantine fault-tolerance, causality, happens before, distributed system, message-passing, synchronous system}
}

Search Results

Documents authored by Misra, Anshuman

Detecting Causality in the Presence of Byzantine Processes: The Synchronous Systems Case

Abstract

Cite as

Thanks for your feedback!

Could not send message