少数决：更安全的分布式一致性算法选举机制

doi:10.3778/j.issn.1673-9418.1912052

计算机科学与探索 ›› 2020, Vol. 14 ›› Issue (10): 1693-1701.DOI: 10.3778/j.issn.1673-9418.1912052

少数决：更安全的分布式一致性算法选举机制

李彬，姜建国

1. 北京交通大学计算机与信息技术学院，北京 100044
2. 国家保密科技测评中心，北京 100044
3. 中国科学院信息工程研究所，北京 100093

出版日期:2020-10-01 发布日期:2020-10-12

Minority Decision: More Secure Voting Mechanism for Distributed Consistency Algorithm

LI Bin, JIANG Jianguo

1. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China
2. National Secrecy Science and Technology Evaluation Center, Beijing 100044, China
3. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Online:2020-10-01 Published:2020-10-12

摘要/Abstract

摘要：

目前应用于分布式系统中的基于选举的分布式一致性算法（类Paxos算法），都是采用得到50%以上选票者当选Leader的方式进行选举。此种选举机制类似现实生活中的选举，存在因控制投票而丧失系统去中心化的安全隐患。而去中心化是分布式系统的重要安全属性，可以避免系统因某个特殊节点故障而整体瘫痪。为此，提出了一种新的Leader选举机制——少数决，即通过逐步淘汰选择一致的多数者的方式选出Leader。此种选举机制可以有效降低绝对控票攻击的可能性，提高Leader选举的随机性，进而保证整个系统去中心化。通过理论分析和实验结果进一步验证了此种选举机制对比传统的多数决选举机制，在没有明显降低选举时间的基础上，具有更好的安全性。

关键词: 一致性算法, 选举机制, 少数决, 去中心化, 安全性

Abstract:

At present, the election based distributed consistency algorithm (Paxos like algorithm) applied in distri-buted system is elected by more than 50% of the voters. This kind of election mechanism is similar to the election in real life, and there is a potential risk of losing systematic decentralization due to the control of voting. Decen-tralization is an important security attribute of the distributed system, which can avoid the overall failure of the system due to the failure of a particular node. For this reason, this paper proposes a new leader election mechanism,minority decision, which selects leaders by phasing out the same majority. This kind of election mechanism can effectively reduce the possibility of absolute vote control attack, improve the randomness of leader election, and then ensure the decentralization of the whole system. Through theoretical analysis and experimental results, it is verified that this kind of election mechanism has better security than the traditional majority election mechanism without significantly reducing the election time.

Key words: consistency algorithm, election mechanism, minority decision, decentralization, security

李彬，姜建国. 少数决：更安全的分布式一致性算法选举机制[J]. 计算机科学与探索, 2020, 14(10): 1693-1701.

LI Bin, JIANG Jianguo. Minority Decision: More Secure Voting Mechanism for Distributed Consistency Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1693-1701.

参考文献

[1] Lamport L. Paxos made simple[J]. ACM SIGACT News, 2001, 32(4): 18-25.
[2] Chandra T, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, Portland, Aug 12-15, 2007. New York: ACM, 2007: 398-407.
[3] Ongaro D, Ousterhout J. In search of an understandable con-sensus algorithm[C]//Proceedings of the 2014 USENIX Con-ference on USENIX Annual Technical Conference, Phila-delphia,?Jun 19-20,?2014. Berkeley: USENIX Association, 2014: 305-320.
[4] Hunt P, Konar M, Junqueira F P, et al. ZooKeeper: wait-free coordination for internet-scale systems[C]//Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, Jun 23-25, 2010. Berkeley: USENIX Associa-tion, 2010: 145-158.
[5] Renesse R, Schiper N, Schneider F. Vive la différence: paxos vs viewstamped replication vs. zab[J]. IEEE Transactions on Dependable and Secure Computing, 2015, 12(4): 472-484.
[6] Zhu Y C. The advantages of raft and Paxos algorithms and the differences of their application scenarios[EB/OL]. [2019- 10-09]. https://www.zhihu.com/question/36648084.朱一聪. Raft与Paxos算法的各自优势及使用场景差异[EB/OL]. [2019-10-09]. https://www.zhihu.com/question/ 36648084.
[7] Lamport L, Shostak R, Pease M. The Byzantine generals pro-blem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.
[8] Kaitani S. Liar game[M]. Tokyo: Young Jump, 2005.
[9] Challet D, Zhang Y C. On the minority game: analytical and numerical studies[J]. Physica A, 1998, 256(3): 514-532.
[10] Fragouli C, Soljanin E. Decentralized network coding[C]//Proceedings of the 2004 IEEE Information Theory Work-shop, San Antonio, Oct 24-29, 2004. Piscataway: IEEE, 2004: 310-314.
[11] Herbert I W. Classical probability[M]. New York: John Wiley & Sons, Inc., 2002.
[12] Jacob M, Andersson S. The Gauss distribution function[J]. Nature of Mathematics & the Mathematics of Nature, 1998:147-190.
[13] Gelman A. Prior distribution[M]//Encyclopedia of Environ-metrics. New York: John Wiley & Sons, Inc., 2006.
[14] Bishop C. Pattern recognition and machine learning (infor-mation science and statistics)[M]. Berlin, Heidelberg: Sprin-ger, 2006.
[15] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms[M]. 3rd ed. Cambridge: MIT Press, 2009.
[16] Kamvar S D, Schlosser M T, Garcia-Molina H. The eigentrust algorithm for reputation management in P2P networks[C]//Proceedings of the 12th International World Wide Web Con-ference, Budapest, May 20-24, 2003. New York: ACM, 2003: 640-651.
[17] Li X, Ling L. PeerTrust: supporting reputation-based trust for peer-to-peer electronic communities[J]. IEEE Transac-tions on Knowledge and Data Engineering, 2004, 16(7): 843-857.
[18] Chen L, Huang S C, Xu K H. Improved Raft consistency algorithm[J]. Journal of Jiangsu University of Science and Technology (Natural Science Edition), 2018, 32(4): 559-563.陈陆, 黄树成, 徐克辉. 改进的Raft一致性算法及其研究[J]. 江苏科技大学学报(自然科学版), 2018, 32(4): 559-563.

少数决：更安全的分布式一致性算法选举机制

Minority Decision: More Secure Voting Mechanism for Distributed Consistency Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	张维珺，胡军，李宛倩，陈朔，石梦烨，唐红英. 安全关键系统需求形式化建模分析实例研究[J]. 计算机科学与探索, 2019, 13(8): 1295-1306.
[2]	李建民，俞惠芳，赵晨. UC安全的自认证盲签密协议[J]. 计算机科学与探索, 2017, 11(6): 932-940.
[3]	仵志鹏，胡军，陈松，石娇洁. 面向AltaRica模型的嵌入式系统安全性验证方法[J]. 计算机科学与探索, 2017, 11(1): 24-36.
[4]	张贵，张育平，陈海燕 . 面向适航认证的IMA架构安全性评估方法[J]. 计算机科学与探索, 2016, 10(8): 1063-1071.
[5]	鲍秋霜，张晋津. 直觉主义计算树逻辑中的安全性和活性[J]. 计算机科学与探索, 2016, 10(2): 163-172.
[6]	杜长霄，李晓红，石红，冯志勇. J2EE应用软件的架构安全评估方法[J]. 计算机科学与探索, 2014, 8(5): 572-581.
[7]	袁崇义1，2 ，赵文1，2，3 ，高昕1，2 ，黄雨1，2，3+ . O-表达式的性质定义与规范[J]. 计算机科学与探索, 2010, 4(1): 20-28.