Detecting Race Conditions in Parallel Programs that Use Semaphores

Simple item page
dc.creatorKlein, Philip N.
dc.creatorLu, Hsueh-I
dc.creatorNetzer, Rob H. B.
dc.date2002-08-03
dc.date.accessioned2026-07-07T03:18:46Z
dc.date.available2026-07-07T03:18:46Z
dc.descriptionWe address the problem of detecting race conditions in programs that use semaphores for synchronization. Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use many semaphores. We show in this paper that it remains NP-complete even if only two semaphores are used in the parallel programs. For the tractable case, i.e., using only one semaphore, we give two algorithms for detecting race conditions from the trace of executing a parallel program on p processors, where n semaphore operations are executed. The first algorithm determines in O(n) time whether a race condition exists between any two given operations. The second algorithm runs in O(np log n) time and outputs a compact representation from which one can determine in O(1) time whether a race condition exists between any two given operations. The second algorithm is near-optimal in that the running time is only O(log n) times the time required simply to write down the output.
dc.description24 pages, 12 figures, preliminary versions appeared in WADS 93 and ESA 96
dc.identifierhttps://arxiv.org/abs/cs/0208004
dc.identifierhttp://arxiv.org/abs/cs/0208004
dc.identifierAlgorithmica, 35(4):321-345, 2003
dc.identifierdoi:10.1007/s00453-002-1004-3
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31248
dc.subjectData Structures and Algorithms
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectF.2.2; G.2.2; D.1.3; D.4.1; E.1
dc.titleDetecting Race Conditions in Parallel Programs that Use Semaphores
dc.typetext

Files

Collections

arXiv