Threshold graphs and synchronization protocols View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1996

AUTHORS

Rossella Petreschi , Andrea Sterbini

ABSTRACT

This paper is a survey on the synchronization of a system of cooperating processes, when the mutual exclusion graph model and the semaphores are used. Threshold graphs and PVchunk semaphores are explained. Matroidal and matrogenic graphs are presented and their synchronization with a constant number of semaphores for each process are pointed out. Threshold dimension of a graph is explained and a sketched proof of its NP-completeness for k≥3 and of the polynomiality for k=2 is provided. The interest in characterizing new classes of graphs not 2-threshold, but synchronizable with a constant number of semaphores, is shown. More... »

PAGES

378-395

References to SciGraph publications

  • 1968. Cooperating Sequential Processes in THE ORIGIN OF CONCURRENT PROGRAMMING
  • 1982-06. Arbitration without common modifiable variables in ACTA INFORMATICA
  • Book

    TITLE

    Combinatorics and Computer Science

    ISBN

    978-3-540-61576-7
    978-3-540-70627-4

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-61576-8_97

    DOI

    http://dx.doi.org/10.1007/3-540-61576-8_97

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Department of Computer Science, University \u201dLa Sapienza\u201d, Via Salaria, 113-00198\u00a0Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "id": "sg:person.011402427702.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Department of Computer Science, University \u201dLa Sapienza\u201d, Via Salaria, 113-00198\u00a0Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sterbini", 
            "givenName": "Andrea", 
            "id": "sg:person.010065200346.76", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010065200346.76"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0012-365x(84)90023-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001514301"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/361179.361202", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005796851"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/355606.361895", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008903287"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(81)90106-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009445682"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/361082.361093", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014873305"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/359545.359563", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021135683"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/355592.365595", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022750712"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(81)90100-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023343635"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/34.4.345", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025603208"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(72)90035-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029535244"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/363162.363167", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029883865"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288966", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030785779", 
              "https://doi.org/10.1007/bf00288966"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288966", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030785779", 
              "https://doi.org/10.1007/bf00288966"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/358527.358537", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031322763"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-3472-0_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034198720", 
              "https://doi.org/10.1007/978-1-4757-3472-0_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(80)90141-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050997689"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/357195.357199", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053427371"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0206008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841347"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0218010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842109"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129054190000102", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062897546"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129054192000036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062897591"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1996", 
        "datePublishedReg": "1996-01-01", 
        "description": "This paper is a survey on the synchronization of a system of cooperating processes, when the mutual exclusion graph model and the semaphores are used. Threshold graphs and PVchunk semaphores are explained. Matroidal and matrogenic graphs are presented and their synchronization with a constant number of semaphores for each process are pointed out. Threshold dimension of a graph is explained and a sketched proof of its NP-completeness for k\u22653 and of the polynomiality for k=2 is provided. The interest in characterizing new classes of graphs not 2-threshold, but synchronizable with a constant number of semaphores, is shown.", 
        "editor": [
          {
            "familyName": "Deza", 
            "givenName": "Michel", 
            "type": "Person"
          }, 
          {
            "familyName": "Euler", 
            "givenName": "Reinhardt", 
            "type": "Person"
          }, 
          {
            "familyName": "Manoussakis", 
            "givenName": "Ioannis", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-61576-8_97", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-61576-7", 
            "978-3-540-70627-4"
          ], 
          "name": "Combinatorics and Computer Science", 
          "type": "Book"
        }, 
        "name": "Threshold graphs and synchronization protocols", 
        "pagination": "378-395", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-61576-8_97"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "4de6eee755f8c82c25dda070861f766882325d10f4b9eb6d573bb5349523699f"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1016349875"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-61576-8_97", 
          "https://app.dimensions.ai/details/publication/pub.1016349875"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T13:26", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8664_00000253.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-61576-8_97"
      }
    ]
     

    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-61576-8_97'

    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-61576-8_97'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-61576-8_97'

    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-61576-8_97'


     

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

    144 TRIPLES      23 PREDICATES      47 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-61576-8_97 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N4ced99cec35d4962a454ef7000fed61e
    4 schema:citation sg:pub.10.1007/978-1-4757-3472-0_2
    5 sg:pub.10.1007/bf00288966
    6 https://doi.org/10.1016/0012-365x(84)90023-2
    7 https://doi.org/10.1016/0020-0190(72)90035-x
    8 https://doi.org/10.1016/0020-0190(80)90141-6
    9 https://doi.org/10.1016/0020-0190(81)90100-9
    10 https://doi.org/10.1016/0020-0190(81)90106-x
    11 https://doi.org/10.1093/comjnl/34.4.345
    12 https://doi.org/10.1137/0206008
    13 https://doi.org/10.1137/0218010
    14 https://doi.org/10.1142/s0129054190000102
    15 https://doi.org/10.1142/s0129054192000036
    16 https://doi.org/10.1145/355592.365595
    17 https://doi.org/10.1145/355606.361895
    18 https://doi.org/10.1145/357195.357199
    19 https://doi.org/10.1145/358527.358537
    20 https://doi.org/10.1145/359545.359563
    21 https://doi.org/10.1145/361082.361093
    22 https://doi.org/10.1145/361179.361202
    23 https://doi.org/10.1145/363162.363167
    24 schema:datePublished 1996
    25 schema:datePublishedReg 1996-01-01
    26 schema:description This paper is a survey on the synchronization of a system of cooperating processes, when the mutual exclusion graph model and the semaphores are used. Threshold graphs and PVchunk semaphores are explained. Matroidal and matrogenic graphs are presented and their synchronization with a constant number of semaphores for each process are pointed out. Threshold dimension of a graph is explained and a sketched proof of its NP-completeness for k≥3 and of the polynomiality for k=2 is provided. The interest in characterizing new classes of graphs not 2-threshold, but synchronizable with a constant number of semaphores, is shown.
    27 schema:editor Nbeb02a6c38a04155bfa8ff6c99befa2e
    28 schema:genre chapter
    29 schema:inLanguage en
    30 schema:isAccessibleForFree false
    31 schema:isPartOf Nbb23260181c445239766aecff0562d7a
    32 schema:name Threshold graphs and synchronization protocols
    33 schema:pagination 378-395
    34 schema:productId N46afe6d6a12443f7b5079beea1069838
    35 N5e48dc30346d46d7a2f89f1a6bd8faeb
    36 Na4287b8c8eb64021a32bcfbf8a1ffd79
    37 schema:publisher N60acce9a64f142f7a4ae12c4ebae0894
    38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016349875
    39 https://doi.org/10.1007/3-540-61576-8_97
    40 schema:sdDatePublished 2019-04-15T13:26
    41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    42 schema:sdPublisher Nbda9dd5fb0b54eda84ea6e03b557a274
    43 schema:url http://link.springer.com/10.1007/3-540-61576-8_97
    44 sgo:license sg:explorer/license/
    45 sgo:sdDataset chapters
    46 rdf:type schema:Chapter
    47 N3a1c90e9af724652b07f2c4a89cac416 schema:familyName Deza
    48 schema:givenName Michel
    49 rdf:type schema:Person
    50 N46afe6d6a12443f7b5079beea1069838 schema:name doi
    51 schema:value 10.1007/3-540-61576-8_97
    52 rdf:type schema:PropertyValue
    53 N4ced99cec35d4962a454ef7000fed61e rdf:first sg:person.011402427702.78
    54 rdf:rest N8c7044af04754cfe95918e1e46a972bb
    55 N5e48dc30346d46d7a2f89f1a6bd8faeb schema:name dimensions_id
    56 schema:value pub.1016349875
    57 rdf:type schema:PropertyValue
    58 N60acce9a64f142f7a4ae12c4ebae0894 schema:location Berlin, Heidelberg
    59 schema:name Springer Berlin Heidelberg
    60 rdf:type schema:Organisation
    61 N76e20fe53eca4c17bc7785e26ce87efa rdf:first Nb06d54bc4a344deca52853ba81d5add6
    62 rdf:rest Nc04e058e81fb4f1b9bf857e903441096
    63 N8c7044af04754cfe95918e1e46a972bb rdf:first sg:person.010065200346.76
    64 rdf:rest rdf:nil
    65 Na4287b8c8eb64021a32bcfbf8a1ffd79 schema:name readcube_id
    66 schema:value 4de6eee755f8c82c25dda070861f766882325d10f4b9eb6d573bb5349523699f
    67 rdf:type schema:PropertyValue
    68 Nb06d54bc4a344deca52853ba81d5add6 schema:familyName Euler
    69 schema:givenName Reinhardt
    70 rdf:type schema:Person
    71 Nbb23260181c445239766aecff0562d7a schema:isbn 978-3-540-61576-7
    72 978-3-540-70627-4
    73 schema:name Combinatorics and Computer Science
    74 rdf:type schema:Book
    75 Nbda9dd5fb0b54eda84ea6e03b557a274 schema:name Springer Nature - SN SciGraph project
    76 rdf:type schema:Organization
    77 Nbeb02a6c38a04155bfa8ff6c99befa2e rdf:first N3a1c90e9af724652b07f2c4a89cac416
    78 rdf:rest N76e20fe53eca4c17bc7785e26ce87efa
    79 Nc04e058e81fb4f1b9bf857e903441096 rdf:first Nced6c88fe362491ea8f390f35a359252
    80 rdf:rest rdf:nil
    81 Nced6c88fe362491ea8f390f35a359252 schema:familyName Manoussakis
    82 schema:givenName Ioannis
    83 rdf:type schema:Person
    84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Information and Computing Sciences
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Computation Theory and Mathematics
    89 rdf:type schema:DefinedTerm
    90 sg:person.010065200346.76 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    91 schema:familyName Sterbini
    92 schema:givenName Andrea
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010065200346.76
    94 rdf:type schema:Person
    95 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    96 schema:familyName Petreschi
    97 schema:givenName Rossella
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    99 rdf:type schema:Person
    100 sg:pub.10.1007/978-1-4757-3472-0_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034198720
    101 https://doi.org/10.1007/978-1-4757-3472-0_2
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/bf00288966 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030785779
    104 https://doi.org/10.1007/bf00288966
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/0012-365x(84)90023-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001514301
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/0020-0190(72)90035-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1029535244
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1016/0020-0190(80)90141-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050997689
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1016/0020-0190(81)90100-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023343635
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1016/0020-0190(81)90106-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1009445682
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1093/comjnl/34.4.345 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025603208
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1137/0206008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841347
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1137/0218010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842109
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1142/s0129054190000102 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897546
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1142/s0129054192000036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897591
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/355592.365595 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022750712
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1145/355606.361895 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008903287
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1145/357195.357199 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053427371
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1145/358527.358537 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031322763
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1145/359545.359563 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021135683
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1145/361082.361093 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014873305
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1145/361179.361202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005796851
    139 rdf:type schema:CreativeWork
    140 https://doi.org/10.1145/363162.363167 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029883865
    141 rdf:type schema:CreativeWork
    142 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    143 schema:name Department of Computer Science, University ”La Sapienza”, Via Salaria, 113-00198 Rome, Italy
    144 rdf:type schema:Organization
     




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


    ...