LI Meian
College of Computer and Information Engineering, Inner Mongolia Agriculture University, Huhehaote, Inner Mongolia, 010018, China
Wang Buyu
College of Computer and Information Engineering, Inner Mongolia Agriculture University, Huhehaote, Inner Mongolia, 010018, China
Chao Lumeng
College of Computer and Information Engineering, Inner Mongolia Agriculture University, Huhehaote, Inner Mongolia, 010018, China
Liu Jiangping
College of Computer and Information Engineering, Inner Mongolia Agriculture University, Huhehaote, Inner Mongolia, 010018, China
ABSTRACT
An advanced symmetric distributed quorum generation algorithm based on limited recursion and backup nodes has been proposed in this paper to reduce the time complexity of a symmetric distributed quorum generation algorithm efficiently and ensure the quorum length not increased significantly. It reduced the time complexity through reducing the optional nodes at every recursion level significantly without increasing the quorum length and the space complexity significantly. Theoretical analysis shows that its quorum length is N1/2, its space complexity is O(N) and its time complexity is O(N1/2!). Experimental results show that this algorithm reduced the real time complexity 79% at least to the limited recursion quorum generation algorithm when 37≤N≤51.
PDF References
How to cite this article
LI Meian, Wang Buyu, Chao Lumeng and Liu Jiangping, 2013. Symmetric Distributed Quorum Generation Algorithm Based on Backup Nodes. Information Technology Journal, 12: 3781-3784.
DOI: 10.3923/itj.2013.3781.3784
URL: https://scialert.net/abstract/?doi=itj.2013.3781.3784
DOI: 10.3923/itj.2013.3781.3784
URL: https://scialert.net/abstract/?doi=itj.2013.3781.3784
REFERENCES
- Lamport, L., 1978. Time, clocks and the ordering of events in a distributed system. Commun. ACM., 21: 558-565.
CrossRefDirect Link - Li, M.A., L. Lin and Z.D. Chen, 2012. Distributed cyclic quorum generation algorithm based on binary plus one. Comput. Eng., 38: 59-61.
CrossRefDirect Link - Li, M.A., L. Lin and Z.D. Chen, 2012. Quorum generation algorithm of dynamic and multi-node initiation based on local recursion. J. Comput. Appl., 32: 606-608.
CrossRefDirect Link - Li, M.A., X.S. Liu and Z. Wang, 2005. A high performance distributed mutual exclusion algorithm based on cyclic coding. Acta Electronica Sinica, 33: 1397-1402.
Direct Link - Maekawa, M., 1985. An algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst., 3: 145-159.
CrossRef - Ricart, G. and A.K. Agrawala, 1981. An optimal algorithm for mutual exclusion in computer networks. Commun. ACM, 24: 9-17.
CrossRefDirect Link