Article

Verifying sequential consistency using vector clocks

Authors:

Harold W. Cain,

Mikko H. LipastiAuthors Info & Claims

SPAA '02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures

Pages 153 - 154

https://doi.org/10.1145/564870.564897

Published: 10 August 2002 Publication History

Get Access

Abstract

We present an algorithm for dynamically verifying that the execution of a multithreaded program is sequentially consistent. The algorithm uses a vector-timestamp logical time mechanism to construct and verify the acyclic nature of an execution's constraint graph.

References

[1]

T. Austin. "DIVA: A reliable substrate for deep submicron microarchitecture design." In Proc. of the 32nd Intl. Symp. on Microarchitecture, November 1999.

Digital Library

Google Scholar

[2]

A. Condon and A. J. Hu. "Automatable verification of se¿quential consistency." In 13th Symposium on Parallel Algorithms and Architectures, January 2001.

Digital Library

Google Scholar

[3]

M. Dubois and C. Scheurich. "Memory access dependen¿cies in shared-memory multiprocessors." IEEE Transac¿tions on Software Engineering, 16(6):660--674, 1990.

Digital Library

Google Scholar

[4]

P. B. Gibbons and E. Korach. "Testing shared memories." SIAM Journal on Computing, 26(4):1208--1244, 1997.

Digital Library

Google Scholar

[5]

A. Landin, E. Hagersten, and S. Haridi. "Race-free interconnection networks and multiprocessor consistency." In Proc. of the 18th Intl. Symp. on Comp. Architecture, 1991.

Digital Library

Google Scholar

Cited By

View all

Soueidi CFalcone Y(2023)Instrumentation for RV: From Basic Monitoring to Advanced Use CasesRuntime Verification10.1007/978-3-031-44267-4_23(403-427)Online publication date: 1-Oct-2023
https://doi.org/10.1007/978-3-031-44267-4_23
Soueidi CFalcone Y(2023)Sound Concurrent Traces for Online MonitoringModel Checking Software10.1007/978-3-031-32157-3_4(59-80)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-32157-3_4
Soueidi CEl-Hokayem AFalcone Y(2023)Opportunistic Monitoring of Multithreaded ProgramsFundamental Approaches to Software Engineering10.1007/978-3-031-30826-0_10(173-194)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30826-0_10
Show More Cited By

Index Terms

Verifying sequential consistency using vector clocks
1. Hardware
  1. Hardware test
    1. Memory test and repair

Recommendations

Efficient sequential consistency using conditional fences
PACT '10: Proceedings of the 19th international conference on Parallel architectures and compilation techniques

Among the various memory consistency models, the sequential consistency (SC) model, in which memory operations appear to take place in the order specified by the program, is the most intuitive and enables programmers to reason about their parallel ...
On verifying causal consistency
POPL '17

Causal consistency is one of the most adopted consistency criteria for distributed implementations of data structures. It ensures that operations are executed at all sites according to their causal precedence. We address the issue of verifying ...
Verifying strong eventual consistency in distributed systems

Data replication is used in distributed systems to maintain up-to-date copies of shared data across multiple computers in a network. However, despite decades of research, algorithms for achieving consistency in replicated systems are still poorly ...

Comments

Information & Contributors

Information

Published In

SPAA '02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures

August 2002

302 pages

ISBN:1581135297

DOI:10.1145/564870

Conference Chair:
Arnold Rosenberg
University of Massachusetts
,
Program Chair:
Bruce Maggs
Carnegie Mellon University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA02

Sponsor:

SPAA02: Fourteenth ACM Symposium on Parallelism in Algorithms and Architectures

August 10 - 13, 2002

Manitoba, Winnipeg, Canada

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
403
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Soueidi CFalcone Y(2023)Instrumentation for RV: From Basic Monitoring to Advanced Use CasesRuntime Verification10.1007/978-3-031-44267-4_23(403-427)Online publication date: 1-Oct-2023
https://doi.org/10.1007/978-3-031-44267-4_23
Soueidi CFalcone Y(2023)Sound Concurrent Traces for Online MonitoringModel Checking Software10.1007/978-3-031-32157-3_4(59-80)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-32157-3_4
Soueidi CEl-Hokayem AFalcone Y(2023)Opportunistic Monitoring of Multithreaded ProgramsFundamental Approaches to Software Engineering10.1007/978-3-031-30826-0_10(173-194)Online publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30826-0_10
Sorin DSorin D(2022)Error DetectionFault Tolerant Computer Architecture10.1007/978-3-031-01723-0_2(19-59)Online publication date: 5-Mar-2022
https://doi.org/10.1007/978-3-031-01723-0_2
Bui TChatterjee KGautam TPavlogiannis AToman V(2021)The reads-from equivalence for the TSO and PSO memory modelsProceedings of the ACM on Programming Languages10.1145/34855415:OOPSLA(1-30)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485541
Long YBagherzadeh MLin EUpadhyaya GRajan HFuentes LBatory DCzarnecki K(2016)On ordering problems in message passing softwareProceedings of the 15th International Conference on Modularity10.1145/2889443.2889444(54-65)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.1145/2889443.2889444
Zakeryfar MGrogono PDesai BAlmeida AMudur S(2013)Static analysis of concurrent programs by adapted vector clockProceedings of the International C* Conference on Computer Science and Software Engineering10.1145/2494444.2494476(58-66)Online publication date: 10-Jul-2013
https://dl.acm.org/doi/10.1145/2494444.2494476
Chen YLi LChen TLi LWang LFeng XHu W(2012)Program Regularization in Memory Consistency VerificationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2012.4423:11(2163-2174)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1109/TPDS.2012.44
Hu WChen YChen TQian CLi L(2012)Linear Time Memory Consistency VerificationIEEE Transactions on Computers10.1109/TC.2011.4161:4(502-516)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1109/TC.2011.41
Romanescu BLebeck ASorin DHoe JAdve V(2010)Specifying and dynamically verifying address translation-aware memory consistencyProceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems10.1145/1736020.1736057(323-334)Online publication date: 13-Mar-2010
https://dl.acm.org/doi/10.1145/1736020.1736057
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Efficient sequential consistency using conditional fences

On verifying causal consistency

Verifying strong eventual consistency in distributed systems

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Efficient sequential consistency using conditional fences

On verifying causal consistency

Verifying strong eventual consistency in distributed systems

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations