DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2026.60

Brief Announcement: How Complex Can Sequential Consistency Be?

Authors: Dimitar Dimitrov

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)

Abstract

Sequential consistency (SC) is the prototypical correctness criterion for shared-memory systems. Deciding whether a finite execution history is SC is NP-complete [Gibbons and Korach, 1997]. In this brief announcement, we study the complexity of SC over infinite execution histories. It is known that SC is not among the safety properties [Glusman and Katz, 2001], which sit at the lowest level of the Borel hierarchy. We show that, under finite arrival, SC is in fact a liveness property. We further demonstrate that no deterministic transducer can compute sequential witnesses for all SC histories, nor can any infinite-state deterministic Büchi acceptor recognize SC. Finally, we establish that, under infinite arrival, SC for memories with unbounded registers and DCAS (double compare-and-swap) is 𝚺¹₁-complete.

Cite as

Dimitar Dimitrov. Brief Announcement: How Complex Can Sequential Consistency Be?. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 60:1-60:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dimitrov:LIPIcs.DISC.2026.60,
  author =	{Dimitrov, Dimitar},
  title =	{{Brief Announcement: How Complex Can Sequential Consistency Be?}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{60:1--60:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.60},
  URN =		{urn:nbn:de:0030-drops-281668},
  doi =		{10.4230/LIPIcs.DISC.2026.60},
  annote =	{Keywords: Distributed systems, Consistency, Complexity}
}

Search Results

Documents authored by Dimitrov, Dimitar

Brief Announcement: How Complex Can Sequential Consistency Be?

Abstract

Cite as

Thanks for your feedback!

Could not send message