Scalable and leaderless Byzantine consensus in cloud computing environments

Jongbeom Lim, Taeweon Suh, Joonmin Gil, Heonchang Yu

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


Traditional Byzantine consensus in distributed systems requires n ≥ 3f + 1, where n is the number of nodes. In this paper, we present a scalable and leaderless Byzantine consensus implementation based on gossip, requiring only n ≥ 2f + 1 nodes. Unlike conventional distributed systems, the network topology of cloud computing systems is often not fully connected, but loosely coupled and layered. Hence, we revisit the Byzantine consensus problem in cloud computing environments, in which each node maintains some number of neighbors, called local view. The message complexity of our Byzantine consensus scheme is O(n), instead of O(n2). Experimental results and correctness proof show that our Byzantine consensus scheme can solve the Byzantine consensus problem safely in a scalable way without a bottleneck and a leader in cloud computing environments.

Original languageEnglish
Pages (from-to)19-34
Number of pages16
JournalInformation Systems Frontiers
Issue number1
Publication statusPublished - 2014 Mar

Bibliographical note

Funding Information:
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST) (No. 2013056346).


  • Byzantine fault tolerance
  • Cloud computing
  • Consensus
  • Gossip

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Scalable and leaderless Byzantine consensus in cloud computing environments'. Together they form a unique fingerprint.

Cite this