Byzantine-resilient dual gossip membership management in clouds

Jong Beom Lim, Kwang Sik Chung, Hwa Min Lee, Kangbin Yim, Heonchang Yu

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


In this paper, we present an effective and efficient Byzantine-resilient dual membership management technique in cloud environments, in which nodes are prone to churn and the network topology is not fully connected. Our method is based on unstructured message communication model, namely a gossip protocol that is able to handle the dynamic behavior of nodes properly in the system. We argue that due to the presence of malicious Byzantine nodes, existing membership management mechanisms are not suitable for preserving uniformity of random sampling. Therefore, we propose a new membership management mechanism using gossip with social membership information. The proposed membership management scheme maintains not only neighbor nodes in a social graph, but also Byzantine nodes in a local data structure. The results show that our dual membership management effectively deals with Byzantine nodes, requiring only n≥ 2f + 1, where n is the number of nodes and f is the number of Byzantine nodes in the system. The message complexity is reduced from O(n2) to O(n) with our proposed algorithm compared to broadcast-based algorithms.

Original languageEnglish
Pages (from-to)3011-3022
Number of pages12
JournalSoft Computing
Issue number9
Publication statusPublished - 2018 May 1

Bibliographical note

Funding Information:
Acknowledgements This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2015R1D1A1A0106-1373).

Publisher Copyright:
© 2017, Springer-Verlag Berlin Heidelberg.


  • Byzantine fault tolerance
  • Cloud computing
  • Membership management
  • Social graph

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Geometry and Topology


Dive into the research topics of 'Byzantine-resilient dual gossip membership management in clouds'. Together they form a unique fingerprint.

Cite this