EUVIMEDEUVIMED entdecken
Open Access · CC BY-ND 4.0

How Hard Is Weak-Memory Testing?

Soham Chakraborty, Shankara Narayanan Krishna, Umang Mathur, Andreas Pavlogiannis

Proceedings of the ACM on Programming Languages · 02.01.2024 · 8 (POPL) · 1978-2009

DOI: 10.1145/3632908 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.01.2024. Verfasst von Soham Chakraborty und 3 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 52 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Weak-memory models are standard formal specifications of concurrency across hardware, programming languages, and distributed systems. A fundamental computational problem is consistency testing : is the observed execution of a concurrent program in alignment with the specification of the underlying system? The problem has been studied extensively across Sequential Consistency (SC) and weak memory, and proven to be N P -complete when some aspect of the input (e.g., number of threads/memory locations) is unbounded. This unboundedness has left a natural question open: are there efficient parameterized algorithms for testing? The main contribution of this paper is a deep hardness result for consistency testing under many popular weak-memory models: the problem remains N P -complete even in its bounded setting, where candidate executions contain a bounded number of threads, memory locations, and values. This hardness spreads across several Release-Acquire variants of C11, a popular variant of its Relaxed fragment, popular Causal Consistency models, and the POWER architecture. To our knowledge, this is the first result that fully exposes the hardness of weak-memory testing and proves that the problem admits no parameterization under standard input parameters. It also yields a computational separation of these models from SC, x86-TSO, PSO, and Relaxed, for which bounded consistency testing is either known (for SC), or shown here (for the rest), to be in polynomial time.

Zitieren

APA

Chakraborty, S., Krishna, S. N., Mathur, U., & Pavlogiannis, A. (2024). How Hard Is Weak-Memory Testing?. Proceedings of the ACM on Programming Languages, 8(POPL), 1978-2009. https://doi.org/10.1145/3632908

Vancouver

Chakraborty S, Krishna SN, Mathur U, Pavlogiannis A. How Hard Is Weak-Memory Testing?. Proceedings of the ACM on Programming Languages. 2024;8(POPL):1978-2009. doi:10.1145/3632908

BibTeX
@article{Chakraborty2024,
  author = {Chakraborty, Soham and Krishna, Shankara Narayanan and Mathur, Umang and Pavlogiannis, Andreas},
  title = {How Hard Is Weak-Memory Testing?},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {POPL},
  pages = {1978--2009},
  doi = {10.1145/3632908}
}
Kostenlos starten →