  Traditional resilient systems operate on fully-replicated fault-tolerant
clusters, which limits their scalability and performance. One way to make the
step towards resilient high-performance systems that can deal with huge
workloads, is by enabling independent fault-tolerant clusters to efficiently
communicate and cooperate with each other, as this also enables the usage of
high-performance techniques such as sharding and parallel processing. Recently,
such inter-cluster communication was formalized as the Byzantine
cluster-sending problem, and worst-case optimal protocols have been proposed
that solve this problem. Unfortunately, these protocols have an all-case linear
complexity in the size of the clusters involved.
  In this paper, we propose probabilistic cluster-sending techniques that can
reliably send messages from one Byzantine fault-tolerant cluster to another
with only an expected constant message complexity, this independent of the size
of the clusters involved. Depending on the robustness of the clusters involved,
our techniques require only two-to-four message round-trips. Furthermore, our
protocols can support worst-case linear communication between clusters, which
is optimal, and deal with asynchronous and unreliable communication. As such,
our work provides a strong foundation for the further development of resilient
high-performance systems.
