Browsing by Author "Gopalakrishnan, G"

Now showing 1 - 2 of 2

Citation - WoS: 1
On the Decidability of Shared Memory Consistency Verification
(Ieee, 2005) Sezgin, A; Gopalakrishnan, G; 01. Atılım University
We view shared memories as structures which define relations over the set of programs and their executions. An implementation is modeled by a transducer where the relation it realizes is its language. This approach allows us to cast shared memory verification as language inclusion. We show that a specification can be approximated by an infinite hierarchy of finite-state transducers, called the memory model machines. Also, checking whether an execution is generated by a sequentially consistent memory is approached through a constraint satisfaction formulation. It is proved that if a memory implementation generates a non interleaved sequential and unambiguous execution, it necessarily generates one such execution of bounded size. Our paper summarizes the key results from the first author's dissertation, and may help a practitioner understand with clarity what "sequential consistency checking is undecidable" means.
On the Definition of Sequential Consistency
(Elsevier Science Bv, 2005) Sezgin, A; Gopalakrishnan, G; 01. Atılım University
The definition of sequential consistency is compared with an intuitive notion of correctness. That the definition is not strong enough is illustrated through a hypothetical memory system which is clearly incorrect, yet sequentially consistent. It is claimed that the reason for this is the absence of a relation between what actually happens (temporal order) and what seems to happen (logical order). A stronger version of sequential consistency is proposed. (c) 2005 Elsevier B.V. All rights reserved.