Race-condition detection in parallel computation with semaphores (extended abstract) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1996

AUTHORS

Philip N. Klein , Hsueh-I Lu , Robert H. B. Netzer

ABSTRACT

We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NP-complete to detect race conditions in programs that use polynomial number of semaphores [10]. We show in this paper that it remains NP-complete even if the programs are allowed to use only two semaphores, which settles the open question raised in [10]. The proof uses a technique that simulates a graph with any number of semaphores by a graph with only two semaphores.For the case of single semaphore, Lu et al. [8] give the previously only-known polynomial-time algorithm that runs in time O(n1.5p), where p is the number of processors and n is the total number of semaphore operations executed. Their algorithm, however, detects only a special class of race conditions. In this paper we cope with the general race-condition detection problem and give an O(np log n) -time algorithm.The output of our algorithm is a compact representation of size Θ(np), from which one can determine in constant time whether a race condition exists between two given operations. Our algorithm is near-optimal in that the time it takes is only O(log n) times the time required simply to write down the output. More... »

PAGES

445-459

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-61680-2_74

DOI

http://dx.doi.org/10.1007/3-540-61680-2_74

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1026455081


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept of Computer Science, Brown Univ., USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Dept of Computer Science, Brown Univ., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Klein", 
        "givenName": "Philip N.", 
        "id": "sg:person.0701364100.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701364100.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science & Information Engineering, National Chung-Cheng Univ., Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Dept of Computer Science, Brown Univ., USA", 
            "Dept. of Computer Science & Information Engineering, National Chung-Cheng Univ., Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept of Computer Science, Brown Univ., USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Dept of Computer Science, Brown Univ., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Netzer", 
        "givenName": "Robert H. B.", 
        "id": "sg:person.015172024763.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015172024763.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NP-complete to detect race conditions in programs that use polynomial number of semaphores [10]. We show in this paper that it remains NP-complete even if the programs are allowed to use only two semaphores, which settles the open question raised in [10]. The proof uses a technique that simulates a graph with any number of semaphores by a graph with only two semaphores.For the case of single semaphore, Lu et al. [8] give the previously only-known polynomial-time algorithm that runs in time O(n1.5p), where p is the number of processors and n is the total number of semaphore operations executed. Their algorithm, however, detects only a special class of race conditions. In this paper we cope with the general race-condition detection problem and give an O(np log n) -time algorithm.The output of our algorithm is a compact representation of size \u0398(np), from which one can determine in constant time whether a race condition exists between two given operations. Our algorithm is near-optimal in that the time it takes is only O(log n) times the time required simply to write down the output.", 
    "editor": [
      {
        "familyName": "Diaz", 
        "givenName": "Josep", 
        "type": "Person"
      }, 
      {
        "familyName": "Serna", 
        "givenName": "Maria", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-61680-2_74", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-61680-1", 
        "978-3-540-70667-0"
      ], 
      "name": "Algorithms \u2014 ESA '96", 
      "type": "Book"
    }, 
    "keywords": [
      "race conditions", 
      "number of processors", 
      "race condition detection", 
      "polynomial time algorithm", 
      "parallel programs", 
      "parallel computation", 
      "detection problem", 
      "compact representation", 
      "polynomial number", 
      "semaphores", 
      "Lu et al", 
      "time algorithm", 
      "semaphore operations", 
      "constant time", 
      "algorithm", 
      "graph", 
      "NPs", 
      "processors", 
      "special class", 
      "computation", 
      "operation", 
      "detects", 
      "synchronization", 
      "representation", 
      "open question", 
      "output", 
      "number", 
      "program", 
      "proof", 
      "time", 
      "detection", 
      "technique", 
      "class", 
      "one", 
      "et al", 
      "total number", 
      "questions", 
      "size", 
      "cases", 
      "conditions", 
      "al", 
      "problem", 
      "paper"
    ], 
    "name": "Race-condition detection in parallel computation with semaphores (extended abstract)", 
    "pagination": "445-459", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026455081"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-61680-2_74"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-61680-2_74", 
      "https://app.dimensions.ai/details/publication/pub.1026455081"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:40", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_189.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-61680-2_74"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-61680-2_74'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-61680-2_74'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-61680-2_74'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-61680-2_74'


 

This table displays all metadata directly associated to this object as RDF triples.

