Back to search

University of British Columbia

Model checking sequential consistency and parameterized protocols

Abstract

dc:description

Perhaps the most difficult aspect of designing a shared memory multiprocessor is the hardware protocol that facilitates the sharing of memory by multiple processors; these protocols are thus a natural target for formal verification. In this thesis we consider several problems relevant to model checking these protocols. The ultimate specification of a protocol is the memory model. Our more theoretical contributions relate to the problem of model checking a protocol for the well-known memory model sequential consistency (SC). We define a restricted version of SC called decisive SC (DSC), which rules out pathologies admitted by SC, and explore the complexities of its verification problems. Our key results are that DSC of a single behavior is NP-complete, DSC of a protocol is PSPACE-hard, a bounded variant DSQ is decidable in EXPSPACE, and full SC remains undecidable even when we require protocol behaviors to be prefix-closed. Also, we show that SC in conjunction with the ubiquitous property data independence imply DSC, which is strong evidence that restricting attention to DSC will never preclude any real protocol. Our second area of contribution considers parameterized model checking (PMC) of protocols. Here the goal is algorithmic proof over all of the infinite configurations of a protocol family parameterized by one or more quantities. We develop a technique to automatically abstract a family parameterized by the number of addresses and the number of data values, such that (a subset of) SC of the abstraction implies that of the family. We apply this method successfully to two nontrivial protocols, and suggest user-assisted solutions if the abstraction blows up or is too coarse for successful verification. We also contribute an approach for sound and complete processor-PMC of state assertions. The approach uses BDD-based symbolic model checking, and harnesses the theory of well-structured transition systems (WSTS). WSTS disallow conjunctive guards, which are found in many protocols. To extend applicability, we provide an automatic reduction for systems with conjunctive guards. Experiments show the efficacy of our conjunctive guard reduction, and that our approach scales better with the local state of each processor when compared with the classical WSTS algorithm.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bingham, Jesse

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/17340

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Bingham, Jesse. Model checking sequential consistency and parameterized protocols. doctoral thesis, University of British Columbia, 2005. http://hdl.handle.net/2429/17340