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.

Detecting Causality in the Presence of Byzantine Processes: There is No Holy Grail

"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."

Causal Ordering Properties of Byzantine Reliable Broadcast Primitives

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.

Anshuman Misra

3

1

SHORT BIO

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES