While a lot of research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures. Considering crashing peers in peer-to-peer networks, it should not be taken for granted that a distributed data structure remains intact. In this work, we present a self-stabilizing protocol for a distributed data structure called the hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The data structure has a wide area of applications including string matching problems while offering low overhead and efficient operations when embedded on top of a distributed hash table. Especially, longest prefix matching for x can be done in O(log |x|) hash table read accesses. We show how to maintain the structure in a self-stabilizing way. Our protocol assures low overhead in a legal state and a total (asymptotically optimal) memory demand of Θ(d) bits, where d is the number of bits needed for storing all keys.
展开▼
机译：尽管有关分布式计算的许多研究都涵盖了用于自稳定计算和拓扑的解决方案，但有关分布式数据结构的自稳定的工作却很少。考虑到对等网络中崩溃的对等节点，不应认为分布式数据结构保持完整是理所当然的。在这项工作中，我们提出了一种称为散列的Patricia Trie（Kniesburges和Scheideler WALCOM'11）的分布式数据结构的自稳定协议，该协议能够对一组键进行有效的前缀搜索。数据结构具有广泛的应用领域，其中包括字符串匹配问题，同时嵌入在分布式哈希表的顶部时，提供了较低的开销和高效的操作。特别是，可以在O（log | x |）哈希表读取访问中完成x的最长前缀匹配。我们展示了如何以自我稳定的方式维持结构。我们的协议确保了在合法状态下的低开销以及Θ（d）位的总（渐近最佳）存储需求，其中d是存储所有密钥所需的位数。
展开▼
