An Effective Method for Determining Consensus in Large Collectives

Dai Tho Dang1, 2, Thanh Ngo Nguyen3 and Dosam Hwang1

  1. Department of Computer Engineering
    Yeungnam University, Gyeongsan 38541, Republic of Korea
    daithodang@ynu.ac.kr, dshwang@yu.ac.kr
  2. Vietnam - Korea University of Information and Communication Technology,
    The University of Danang, Danang, Vietnam
    ddtho@vku.udn.vn
  3. Department of Applied Informatics, Faculty of Computer Science and Management
    Wrocław University of Science and Technology, 50-370 Wrocław, Poland
    thanh-ngo.nguyen@pwr.edu.pl

Abstract

Nowadays, using the consensus of collectives for solving problems plays an essential role in our lives. The rapid development of information technology has facilitated the collection of distributed knowledge from autonomous sources to find solutions to problems. Consequently, the size of collectives has increased rapidly. Determining consensus for a large collective is very time-consuming and expensive. Thus, this study proposes a vertical partition method (VPM) to find consensus in large collectives. In the VPM, the primary collective is first vertically partitioned into small parts. Then, a consensus-based algorithm is used to determine the consensus for each smaller part. Finally, the consensus of the collective is determined based on the consensuses of the smaller parts. The study demonstrates, both theoretically and experimentally, that the computational complexity of the VPM is lower than 57.1% that of the basic consensus method. This ratio reduces quickly if the number of smaller parts reduces.

Key words

large collective, consensus, algorithm, computational complexity

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS210314062D

How to cite

Dang, D. T., Nguyen, T. N., Hwang, D.: An Effective Method for Determining Consensus in Large Collectives. Computer Science and Information Systems, https://doi.org/10.2298/CSIS210314062D