jsc*_*410 5 algorithm geometry graph-algorithm data-synchronization
给定一组M个非同步副本,我们如何找到给定大小N的子集,以最小化在可靠的多播环境中同步其消息状态所需的消息重传次数(即 - 所有副本可靠地接收所有其他副本的消息)？
副本的消息状态由它们各自来自相同D源的消息组成(D> = M).对于每个源,副本具有来自该源的所有消息,直到某些最高序数(即 - FIFO,没有孔,从零开始).因此,副本的消息状态可以表示为序数向量,每个元素对应一个源.或者,如果您愿意,可以将副本的消息状态视为D维空间中的一个点.
假设所有M个副本已经交换了它们的消息状态向量,因此它们都具有所有消息状态的M行×D列的矩阵.因此,鉴于矩阵,现在这纯粹是一个集中的计算问题.
给出最佳答案的蛮力方法是检查所有(M选择N)子集并选择需要同步该子集所需的最小重传次数的子集.问题是这种方法在M中至少具有因子渐近复杂性.
我想知道是否有人知道或者可能会想到一个具有更好的渐近界限的最优算法？
最初,我正在考虑将其作为图论理论解决,其中复制品的消息状态是完全连接图中的顶点,其中边权重是两个端点的消息状态向量之间的曼哈顿距离.然后使用Prim算法跟随Kruskal算法进行min-link凝聚层次聚类,其中我们在任何聚类的大小等于或超过N时停止.
这可以在O(M ^ 2)时间内运行,但我可以构建反例,它不会立即产生最佳答案.例如,为简单起见,D = 1,让M = 7个复制品的序数为{0,2,4,14,15,16,19},N = 5.Kruskal的算法将聚类{14,15,16 ,19}和{0,2,4}然后在最后一步将这两个集群连接在一起.但我们想要的实际答案是将副本与状态{2,4,14,15,16}同步.也许我们可以在第一个合并的集群超过N然后尝试修剪它时停止？但是在这个例子中,我们又回来再次问原始问题,因为我们停止的集群实际上包含了所有M个副本!当然,当D> 1时,这个问题并不是那么简单,它总是(D> = M).
上述方法的另一个问题是,如果算法选择将两个副本群集同步到一个更大的群集中,那么这不仅会影响其他群集与新合并群集之间的距离(例如 - 就像在正常的凝聚层次聚类中一样),也是所有其他集群之间的距离,因为它们都听到并且可以从发送的任何重传中受益.因此,所有群集之间的所有距离都可以在每个合并步骤之后以非常简单的方式改变,如果您允许副本受益于此处接收的消息而不是FIFO,无孔顺序.例如,副本A具有从源D1到序号X的消息.算法选择同步两个副本群集,既不包括A,也需要从X + 5到X + 10的源D1重传消息.最优算法将意识到A可能从这些重传中受益,即使它们超出了他的FIFO,源D1的无孔序数,消息间隙为X + 1到X + 4.
我想到解决它的另一种方式是将其视为几何问题,其中M个复制品的状态代表D维L1空间中的点.然后我们想要找到包含至少N个点的最小"体积"凸包.这实际上可能不是一个好的方法,但几何上自然地考虑它可以捕获所有复制品可以从任何两组复制品同步中受益的想法.它们的大部分距离将缩小到由两个集合状态的合并创建的新对象的表面(而不是顶点!).
编辑 - 我想到的另一种方式来自我给出的例子.对于每个源DX,找到需要最少重传次数的N个副本的子集,以在该源上进行同步.这很容易.那么问题是你必须比较和修改这些D子集以使它们全部覆盖相同的N个副本.这不是一个完全形成的想法,因为每个维度DX中的最小N是全局空间中的局部最小值,可能在错误的区域中作为该维度的全局最优答案.无论如何,这是另一个想法.
EDIT2 - 回到Prim的+ Kruskal算法并忽略每个合并更新所有簇之间的相对距离,当我们发现大小等于或超过N的第一个簇时,最佳答案必须是某个子集那个集群？如果集群的大小等于N,那么我们就完成了.如果簇的大小超过N,那么我们可以做一些像计算簇的质心并选择N个最接近质心的复制品吗？这会产生最佳答案吗？这似乎仍然不正确,因为它没有考虑距离质心的各种距离的"方向性".也就是说,它不区分在D维空间中彼此接近的两个复制品(它应该支持),而不是相对于质心处于彼此"相反"方向的两个复制品.也许我们可以改为查看群集中副本的最小生成树,并以某种方式有效地修剪它以找到保持连接的最小权重子集？
任何想法或相关算法的指针将不胜感激!
J. *_*rth -1
您可以将您的环境表示为图表。之后，您可以使用最小生成树来连接环境中的所有节点，而无需重复连接。然后，通过最小生成树仅发送一条消息就可以到达环境中的所有节点。不需要重新传输消息。