Detecting causality in the presence of Byzantine processes: The case of synchronous systems

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, irrespecti...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2024-12, Vol.301, p.105212, Article 105212
Main Authors: Misra, Anshuman, Kshemkalyani, Ajay D.
Format: Article
Language:English
Subjects:
Byzantine fault-tolerance
Causality
Distributed algorithm
Message-passing
Synchronization
Synchronous system
“Happened before” relation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. We prove the result by providing two algorithms. The first algorithm uses the Replicated State Machine (RSM) approach and vector clocks. The second algorithm is round-based and uses matrix clocks. The RSM-based algorithm can also run deterministically in partially synchronous systems.
ISSN:0890-5401
DOI:10.1016/j.ic.2024.105212