基于分布式编程语言的Chord协议和算法

文章编号:10019081(2013)07188505

doi:10.11772/j.issn.10019081.2013.07.1885

摘 要:

P2P分布式哈希表(DHT)协议本身简洁并且易于理解，但是命令式语言与分布式架构的不匹配使得实现和部署一个拥有全部功能的类似Chord的组件相当困难和复杂。针对这些问题，提出一种基于Bloom系统来设计P2P分布式哈希表协议的方法。首先，阐述了Bloom系统的分布式逻辑编程语言要素；其次，设计了一个最小分布式系统；再次，通过定义永久、暂时、异步通信和周期集合，设计了指表维护算法、后继列表算法以及维持稳定算法等，实现一个chord原型系统。实验结果证明，原型系统能完成Chord所有功能，并且与传统语言相比，代码量减少60%。分析表明最终的算法代码和分布式哈希表协议规范高度一致，不仅增强了代码的可读性和重用性，而且加深了对协议本身及其应用的理解。

关键词： P2P；分布式哈希表；逻辑编程；Chord；Bloom

中图分类号：TP311.133.1文献标志码:A

英文标题

Chord protocol and algorithm in distributed programming language



英文作者名

PENG Chengzhang, JIANG Zejun*, CAI Xiaobin, ZHANG Zhike

英文地址(

School of Computer Science, Northwestern Polytechnical University, Xian Shaanxi 710129, China英文摘要)

Abstract:

The PeertoPeer (P2P) Distributed Hash Table (DHT) protocol is concise, and can be understood easily, but implementing and deploying a component like Chord with all functions in practice is very difficult and complicated because of the mismatch between popular imperative language and distributed architecture. To resolve these problems, a P2P DHT protocol based on Bloom system was proposed. Firstly, the distributed logic programming languages key elements of Bloom system were expounded. Secondly, a minimal distributed system was designed. Thirdly, a Chord prototype system was implemented through defining persistent, transient, asynchronous communicating and periodic collections and designing several algorithms for finger table maintaining, successor listing, stabilization preseving and so on. The experimental results show that the prototype system can finish full functions of Chord, and compared to traditional languages, 60% of the code lines can be saved. The analysis indicates such a high degree of uniformity between final code of the algorithm and the DHT protocol specification makes it more readable and reusable, and helpful for further understanding the specific protocol and relative applications.

The PeertoPeer (P2P) distributed hash table protocol is concise, and can be understood easily, but implementing and deploying a component like Chord offering full functioned protocol in practice are very difficult and complicated because of the mismatch between popular imperative languages and distributed architectures. For resolving these problems, designing a P2P distributed hash table protocol based on Bloom system was proposed. Firstly, the distributed logic programming languages key elements of Bloom system was shown. Secondly, a minimal distributed system was designed. Thirdly, a Chord prototype system was implemented through defining persistent, transient, asynchronous communicating and periodic collections and designing several algorithms for finger table maintaining, successor lists, stabilization and so on. The experimental results show that the prototype system can finish full functions of Chord, and comparing to traditional languages, 60% of the code lines can be saved. The analysis indicates such high degree of uniformity between final codes for the algorithm and the distributed hash table protocol specification makes it more readable and reusable, and helpful for further understanding the specific protocols and relative applications.