Publication

On the complexity of linearizability

Jad Hamza
2019
Journal Articles

Abstract

It was previously shown that the problem of verifying whether a finite concurrent system is linearizable can be done with an EXPSPACE complexity. However, the best known lower bound is PSPACE-hardness, and can be obtained using a reduction from control-state reachability to linearizability. In this paper, we close the complexity gap between the PSPACE lower bound and the EXPSPACE upper bound, and show that linearizability is EXPSPACE-complete.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

On the complexity of linearizability

Chat with Graph Search

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Inhalation of Microplastics—A Toxicological Complexity

A Comparative Analysis of Tools & Task Types for Measuring Computational Problem-Solving