title: How to minimize the number of retransmissions to synchronize N replicas?
body: <p>Given a set of M unsynchronized replicas, how do we find the subset of given size N that minimizes the number of message retransmissions necessary to synchronize their message states in a reliable multicast environment (i.e. - all replicas reliably receive all other replicas' messages)?</p>
  
  <p>The message states of the replicas consists of messages they each have from the same D sources (D >= M).  For each source, a replica has all of the messages from that source up to some highest ordinal (i.e. - FIFO, with no holes, starting from zero).  So, a replica's message state can be represented as a vector of ordinals, with each element corresponding to a source.  Alternatively, you can think of a replica's message state as a point in D-dimensional space, if you like.</p>
  
  <p>Assume that all M replicas have already exchanged their message state vectors, so all of them have a matrix of M rows x D columns of all of their message states.  So, this is now purely a centralized computational problem given that matrix.</p>
  
  <p>The brute force approach that gives an optimal answer would be to examine all (M select N) subsets and pick one that requires the minimum number of retransmissions necessary to synchronize that subset.  The problem is that this approach looks to have at least factorial asymptotic complexity in M.</p>
  
  <p>I wanted to see if anyone knows or could think of an optimal algorithm with much better asymptotic bounds?</p>
  
  <p>Originally, I was thinking of tackling it as a graph theory problem with the replicas' message states being vertices in a fully connected graph where the edge weights were the Manhattan distance between the two endpoints' message state vectors.  Then do something like min-link agglomerative hierarchical clustering using Prim's algorithm followed by Kruskal's algorithm where we stop once any cluster's size equals or exceeds N.  </p>
  
  <p>That can run in O(M^2) time, but I can construct counter examples where it doesn't immediately yield the optimal answer.  For example, with D = 1 for simplicity's sake, let the M = 7 replicas' ordinals be { 0, 2, 4, 14, 15, 16, 19 } and N = 5.  Kruskal's algorithm will cluster { 14, 15, 16, 19 } and { 0, 2, 4 } and then join those two clusters together in the final step.  But the actual answer we wanted is to synchronize the replicas with states { 2, 4, 14, 15, 16 } together.  Maybe we could stop when the first merged cluster exceeds N and then try to prune it?  But in this example, then we are right back to asking the original question again as the cluster on which we stopped actually contains all M replicas!  And, of course, this problem isn't nearly as simple when D > 1, which it always will be (D >= M).</p>
  
  <p>Another problem with the above approach is that if the algorithm chooses to synchronize two clusters of replicas into a bigger cluster, then this not only affects the distances between the other clusters and the newly merged cluster (e.g. - like in normal agglomerative hierarchical clustering) but also the distances between all of the other clusters too because they all hear and can benefit from any retransmissions sent.  So, all of the distances between all of the clusters can change after each merge step and in a not-so-simple manner if you allow for a replica to benefit from messages received here not in FIFO, no-holes order.  For example, a replica A has messages from source D1 up through ordinal X.  The algorithm chooses to synchronize two clusters of replicas, neither including A, that required retransmission of messages from source D1 of X+5 through X+10.  An optimal algorithm would realize that A potentially benefits from these retransmissions even though they are beyond his FIFO, no-holes ordinal for source D1 with a message gap of X+1 through X+4.</p>
  
  <p>A different way I thought about tackling it was to consider it a geometrical problem where the M replicas' states represent points in a D-dimensional L1 space.  Then we want to find the smallest "volume" convex hull that contains at least N points.  This may not actually be a good approach but thinking about it geometrically naturally captures the idea that all replicas can benefit from any two sets of replicas synchronizing.  Most of their distances will be reduced to the new object's surface (not vertices!) created by the merge of the two sets' states.</p>
  
  <p>EDIT - Another way I thought about it came from the example I gave.  For each source DX find the subset of N replicas that requires the minimum number of retransmissions to synchronize on that source.  That's easy enough.  The problem then is that you then have to compare and modify these D subsets to get them all to cover the same N replicas.  It's not a fully formed idea because the minimum N in each dimension DX is a local minimum in the global space that could be in the wrong area as the globally optimal answer for that dimension.  Anyway, it's another idea to think about.</p>
  
  <p>EDIT2 - Going back to Prim's + Kruskal's algorithm and ignoring that each merge updates the relative distances between all of the clusters, is it true that when we discover the first cluster whose size equals or exceeds N, then the optimal answer must be some subset of that cluster?  If the cluster's size equals N, then we are done.  If the cluster's size exceeds N, then could we do something like compute the centroid of the cluster and choose the N closest replicas to the centroid?  Would that yield the optimal answer?  That still doesn't seem right because it doesn't consider the "directionality" of the various distances from the centroid.  That is, it doesn't differentiate between two replicas that are close to each other in D-dimensional space (which it should favor) as opposed to two replicas that are in "opposite" directions from each other with respect to the centroid.  Maybe we could instead look at the minimum spanning tree of the replicas in the cluster and somehow prune it efficiently to find the minimum weight subset that remains connected?</p>
  
  <p>Any ideas or pointers to relevant algorithms would be greatly appreciated!</p>