  This paper considers the classical state machine replication (SMR) problem in
a distributed system model inspired by cross-chain exchanges. We propose a
novel SMR protocol adapted for this model. Each state machine transition takes
$O(n)$ message delays, where $n$ is the number of active participants, of which
any number may be Byzantine. This protocol makes novel use of path signatures
to keep replicas consistent. This protocol design cleanly separates application
logic from fault-tolerance, providing a systematic way to replace complex
ad-hoc cross-chain protocols with a more principled approach.
