|
 ABSTRACT
The problem of concurrent accesses to registers by asynchronous components is considered. A set of axioms about the values in a register during concurrent accesses is proposed. It is shown that if these axioms are met by a register, then concurrent accesses to it may be viewed as nonconcurrent, thus making it possible to analyze asynchronous algorithms without elaborate timing analysis of operations. These axioms are shown, in a certain sense, to be the weakest. Motivation for this work came from analyzing low-level hardware components in a VLSI chip which concurrently accesses a flip-flop.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
CHANEY, W., AND MOLNAR, C. Anomalous behavior of synchronizer and arbiter circuits. IEEE Trans. Comput. (Apr. 1973), 421-422.
|
 |
2
|
|
| |
3
|
|
| |
4
|
LAMPORT, L. A theorem on multiprocess algorithms. Tech. Rep. CA-7503-2011, Massachusetts Computer Associates, Mar. 1975.
|
| |
5
|
MARINO, L.P. General theory of metastable operation. IEEE Trans. Comput. C-30, 2 (Feb. 1981).
|
| |
6
|
MILLS, H. D., AND LOUNSBERY, J.M. Combinatorial analyses of process synchronization. IBM, FSD (internal memo), Aug. 1983.
|
| |
7
|
OWlCKI, S., AND GRIES, D. An axiomatic proof technique for parallel programs. Acta In{. 6, 4 (1976), 319-340.
|
| |
8
|
S^UNDERS, J.M. Engineering description of a flip-flop reader and writer. IBM, FSD (internal memo), Jan. 1984.
|
| |
9
|
|
| |
10
|
WANN, D., AND FRANKLIN, M. Asynchronous and clocked control structures for VLSI--based interconnection networks. IEEE Trans. Comput. C-32, 3 (Mar. 1983), 264-293.
|
CITED BY 27
|
|
|
|
|
Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada
|
|
|
|
|
|
Divyakant Agrawal , Manhoi Choy , Hong Va Leong , Ambuj K. Singh, Mixed consistency: a model for parallel programming (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mustaque Ahamad , Rida A. Bazzi , Ranjit John , Prince Kohli , Gil Neiger, The power of processor consistency, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 30-July 02, 1993, Velen, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993
|
|
|
Ambuj K. Singh , James H. Anderson , Mohamed G. Gouda, The elusive atomic register revisited, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.206-221, August 10-12, 1987, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ernesto Jiménez , Antonio Fernández , Vicent Cholvi, A parametrized algorithm that implements sequential, causal, and cache memory consistencies, Journal of Systems and Software, v.81 n.1, p.120-131, January, 2008
|
REVIEW
"Mathai Joseph : Reviewer"
Guaranteeing atomicity of operations in a system with concurrent reading and
writing of variables (i.e., locations, registers, bits, or flip flops, depending
on one's level of interest) is a problem that is usually solved by making use of
the at
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
B.3