Composing ordered sequential consistency

被引：3
|
作者：
Lev-Ari, Kfir [1 ]
Bortnikov, Edward [2 ]
Keidar, Idit [1 ,2 ]
Shraer, Alexander
机构：
[1] Technion, Viterbi Dept Elect Engn, Haifa, Israel
[2] Yahoo Res, Haifa, Israel
来源：
INFORMATION PROCESSING LETTERS | 2017年 / 123卷
关键词：
Composability; Consistency; Distributed systems;
D O I：
10.1016/j.ipl.2017.03.004
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We define ordered sequential consistency (OSC), a generic criterion for concurrent objects. We show that OSC encompasses a range of criteria, from sequential consistency to linearizability, and captures the typical behavior of real-world coordination services, such as ZooKeeper. A straightforward composition of OSC objects is not necessarily OSC, e.g., a composition of sequentially consistent objects is not sequentially consistent. We define a global property we call leading ordered operations, and prove that it enables correct OSC composition. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码：47 / 50
页数：4
相关论文
共 50 条
  • [1] Composing Partially Ordered Monads
    Eklund, Patrik
    Helgesson, Robert
    RELATIONS AND KLEENE ALGEBRA IN COMPUTER SCIENCE, PROCEEDINGS, 2009, 5827 : 88 - 102
  • [2] STRUCTURAL CONSISTENCY, CONSISTENCY, AND SEQUENTIAL RATIONALITY
    KREPS, DM
    RAMEY, G
    ECONOMETRICA, 1987, 55 (06) : 1331 - 1348
  • [3] On the definition of sequential consistency
    Sezgin, A
    Gopalakrishnan, G
    INFORMATION PROCESSING LETTERS, 2005, 96 (06) : 193 - 196
  • [4] Regular Sequential Serializability and Regular Sequential Consistency
    Helt, Jeffrey
    Burke, Matthew
    Levy, Amit
    Lloyd, Wyatt
    PROCEEDINGS OF THE 28TH ACM SYMPOSIUM ON OPERATING SYSTEMS PRINCIPLES, SOSP 2021, 2021, : 163 - 179
  • [5] Automatable verification of sequential consistency
    Condon, AE
    Hu, AJ
    THEORY OF COMPUTING SYSTEMS, 2003, 36 (05) : 431 - 460
  • [6] Automatable Verification of Sequential Consistency
    Anne E. Condon
    Alan J. Hu
    Theory of Computing Systems, 2003, 36 : 431 - 460
  • [7] Sequential consistency as lazy linearizability
    Raynal, M
    EURASIA-ICT 2002: INFORMATION AND COMMUNICATION TECHNOLOGY, PROCEEDINGS, 2002, 2510 : 866 - 873
  • [8] CONSISTENCY OF SEQUENTIAL BINOMIAL ESTIMATES
    WOLFOWITZ, J
    ANNALS OF MATHEMATICAL STATISTICS, 1947, 18 (01): : 131 - 135
  • [9] SEQUENTIAL CONSISTENCY VERSUS LINEARIZABILITY
    ATTIYA, H
    WELCH, JL
    ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1994, 12 (02): : 91 - 122
  • [10] Fork sequential consistency is blocking
    Cachin, Christian
    Keidar, Idit
    Shraer, Alexander
    INFORMATION PROCESSING LETTERS, 2009, 109 (07) : 360 - 364
12345