The cluster-sending problem

The cluster-sending problem is the problem of sending a message between two clusters of potentially-unreliable replicas (e.g., clusters managed via a Byzantine fault-tolerant consensus protocol). Recently, it has been shown that the cluster-sending problem is a distinct problem than consensus that can be solved with lower worst-case complexity. For example, in the setting of two clusters with n replicas each of which at-most f, 2f < n are faulty, one can perform cluster sending in O(n) messages.

Using probabilistic techniques one can do significantly better, however: a probabilistic approach can perform cluster-sending under the same circumstances with an expected-case of only four communication phases.

Project Files and Related Publications

1. The experimental evaluation of probabilistic cluster-sending methods. source code (.zip).
   Full implementation of an evaluation of the viability to use probabilistic experiments, as performed by probabilistic cluster-sending protocols, and their full evaluation in the context of cluster-sending (e.g., to determine practical expected communication costs and variance therein). The implementation contains all supporting tooling used during the experiments. The source code contains step-by-step instructions to compile and use the code using either G++ or Microsoft Visual C++. In addition, full measurements are provided.