We use cookies to improve your experience with our site.

Jupiter协议的抽象与精化

Jupiter Made Abstract, and Then Refined

  • 摘要: 1、研究背景: 协同文本编辑系统允许多用户共同编辑一个共享文档。为了保证系统的高可用性,该类系统通常会将文档的多个副本存放在不同的节点上。为了降低访问延迟,用户将请求提交到本地节点,本地节点立即处理该请求并返回给用户,更新操作以异步的方式传播到其它节点。我们可以将文档建模为列表。因此,协同文本编辑系统需要实现复制列表数据类型。在客户端/服务器端模型下,Jupiter协议是实现复制列表数据类型的经典协议。目前,研究人员已经开发出多种Jupiter协议的变体,比如Wei等人提出的CJupiter、Xu等人提出的XJupiter以及Attiya等人提出的AJupiter。它们都使用了难于理解的操作转换技术。并且,由于使用了不同的数据结构,它们之间的关系也模糊不清。
    2、研究目的: 我们希望能系统地研究这些Jupiter协议变体。一方面,我们研究它们的共性,为深入理解Jupiter协议族提供框架。另一方面,我们研究它们之间的关系。
    3、研究方法: 为了严格刻画Jupiter协议族以及它们之间的关系,我们采用了形式化方法。具体地讲,我们使用形式化规约语言TLA+、模型检验工具TLC以及精化技术。
    4、研究结果: 我们首先提出了Jupiter协议族需要解决的与操作转换相关的核心问题,然后给出了一个通用且抽象的协议AbsJupiter。该协议不依赖于具体的数据协议。接着,我们建立了从AbsJupiter到CJupiter、从CJupiter到XJupiter以及从XJupiter到AJupiter的精化关系。此外,我们使用形式化规约语言TLA+描述了这些Jupiter协议变体,并使用TLC模型检验工具验证了它们的正确性以及精化关系的正确性。
    5、研究结论: 我们使用形式化方法描述并验证了经典Jupiter协议族的正确性以及它们之间的精化关系。这为验证真实系统中的真实协议提供了重要的案例与经验。我们希望能使用形式化方法继续研究P2P系统中的Jupiter协议变体。

     

    Abstract: Collaborative text editing systems allow multiple users to concurrently edit the same document, which can be modeled by a replicated list object. In the literature, there is a family of operational transformation (OT)-based Jupiter protocols for replicated lists, including AJupiter, XJupiter, and CJupiter. They are hard to understand due to the subtle OT technique, and little work has been done on formal verification of complete Jupiter protocols. Worse still, they use quite different data structures. It is unclear about how they are related to each other, and it would be laborious to verify each Jupiter protocol separately. In this work, we make contributions towards a better understanding of Jupiter protocols and the relation among them. We first identify the key OT issue in Jupiter and present a generic solution. We summarize several techniques for carrying out the solution, including the data structures to maintain OT results and to guide OTs. Then, we propose an implementation-independent AbsJupiter protocol. Finally, we establish the (data) refinement relation among these Jupiter protocols (AbsJupiter included). We also formally specify and verify the family of Jupiter protocols and the refinement relation among them using TLA+ (TLA stands for “Temporal Logic of Actions”) and the TLC model checker. To our knowledge, this is the first work to formally specify and verify a family of OT-based Jupiter protocols and the refinement relation among them. It would be helpful to promote a rigorous study of OT-based protocols.

     

/

返回文章
返回