Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Novel Approach to Efficiently Verify Sequential Consistency in Concurrent Programs
Univ Zakho, Dept Comp Sci, Zakho 42002, Iraq..
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems.ORCID iD: 0000-0001-6832-6611
Univ Zakho, Dept Comp Sci, Zakho 42002, Iraq.;Univ Zakho, Res Ctr, Semant Web Lab, Duhok 42002, Iraq..
2025 (English)In: Computers, E-ISSN 2073-431X, Vol. 14, no 3, article id 110Article in journal (Refereed) Published
Abstract [en]

Verifying sequential consistency (SC) in concurrent programs is computationally challenging due to the exponential growth of possible interleavings among read and write operations. Many of these interleavings produce identical outcomes, rendering exhaustive verification approaches inefficient and computationally expensive, especially as thread counts increase. To mitigate this challenge, this study introduces a novel approach that efficiently verifies SC by identifying a minimal subset of valid event orderings. The proposed method iteratively focuses on ordering write events and evaluates their compatibility with SC conditions, including program order, read-from (rf) relations, and SC semantics, thereby significantly reducing redundant computations. Corresponding read events are subsequently integrated according to program order once the validity of write events has been confirmed, enabling rapid identification of violations to SC criteria. Three algorithmic variants of this approach were developed and empirically evaluated. The final variant exhibited superior performance, achieving substantial improvements in execution time-ranging from 31.919% to 99.992%-compared to the optimal existing practical SC verification algorithms. Additionally, comparative experiments demonstrated that the proposed approach consistently outperforms other state-of-the-art methods in both efficiency and scalability.

Place, publisher, year, edition, pages
MDPI, 2025. Vol. 14, no 3, article id 110
Keywords [en]
sequential consistency, memory model, concurrent program, verification
National Category
Computer Sciences Computer Systems
Identifiers
URN: urn:nbn:se:uu:diva-554513DOI: 10.3390/computers14030110ISI: 001452003800001Scopus ID: 2-s2.0-105001328011OAI: oai:DiVA.org:uu-554513DiVA, id: diva2:1952072
Available from: 2025-04-14 Created: 2025-04-14 Last updated: 2025-04-14Bibliographically approved

Open Access in DiVA

fulltext(3307 kB)51 downloads
File information
File name FULLTEXT01.pdfFile size 3307 kBChecksum SHA-512
86d563bf3171c895ca8e9345b7054260930de4fdbe2afe217edcf9a3ee18025c4b900b483b1acd85cb5cfffe1adac786ed0d96b16891ab946331cb7e6185e0c9
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Abdulla, Parosh
By organisation
Computer SystemsDivision of Computer Systems
In the same journal
Computers
Computer SciencesComputer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 52 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 113 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf