Detecting causality or the “happened before” relation between events in an asynchronous distributed system is a widely used building block in distributed applications. To the best of our knowledge, this problem has not been examined in a system with Byzantine processes. We prove the following results for an asynchronous system with Byzantine processes. (1) We prove that it is impossible to determine causality between events in the presence of even a single Byzantine process when processes communicate by unicasting. (2) We also prove a similar impossibility result when processes communicate by broadcasting. (3) We also prove a similar impossibility result when processes communicate by multicasting. (4–5) In an execution where there exists a causal path between two events passing through only correct processes, we prove that it is possible to detect causality between such a pair of events when processes communicate by unicasting or broadcasting. (6) However, when processes communicate by multicasting and there exists a causal path between two events passing through only correct processes, we prove that it is impossible to detect causality between such a pair of events. (7–9) Even with the use of cryptography, we prove that the impossibility results of (1–3) for unicasts , broadcasts, and multicasts, respectively, hold. (10–12) With the use of cryptography, when there exists a causal path between two events passing through only correct processes, we prove it is possible to detect causality between such a pair of events, irrespective of whether the communication is by unicasts, broadcasts, or multicasts. Our results are significant because Byzantine systems mirror the real world.

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.

Byzantine fault-tolerant causal ordering of messages is useful to many applications. Causal ordering requires a property that we term strong safety, and liveness. In this paper, we use execution histories to prove that it is impossible to solve causal ordering – strong safety and liveness – in a deterministic manner for unicasts, multicasts, and broadcasts in an asynchronous system with one or more Byzantine processes. We also define a weaker version of strong safety termed weak safety. We prove that it is impossible to solve causal ordering – weak safety and liveness – in a deterministic manner for unicasts and multicasts, in an asynchronous system with one or more Byzantine processes. In view of these impossibility results, we propose the Sender-Inhibition algorithm and the Channel Sync algorithm to provide causal order – weak safety and liveness – of unicasts under the Byzantine failure model in synchronous systems, which have a known upper bound on message latency. The 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. The two algorithms provide different trade-offs. We also indicate how the algorithms can be extended to multicasts.

Causal ordering of messages in distributed systems is important for capturing application-level semantics. To the best of our knowledge, Byzantine fault-tolerant causal ordering has not been attempted for point-to-point communication in an asynchronous setting. In this paper, we first prove that it is impossible to causally order messages under point-to-point communication in an asynchronous system with one or more Byzantine processes. In the face of this impossibility, we then present an algorithm that can causally order messages under point-to-point communication in the face of Byzantine failures, assuming the network provides a known upper bound on the message latency. We also prove that it is impossible to causally order multicasts in an asynchronous setting with one or more Byzantine processes. We then give an extension of our algorithm for unicasts to provide Byzantine fault-tolerant causal ordering of multicasts under the assumption of a known upper bound on the message latency.

Causal ordering of broadcasts is a widely used requirement in collaborative distributed software systems. We consider Byzantine-tolerant causal ordering of broadcasts in a replicated data store implemented over an incomplete graph network topology, wherein messages of the broadcast are sent via flooding. We propose two protocols to achieve this. The incomplete graph topology also occurs naturally in wireless networks and in overlay peer-to-peer networks. We identify four properties – safety, liveness, no impersonation, and no avatars – that a Byzantine-tolerant causal broadcast algorithm for a replicated data store over an incomplete graph must satisfy. We also reformulate the traditional properties – validity, integrity, self-delivery, and reliability (or termination) – specified for a complete graph in the literature for a replicated data store system over an incomplete graph topology. We then analyze whether Byzantine processes can mount attacks on these properties in our two protocols. We show results for the classical communication model and the local broadcast model.

Detecting causality or the happens before relation between events in an asynchronous distributed system is a fundamental building block for distributed applications. To the best of our knowledge, this problem has not been examined in a system with Byzantine processes. We prove the following results for an asynchronous system with Byzantine processes. (1) We prove that it is impossible to determine causality between events in the presence of even a single Byzantine process when processes communicate by unicasting. (2) We also prove a similar impossibility result when processes communicate by broadcasting. (3) We also prove a similar impossibility result when processes communicate by multicasting. (4) In an execution where there exists a causal path between two events passing through only correct processes, the impossibility result for unicasts remains. (5) However, when processes communicate by broadcasting and there exists a causal path between two events passing through only correct processes, it is possible to detect causality between such a pair of events. (6) In an execution where processes communicate by multicasting and there exists a causal path between two events passing through only correct processes, we prove that the impossibility result for multicasts remains.

In this paper, we examine the inherent properties of the Byzantine Reliable Broadcast (BRB) primitive as pertain to the ability to provide causal ordering. We prove the following results. First, we analyze Bracha’s BRB algorithm and show that under the failure-free model, safety is guaranteed across broadcasts. Second, we also prove that Bracha’s BRB algorithm guarantees safety across broadcasts under the crash failure model tolerating any number of crash failures. Third, we prove that Bracha’s BRB algorithm cannot provide weak or strong safety under the Byzantine failure model. Fourth, we prove that neither the Imbs-Raynal BRB protocol nor any (2,*)-round BRB protocol can provide causal order even if all processes are correct, and they must incur additional latency to causally order messages at a higher layer. The inherent causal ordering properties of Bracha’s BRB can be of use under favourable circumstances in practical applications, given the widespread adoption of the protocol.