Byzantine Fault-Tolerant Causal Ordering
Anshuman Misra, Ajay D. Kshemkalyani · 2023
Byzantine fault-tolerant causal ordering of messages in asynchronous systems is useful to many applications. Although the problem has been studied for broadcast communication, it has not been examined for unicasts or multicasts in asynchronous systems. In this paper, we use execution histories to prove that it is impossible to solve causal ordering for both unicasts and multicasts in an asynchronous system with one or more Byzantine processes. In view of these impossibility results, we propose the Channel Sync Algorithms to provide causal order of unicasts and multicasts under the Byzantine failure model in synchronous systems, which have a known upper bound on message latency. The Channel Sync Algorithms operate under the synchronous system model, but are inherently asynchronous and offer a high degree of concurrency as lock-step communication is not assumed.