论文标题
容忍分布式目录
Fault-Tolerant Distributed Directories
论文作者
论文摘要
分布式目录是图$ g $上的覆盖数据结构，有助于访问共享令牌$ t $。该目录支持三个操作：发布，宣布令牌，查找，以阅读令牌的内容并移动，以获取对令牌的独家更新访问权限。该目录是使用弱或强簇建立在图的层次分区上的。主要机制是维护目录路径，该目录路径始于层次结构中的根节点，并指向令牌的当前所有者。在文献中，有基于层次图结构的已知目录算法，但它们都没有考虑故障。给定层次分区，我们考虑$ f $ edge失败对分布式目录的功能和性能的影响。边缘故障可能会导致将簇分为最多$ f+1 $连接的组件，并增加层次结构中的级别数量。为了在故障后恢复分层分区，我们将群集及其连接的组件中的跨越树保持。如果$ g $保持连接，我们表明目录路径的每个级别仅通过一个因子$ f $扩张。我们还表明，对于消息复杂性，在最坏情况下，发布和查找操作的性能会受到最坏的因素$ f $的影响。移动操作的消息复杂性增加了$ f $ factor和层次结构中其他层的数量。
A distributed directory is an overlay data structure on a graph $G$ that helps to access a shared token $t$. The directory supports three operations: publish, to announce the token, lookup, to read the contents of the token, and move, to get exclusive update access to the token. The directory is built upon a hierarchical partition of the graph using either weak or strong clusters. The main mechanism is the maintenance of a directory path that starts at the root node in the hierarchy and points to the current owner of the token. In the literature, there are known directory algorithms based on hierarchical graph structures, but none of them have considered failures. Given a hierarchical partition, we consider the impact of $f$ edge failures on the functionality and performance of the distributed directory. The edge failures may result in the splitting of clusters into up to $f+1$ connected components and an increase in the number of levels in the hierarchy. To recover the hierarchical partition after failures, we maintain spanning trees in the clusters and their connected components. If $G$ remains connected, we show that each level of the directory path is dilated by only a factor $f$. We also show that the performance of the publish and lookup operations is affected in the worst case by a factor $f$ with respect to the message complexity. The message complexity of the move operation increases by an $f$ factor and the number of additional layers in the hierarchy.
