Skip to main content
Article
Byzantine Fault Tolerance for Collaborative Editing With Commutative Operations
2016 IEEE International Conference on Electro Information Technology (EIT)
  • Wenbing Zhao, Cleveland State University
  • Mamdouh Babi, Cleveland State University
  • William Yang
  • Xiong Luo
  • Yueqin Zhu, China Geological Survey
  • Jack Yang
  • Chaomin Luo, University of Detroit Mercy
  • Mary Yang
Document Type
Conference Proceeding
Publication Date
1-1-2016
Abstract

In this paper, we present a study on how to achieve Byzantine fault tolerance for collaborative editing systems with commutative operations. Recent research suggests that Conflict-free Replicated Data Types (CRDTs) can be used to construct collaborative editing systems where concurrent update operations are commutative. This new approach is shown to avoid the complex issue of conflict resolution for concurrent updates to a shared document. The shared document is often modeled as a linear text buffer where each basic element is assigned a globally unique and totally ordered identifier. The linear text buffer constructed this way would constitute as a CRDT, which would make concurrent update operations issued by different users commutative. State convergence at all users can be achieved automatically as long as the users could receive the same set of operations irrespective of their relative ordering. However, it is not straightforward to guarantee state convergence in the presence of malicious users and external adversaries. In this paper, we carefully analyze the threats towards this type of systems, and propose a lightweight solution to achieve Byzantine fault tolerance with low runtime overhead. We define a set of correctness properties for such systems and prove that the proposed Byzantine fault tolerance mechanisms guarantee these properties.

DOI
10.1109/EIT.2016.7535248
Citation Information
W. Zhao, M. Babi, William Yang, Xiong Luo, Yueqin Zhu, Jack Yang, Chaomin Luo and M. Yang, "Byzantine fault tolerance for collaborative editing with commutative operations," in 2016 IEEE International Conference on Electro Information Technology (EIT), 2016, pp. 246-251.