Byzantine Fault Tolerance for Collaborative Editing With Commutative Operations

Document Type

Conference Proceeding

Publication Date

2016

Publication Title

2016 IEEE International Conference on Electro Information Technology (EIT)

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.

Original Citation

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.

DOI

10.1109/EIT.2016.7535248

Link to Full Text

Share

COinS