License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2023.30
URN: urn:nbn:de:0030-drops-190245
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19024/
Go to the corresponding LIPIcs Volume Portal

Domínguez, Jesús ; Nanevski, Aleksandar

Visibility and Separability for a Declarative Linearizability Proof of the Timestamped Stack

pdf-format:
LIPIcs-CONCUR-2023-30.pdf (0.8 MB)

Abstract

Linearizability is a standard correctness criterion for concurrent algorithms, typically proved by establishing the algorithms' linearization points (LP). However, LPs often hinder abstraction, and for some algorithms such as the timestamped stack, it is unclear how to even identify their LPs. In this paper, we show how to develop declarative proofs of linearizability by foregoing LPs and instead employing axiomatization of so-called visibility relations. While visibility relations have been considered before for the timestamped stack, our study is the first to show how to derive the axiomatization systematically and intuitively from the sequential specification of the stack. In addition to the visibility relation, a novel separability relation emerges to generalize real-time precedence of procedure invocation. The visibility and separability relations have natural definitions for the timestamped stack, and enable a novel proof that reduces the algorithm to a simplified form where the timestamps are generated atomically.

BibTeX - Entry

@InProceedings{dominguez_et_al:LIPIcs.CONCUR.2023.30,
  author =	{Dom{\'\i}nguez, Jes\'{u}s and Nanevski, Aleksandar},
  title =	{{Visibility and Separability for a Declarative Linearizability Proof of the Timestamped Stack}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19024},
  URN =		{urn:nbn:de:0030-drops-190245},
  doi =		{10.4230/LIPIcs.CONCUR.2023.30},
  annote =	{Keywords: Linearizability, Visibility Relations, Timestamped Stack}
}

Keywords: Linearizability, Visibility Relations, Timestamped Stack
Collection: 34th International Conference on Concurrency Theory (CONCUR 2023)
Issue Date: 2023
Date of publication: 07.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI