  Logical clocks are a fundamental tool to establish causal ordering of events
in a distributed system. They have been applied in weakly consistent storage
systems, causally ordered broadcast, distributed snapshots, deadlock detection,
and distributed system debugging. However, prior logical clock constructs fail
to work in an open network with Byzantine participants. In this work, we
present Chrono, a novel logical clock system that targets such challenging
environment. We first redefine causality properties among distributed processes
under the Byzantine failure model. To enforce these properties, Chrono defines
a new validator abstraction for building fault-tolerant logical clocks.
Furthermore, our validator abstraction is customizable: Chrono includes
multiple backend implementations for the abstraction, each with different
security-performance trade-offs. We have applied Chrono to build two
decentralized applications, a mutual exclusive service and a weakly consistent
key-value store. Chrono adds only marginal overhead compared to systems that
tolerate no Byzantine faults. It also out-performs state-of-the-art BFT total
order protocols by significant margins.
