Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 44 Issue 6, Nov. 1997

Contention in shared memory algorithms
Cynthia Dwork, Maurice Herlihy, Orli Waarts
Pages: 779-805
DOI: 10.1145/268999.269000
Most complexity measures for concurrent algorithms for asynchronous shared-memory architectures focus on process steps and memory consumption. In practice, however, performance of multiprocessor algorithms is heavily influenced by...

Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe
Pages: 806-825
DOI: 10.1145/268999.269002
In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner—a candidate who beats all other candidates in pairwise majority-rule...

Software reliability via run-time result-checking
Hal Wasserman, Manuel Blum
Pages: 826-849
DOI: 10.1145/268999.269003
We review the field of result-checking, discussing simple checkers and self-correctors. We argue that such checkers could profitably be incorporated in software as an aid to efficient debugging and enhanced reliability. We consider how to modify...

Compositional refinement of interactive systems
Manfred Broy
Pages: 850-891
DOI: 10.1145/268999.269004
We introduce a method to describe systems and their components by functional specification techniques. We define notions of interface and interaction refinement for interactive systems and their components. These notions of refinement allow us...

Author Index
Author Index
Page: 892
DOI: 10.1145/268999.269806