Polystyrene: the Decentralized Data Shape That Never Dies
Polystyrene: the Decentralized Data Shape That Never Dies
复制标题
聚苯乙烯：永不消亡的去中心化数据形态
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
François Taïani
中科院分区：
文献类型：
--
作者：
S. Bouget;H. Kervadec;Anne;François Taïani
分散式拓扑构造协议沿着预定义的拓扑（例如，环面、环或超立方体）组织节点沿着。这样的拓扑结构已经被用在从路由和存储系统到订阅和事件传播的许多环境中。由于大多数拓扑假设节点的物理位置和它们在拓扑中的位置之间没有相关性，它们不能很好地处理灾难性故障，其中整个拓扑区域消失。当这种情况发生时，系统的整体形状通常会丢失。这在覆盖节点用于映射虚拟数据空间的应用中是非常成问题的，无论是用于路由、索引还是存储。在本文中，我们提出了一种新的分散的方法，保持拓扑结构的初始形状，即使一个大的（连续）部分拓扑失败。我们的方法依赖于物理节点和虚拟节点之间的动态解耦，从而实现快速重塑。例如，我们的结果表明，在50%的节点崩溃后，51，200个节点的环面仅用10轮就收敛回完整的环面。我们的协议是既简单又灵活，并提供了一种新的形式的集体生存能力，超越了目前的最先进的。
Decentralized topology construction protocols organize nodes along a predefined topology (e.g. a torus, ring, or hypercube). Such topologies have been used in many contexts ranging from routing and storage systems, to publish-subscribe and event dissemination. Since most topologies assume no correlation between the physical location of nodes and their positions in the topology, they do not handle catastrophic failures well, in which a whole region of the topology disappears. When this occurs, the overall shape of the system typically gets lost. This is highly problematic in applications in which overlay nodes are used to map a virtual data space, be it for routing, indexing or storage. In this paper, we propose a novel decentralized approach that maintains the initial shape of the topology even if a large (consecutive) portion of the topology fails. Our approach relies on the dynamic decoupling between physical nodes and virtual ones enabling a fast reshaping. For instance, our results show that a 51,200-node torus converges back to a full torus in only 10 rounds after 50% of the nodes have crashed. Our protocol is both simple and flexible and provides a novel form of collective survivability that goes beyond the current state of the art.