126 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-61680-2_74 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N634027f160ac496185a01f44569bacd3
4 schema:datePublished 1996
5 schema:datePublishedReg 1996-01-01
6 schema:description We address a problem arising in debugging parallel programs, detecting race conditions in programs using semaphores for synchronization. It is NP-complete to detect race conditions in programs that use polynomial number of semaphores [10]. We show in this paper that it remains NP-complete even if the programs are allowed to use only two semaphores, which settles the open question raised in [10]. The proof uses a technique that simulates a graph with any number of semaphores by a graph with only two semaphores.For the case of single semaphore, Lu et al. [8] give the previously only-known polynomial-time algorithm that runs in time O(n1.5p), where p is the number of processors and n is the total number of semaphore operations executed. Their algorithm, however, detects only a special class of race conditions. In this paper we cope with the general race-condition detection problem and give an O(np log n) -time algorithm.The output of our algorithm is a compact representation of size Θ(np), from which one can determine in constant time whether a race condition exists between two given operations. Our algorithm is near-optimal in that the time it takes is only O(log n) times the time required simply to write down the output.
7 schema:editor Nf80cfcb580fe4c1fa2b0ff5af3ab1e05
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N58633f171c044801aae7fcdce114adb4
12 schema:keywords Lu et al
13 NPs
14 al
15 algorithm
16 cases
17 class
18 compact representation
19 computation
20 conditions
21 constant time
22 detection
23 detection problem
24 detects
25 et al
26 graph
27 number
28 number of processors
29 one
30 open question
31 operation
32 output
33 paper
34 parallel computation
35 parallel programs
36 polynomial number
37 polynomial time algorithm
38 problem
39 processors
40 program
41 proof
42 questions
43 race condition detection
44 race conditions
45 representation
46 semaphore operations
47 semaphores
48 size
49 special class
50 synchronization
51 technique
52 time
53 time algorithm
54 total number
55 schema:name Race-condition detection in parallel computation with semaphores (extended abstract)
56 schema:pagination 445-459
57 schema:productId N085eb940346a497d840a86bd44717ea7
58 N09d9112cd6334e328c177b7536450e4e
59 schema:publisher N35e8b846273245e19b0ad5640f09fe9c
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026455081
61 https://doi.org/10.1007/3-540-61680-2_74
62 schema:sdDatePublished 2022-05-10T10:40
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N3f161b5300f04bb6a907a1f9676c2023
65 schema:url https://doi.org/10.1007/3-540-61680-2_74
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N085eb940346a497d840a86bd44717ea7 schema:name doi
70 schema:value 10.1007/3-540-61680-2_74
71 rdf:type schema:PropertyValue
72 N09d9112cd6334e328c177b7536450e4e schema:name dimensions_id
73 schema:value pub.1026455081
74 rdf:type schema:PropertyValue
75 N1babec2926c44cda9a6e9ff4da413da3 rdf:first sg:person.013345515575.46
76 rdf:rest N2b25f37d175040fd86955124c111965f
77 N271d1ae5b0af40a9b6f3164851396d8a schema:familyName Diaz
78 schema:givenName Josep
79 rdf:type schema:Person
80 N2b25f37d175040fd86955124c111965f rdf:first sg:person.015172024763.29
81 rdf:rest rdf:nil
82 N35e8b846273245e19b0ad5640f09fe9c schema:name Springer Nature
83 rdf:type schema:Organisation
84 N3f161b5300f04bb6a907a1f9676c2023 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 N4cf1e64a79264fe9bdd933fb9717e389 schema:familyName Serna
87 schema:givenName Maria
88 rdf:type schema:Person
89 N58633f171c044801aae7fcdce114adb4 schema:isbn 978-3-540-61680-1
90 978-3-540-70667-0
91 schema:name Algorithms — ESA '96
92 rdf:type schema:Book
93 N634027f160ac496185a01f44569bacd3 rdf:first sg:person.0701364100.14
94 rdf:rest N1babec2926c44cda9a6e9ff4da413da3
95 Nc8d24a3d2ac541dc9ae33031ccdf456e rdf:first N4cf1e64a79264fe9bdd933fb9717e389
96 rdf:rest rdf:nil
97 Nf80cfcb580fe4c1fa2b0ff5af3ab1e05 rdf:first N271d1ae5b0af40a9b6f3164851396d8a
98 rdf:rest Nc8d24a3d2ac541dc9ae33031ccdf456e
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computation Theory and Mathematics
104 rdf:type schema:DefinedTerm
105 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.412047.4
106 schema:familyName Lu
107 schema:givenName Hsueh-I
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
109 rdf:type schema:Person
110 sg:person.015172024763.29 schema:affiliation grid-institutes:grid.40263.33
111 schema:familyName Netzer
112 schema:givenName Robert H. B.
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015172024763.29
114 rdf:type schema:Person
115 sg:person.0701364100.14 schema:affiliation grid-institutes:grid.40263.33
116 schema:familyName Klein
117 schema:givenName Philip N.
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701364100.14
119 rdf:type schema:Person
120 grid-institutes:grid.40263.33 schema:alternateName Dept of Computer Science, Brown Univ., USA
121 schema:name Dept of Computer Science, Brown Univ., USA
122 rdf:type schema:Organization
123 grid-institutes:grid.412047.4 schema:alternateName Dept. of Computer Science & Information Engineering, National Chung-Cheng Univ., Taiwan
124 schema:name Dept of Computer Science, Brown Univ., USA
125 Dept. of Computer Science & Information Engineering, National Chung-Cheng Univ., Taiwan
126 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...