Unifying Concurrent Objects and Distributed Tasks: Interval-Linearizability

作     者：Castaneda, Armando Rajsbaum, Sergio Raynal, Michel 

作者机构：Univ Nacl Autonoma Mexico Inst Matemat Mexico City DF Mexico Univ Rennes IRISA F-35042 Rennes France Hong Kong Polytech Univ Hong Kong Peoples R China Inst Matemat Ciudad De Mexico 04510 Mexico 

出 版 物：《JOURNAL OF THE ACM》 (J ACM)

年 卷 期：2018年第65卷第6期

页      面：45.1-45.42页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：PAPIIT-UNAM [IA102417, IN109917] LAISLA Mexico-France research grant Fondation Sciences Mathematiques de Paris Franco-German ANR project DISCMAT French ANR project DESCARTES [16-CE40-0023-03] INRIA-UNAM Equipe Associee LiDiCo (at the Limits of Distributed Computing) 

主　　题：Asynchronous system concurrency concurrent object distributed algorithm distributed task linearizability object composability non-determinism process crash sequential specification set-linearizability 

摘      要：Tasks and objects are two predominant ways of specifying distributed problems where processes should compute outputs based on their inputs. Roughly speaking, a task specifies, for each set of processes and each possible assignment of input values, their valid outputs. In contrast, an object is defined by a sequential specification. Also, an object can be invoked multiple times by each process, while a task is a one-shot problem. Each one requires its own implementation notion, stating when an execution satisfies the specification. For objects, linearizability is commonly used, while tasks implementation notions are less explored. The article introduces the notion of interval-sequential object, and the corresponding implementation notion of interval-linearizability, to encompass many problems that have no sequential specification as objects. It is shown that interval-sequential specifications are local, namely, one can consider interval-linearizable object implementations in isolation and compose them for free, without sacrificing interval-linearizability of the whole system. The article also introduces the notion of refined tasks and its corresponding satisfiability notion. In contrast to a task, a refined task can be invoked multiple times by each process. Also, objects that cannot be defined using tasks can be defined using refined tasks. In fact, a main result of the article is th at interval-sequential objects and refined tasks have the same expressive power and both are complete in the sense that they are able to specify any prefix-closed set of well-formed executions. Interval-linearizability and refined tasks go beyond unifying objects and tasks;they shed new light on both of them. On the one hand, interval-linearizability brings to task the following benefits: an explicit operational semantics, a more precise implementation notion, a notion of state, and a locality property. On the other hand, refined tasks open new possibilities of applying topological tech