Document Open Access Logo

Specification and Implementation of Replicated List: The Jupiter Protocol Revisited

Authors Hengfeng Wei, Yu Huang, Jian Lu

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.12.pdf
  • Filesize: 1 MB
  • 16 pages

Document Identifiers

Author Details

Hengfeng Wei
  • State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China
Yu Huang
  • State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China
Jian Lu
  • State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China

Funding

This work is supported by the National 973 Program of China (No. 2015CB352202) and the National Natural Science Foundation of China (No. 61690204, 61702253).
  • Huang, Yu: Contact Author.

Cite As Get BibTex

Hengfeng Wei, Yu Huang, and Jian Lu. Specification and Implementation of Replicated List: The Jupiter Protocol Revisited. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.12

Abstract

The replicated list object is frequently used to model the core functionality of replicated collaborative text editing systems. Since 1989, the convergence property has been a common specification of a replicated list object. Recently, Attiya et al. proposed the strong/weak list specification and conjectured that the well-known Jupiter protocol satisfies the weak list specification. The major obstacle to proving this conjecture is the mismatch between the global property on all replica states prescribed by the specification and the local view each replica maintains in Jupiter using data structures like 1D buffer or 2D state space. To address this issue, we propose CJupiter (Compact Jupiter) based on a novel data structure called n-ary ordered state space for a replicated client/server system with n clients. At a high level, CJupiter maintains only a single n-ary ordered state space which encompasses exactly all states of each replica. We prove that CJupiter and Jupiter are equivalent and that CJupiter satisfies the weak list specification, thus solving the conjecture above.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Distributed computing methodologies
  • Software and its engineering → Correctness
  • Human-centered computing → Collaborative and social computing systems and tools
Keywords
  • Collaborative text editing systems
  • Replicated list
  • Concurrency control
  • Strong/weak list specification
  • Operational transformation
  • Jupiter protocol

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Apache Wave. URL: https://incubator.apache.org/wave/.
  2. Google Docs. URL: https://docs.google.com.
  3. What’s different about the new Google Docs: Making collaboration fast. URL: https://drive.googleblog.com/2010/09/whats-different-about-new-google-docs.html.
  4. Apache Wave (incubating) Protocol Documentation (Release 0.4), August 22, 2015. Google Scholar
  5. Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang, and Marek Zawirski. Specification and complexity of collaborative text editing. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 259-268. ACM, 2016. Google Scholar
  6. Hagit Attiya, Faith Ellen, and Adam Morrison. Limitations of Highly-Available Eventually-Consistent Data Stores. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC '15, pages 385-394. ACM, 2015. Google Scholar
  7. Sebastian Burckhardt, Alexey Gotsman, Hongseok Yang, and Marek Zawirski. Replicated Data Types: Specification, Verification, Optimality. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '14, pages 271-284. ACM, 2014. Google Scholar
  8. C. A. Ellis and S. J. Gibbs. Concurrency Control in Groupware Systems. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, SIGMOD '89, pages 399-407. ACM, 1989. Google Scholar
  9. Abdessamad Imine, Michaël Rusinowitch, Gérald Oster, and Pascal Molli. Formal Design and Verification of Operational Transformation Algorithms for Copies Convergence. Theor. Comput. Sci., 351(2):167-183, February 2006. Google Scholar
  10. Leslie Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM, 21(7):558-565, July 1978. Google Scholar
  11. Bo Leuf and Ward Cunningham. The Wiki Way: Quick Collaboration on the Web. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2001. Google Scholar
  12. Rui Li, Du Li, and Chengzheng Sun. A Time Interval Based Consistency Control Algorithm for Interactive Groupware Applications. In Proceedings of the 10th International Conference on Parallel and Distributed Systems, ICPADS '04, pages 429-438, 2004. Google Scholar
  13. David A. Nichols, Pavel Curtis, Michael Dixon, and John Lamping. High-latency, Low-bandwidth Windowing in the Jupiter Collaboration System. In Proceedings of the 8th Annual ACM Symposium on User Interface and Software Technology, UIST '95, pages 111-120. ACM, 1995. Google Scholar
  14. Atul Prakash and Michael J. Knister. A Framework for Undoing Actions in Collaborative Systems. ACM Trans. Comput.-Hum. Interact., 1(4):295-330, December 1994. Google Scholar
  15. Matthias Ressel, Doris Nitsche-Ruhland, and Rul Gunzenhäuser. An Integrating, Transformation-oriented Approach to Concurrency Control and Undo in Group Editors. In Proceedings of the 1996 ACM Conference on Computer Supported Cooperative Work, CSCW '96, pages 288-297. ACM, 1996. Google Scholar
  16. Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee. Replicated Abstract Data Types: Building Blocks for Collaborative Applications. J. Parallel Distrib. Comput., 71(3):354-368, March 2011. Google Scholar
  17. Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-free Replicated Data Types. In Proceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS'11, pages 386-400. Springer-Verlag, 2011. Google Scholar
  18. Haifeng Shen and Chengzheng Sun. Flexible Notification for Collaborative Systems. In Proceedings of the 2002 ACM Conference on Computer Supported Cooperative Work, CSCW '02, pages 77-86. ACM, 2002. Google Scholar
  19. Chengzheng Sun. Undo As Concurrent Inverse in Group Editors. ACM Trans. Comput.-Hum. Interact., 9(4):309-361, December 2002. Google Scholar
  20. Chengzheng Sun and Clarence Ellis. Operational Transformation in Real-time Group Editors: Issues, Algorithms, and Achievements. In Proceedings of the 1998 ACM Conference on Computer Supported Cooperative Work, CSCW '98, pages 59-68. ACM, 1998. Google Scholar
  21. Chengzheng Sun, Xiaohua Jia, Yanchun Zhang, Yun Yang, and David Chen. Achieving Convergence, Causality Preservation, and Intention Preservation in Real-time Cooperative Editing Systems. ACM Trans. Comput.-Hum. Interact., 5(1):63-108, March 1998. Google Scholar
  22. Chengzheng Sun, Yi Xu, and Agustina Agustina. Exhaustive Search of Puzzles in Operational Transformation. In Proceedings of the 17th ACM Conference on Computer Supported Cooperative Work, CSCW '14, pages 519-529. ACM, 2014. Google Scholar
  23. David Sun and Chengzheng Sun. Context-Based Operational Transformation in Distributed Collaborative Editing Systems. IEEE Trans. Parallel Distrib. Syst., 20(10):1454-1470, October 2009. Google Scholar
  24. Nicolas Vidot, Michelle Cart, Jean Ferrié, and Maher Suleiman. Copies Convergence in a Distributed Real-time Collaborative Environment. In Proceedings of the 2000 ACM Conference on Computer Supported Cooperative Work, CSCW '00, pages 171-180. ACM, 2000. Google Scholar
  25. Hengfeng Wei, Yu Huang, and Jian Lu. Specification and Implementation of Replicated List: The Jupiter Protocol Revisited. CoRR, abs/1708.04754, 2017. Google Scholar
  26. Yi Xu, Chengzheng Sun, and Mo Li. Achieving Convergence in Operational Transformation: Conditions, Mechanisms and Systems. In Proceedings of the 17th ACM Conference on Computer Supported Cooperative Work, CSCW '14, pages 505-518. ACM, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact