Solvability of Byzantine Fault-Tolerant Causal Ordering: Synchronous Systems Case
Anshuman Misra, Ajay D. Kshemkalyani · 2024
Causal ordering is widely used in distributed systems to maintain validity and correctness of data across concurrent updates. Previous work has shown that it is impossible to solve the causal ordering problem under the strong safety condition in cryptography-free Byzantine-prone systems. It has also been shown that it is impossible to solve deterministic causal ordering for unicasts/multicasts in asynchronous systems even under a weaker notion of safety called weak safety. However, inherently asynchronous (round-free) protocols solve causal ordering for unicasts/multicasts in synchronous systems under the weak safety condition. In this paper, we first examine the causal ordering problem under the notion of synchronous rounds. We examine whether causal ordering is solvable by simulating rounds in synchronous systems under fault-free, crash-failure and Byzantine failure models. We then provide a round-based synchronous algorithm for causal ordering of unicasts/multicasts/broadcasts under the strong safety condition. Finally, we provide an overall analysis of solvability of causal ordering in synchronous systems for a variety of system model settings.