  Replicated state machines (RSMs) cannot effectively communicate today as
there is no formal framework or efficient protocol to do so. To address this
issue, we introduce a new primitive, the Cross-Cluster Consistent Broadcast
(C3B) and present PICSOU, a practical C3B implementation. PICSOU draws
inspiration from networking and TCP to allow two RSMs to communicate with
constant metadata overhead in the failure-free case and minimal number of
message resends in the case of failures. PICSOU is flexible and allows both
crash fault-tolerant and byzantine fault-tolerant protocols to communicate. At
the heart of PICSOU's good performance and generality lies a novel technique we
call QUACKs (quorum acknowledgements) that allow nodes in each RSM to precisely
determine when messages have definitely been received, or definitely been lost.
Our results are promising: we obtain up to 24x better performance than existing
all-to-all solutions.
