2026-08-04T08:07:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19101 2024-03-06T11:03:11Z ddc:004 open_access

Detecting Causality in the Presence of Byzantine Processes: The Synchronous Systems Case Misra, Anshuman Kshemkalyani, Ajay D. Byzantine fault-tolerance causality happens before distributed system message-passing synchronous system 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anshuman Misra and Ajay D. Kshemkalyani 2023 Is Part Of LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2023.11 urn:nbn:de:0030-drops-191017 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode