Proof labeling schemes View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2010-05

AUTHORS

Amos Korman, Shay Kutten, David Peleg

ABSTRACT

This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as “how expensive is local verification?” and more specifically, “how expensive is local verification compared to computation?” A suitable model is introduced in which these questions are studied in terms of the number of bits a vertex needs to communicate. The model includes the definition of a proof labeling scheme (a pair of algorithms- one to assign the labels, and one to use them to verify that the global property holds). In addition, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the bit complexity of schemes for multiple basic problems. The paper also studies the role and cost of unique identities in terms of impossibility and complexity, in the context of proof labeling schemes. Previous studies on related questions deal with distributed algorithms that simultaneously compute a configuration and verify that this configuration has a certain desired property. It turns out that this combined approach enables the verification to be less costly sometimes, since the configuration is typically generated so as to be easily verifiable. In contrast, our approach separates the configuration design from the verification. That is, it first generates the desired configuration without bothering with the need to verify it, and then handles the task of constructing a suitable verification scheme. Our approach thus allows for a more modular design of algorithms, and has the potential to aid in verifying properties even when the original design of the structures for maintaining them was done without verification in mind. More... »

PAGES

215-233

References to SciGraph publications

  • 2005. Labeling Schemes for Tree Representation in DISTRIBUTED COMPUTING – IWDC 2005
  • 1993. Time optimal self-stabilizing spanning tree algorithms in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 2004. Distributed Weighted Matching in DISTRIBUTED COMPUTING
  • 2005. Label-Guided Graph Exploration by a Finite Automaton in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1994. Self-stabilization by local checking and global reset in DISTRIBUTED ALGORITHMS
  • 1999-10. Memory requirements for silent stabilization in ACTA INFORMATICA
  • 1998. Transient fault detectors in DISTRIBUTED COMPUTING
  • 2006. Tree Exploration with an Oracle in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006
  • 1993-11. Self-stabilization of dynamic systems assuming only read/write atomicity in DISTRIBUTED COMPUTING
  • 2007. Labeling Schemes for Vertex Connectivity in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1990. Distributed reset in FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00446-010-0095-3

    DOI

    http://dx.doi.org/10.1007/s00446-010-0095-3

    DIMENSIONS

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


    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": {
              "name": [
                "CNRS and University, Paris Diderot, 75013, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Korman", 
            "givenName": "Amos", 
            "id": "sg:person.013353220506.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technion \u2013 Israel Institute of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Information Systems Group, Faculty of IE and M, The Technion, 32000, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kutten", 
            "givenName": "Shay", 
            "id": "sg:person.010351002277.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010351002277.08"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Weizmann Institute of Science", 
              "id": "https://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, 76100, Rehovot, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Peleg", 
            "givenName": "David", 
            "id": "sg:person.012357743251.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357743251.05"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000771230"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1146381.1146410", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005207210"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s002360050180", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005215512", 
              "https://doi.org/10.1007/s002360050180"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-53487-3_54", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005703088", 
              "https://doi.org/10.1007/3-540-53487-3_54"
            ], 
            "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/1248377.1248402", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006646469"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11603771_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014679656", 
              "https://doi.org/10.1007/11603771_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11603771_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014679656", 
              "https://doi.org/10.1007/11603771_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jpdc.2001.1823", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014818940"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/201019.201022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016634643"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02278851", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017141967", 
              "https://doi.org/10.1007/bf02278851"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02278851", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017141967", 
              "https://doi.org/10.1007/bf02278851"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1011767.1011811", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024782193"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(96)00286-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027194969"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/31846.32978", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029316927"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/248052.248104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030772651"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/259380.259438", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031424196"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0065-2458(08)60342-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031577398"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73420-8_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031709023", 
              "https://doi.org/10.1007/978-3-540-73420-8_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73420-8_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031709023", 
              "https://doi.org/10.1007/978-3-540-73420-8_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30186-8_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032469964", 
              "https://doi.org/10.1007/978-3-540-30186-8_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30186-8_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032469964", 
              "https://doi.org/10.1007/978-3-540-30186-8_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/357195.357200", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032636611"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/167088.167256", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034686486"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57529-4_72", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035925902", 
              "https://doi.org/10.1007/3-540-57529-4_72"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/28.1.5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035935066"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11821069_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037978405", 
              "https://doi.org/10.1007/11821069_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11821069_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037978405", 
              "https://doi.org/10.1007/11821069_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0020443", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038735350", 
              "https://doi.org/10.1007/bfb0020443"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040407045", 
              "https://doi.org/10.1007/11523468_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040407045", 
              "https://doi.org/10.1007/11523468_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1146381.1146389", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043358496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/65950.65953", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049892375"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jalgor.2004.05.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050578061"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/167088.167149", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051815222"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2005.03.015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051912794"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/568438.568451", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052254226"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0056474", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053469461", 
              "https://doi.org/10.1007/bfb0056474"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/71.588622", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061217634"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0221070", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842402"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539703433912", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879473"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1987.20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086175088"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1991.185377", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086290108"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1991.185378", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086290493"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/fscs.1990.89594", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086292491"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9780898719772", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098557268"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9781139015165", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098713219"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010-05", 
        "datePublishedReg": "2010-05-01", 
        "description": "This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as \u201chow expensive is local verification?\u201d and more specifically, \u201chow expensive is local verification compared to computation?\u201d A suitable model is introduced in which these questions are studied in terms of the number of bits a vertex needs to communicate. The model includes the definition of a proof labeling scheme (a pair of algorithms- one to assign the labels, and one to use them to verify that the global property holds). In addition, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the bit complexity of schemes for multiple basic problems. The paper also studies the role and cost of unique identities in terms of impossibility and complexity, in the context of proof labeling schemes. Previous studies on related questions deal with distributed algorithms that simultaneously compute a configuration and verify that this configuration has a certain desired property. It turns out that this combined approach enables the verification to be less costly sometimes, since the configuration is typically generated so as to be easily verifiable. In contrast, our approach separates the configuration design from the verification. That is, it first generates the desired configuration without bothering with the need to verify it, and then handles the task of constructing a suitable verification scheme. Our approach thus allows for a more modular design of algorithms, and has the potential to aid in verifying properties even when the original design of the structures for maintaining them was done without verification in mind.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00446-010-0095-3", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "22"
          }
        ], 
        "name": "Proof labeling schemes", 
        "pagination": "215-233", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6371d1e95bcd3c0eb3c66301975c2fa6c29667f9dfb0db01ff1bf97f27a1fc23"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00446-010-0095-3"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020871573"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00446-010-0095-3", 
          "https://app.dimensions.ai/details/publication/pub.1020871573"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T10:04", 
        "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/0000000347_0000000347/records_89826_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00446-010-0095-3"
      }
    ]
     

    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/s00446-010-0095-3'

    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/s00446-010-0095-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00446-010-0095-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00446-010-0095-3'


     

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

    214 TRIPLES      21 PREDICATES      68 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00446-010-0095-3 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N78514171e8f9429283df79d17169a120
    4 schema:citation sg:pub.10.1007/11523468_28
    5 sg:pub.10.1007/11603771_2
    6 sg:pub.10.1007/11821069_2
    7 sg:pub.10.1007/3-540-53487-3_54
    8 sg:pub.10.1007/3-540-57529-4_72
    9 sg:pub.10.1007/978-3-540-30186-8_24
    10 sg:pub.10.1007/978-3-540-73420-8_11
    11 sg:pub.10.1007/bf02278851
    12 sg:pub.10.1007/bfb0020443
    13 sg:pub.10.1007/bfb0056474
    14 sg:pub.10.1007/s002360050180
    15 https://doi.org/10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5
    16 https://doi.org/10.1006/jpdc.2001.1823
    17 https://doi.org/10.1016/j.jalgor.2004.05.002
    18 https://doi.org/10.1016/j.tcs.2005.03.015
    19 https://doi.org/10.1016/s0065-2458(08)60342-3
    20 https://doi.org/10.1016/s0304-3975(96)00286-1
    21 https://doi.org/10.1017/cbo9781139015165
    22 https://doi.org/10.1093/comjnl/28.1.5
    23 https://doi.org/10.1109/71.588622
    24 https://doi.org/10.1109/fscs.1990.89594
    25 https://doi.org/10.1109/sfcs.1987.20
    26 https://doi.org/10.1109/sfcs.1991.185377
    27 https://doi.org/10.1109/sfcs.1991.185378
    28 https://doi.org/10.1137/0221070
    29 https://doi.org/10.1137/1.9780898719772
    30 https://doi.org/10.1137/s0097539703433912
    31 https://doi.org/10.1145/1011767.1011811
    32 https://doi.org/10.1145/1146381.1146389
    33 https://doi.org/10.1145/1146381.1146410
    34 https://doi.org/10.1145/1248377.1248402
    35 https://doi.org/10.1145/167088.167149
    36 https://doi.org/10.1145/167088.167256
    37 https://doi.org/10.1145/201019.201022
    38 https://doi.org/10.1145/248052.248104
    39 https://doi.org/10.1145/259380.259438
    40 https://doi.org/10.1145/31846.32978
    41 https://doi.org/10.1145/357195.357200
    42 https://doi.org/10.1145/361179.361202
    43 https://doi.org/10.1145/568438.568451
    44 https://doi.org/10.1145/65950.65953
    45 schema:datePublished 2010-05
    46 schema:datePublishedReg 2010-05-01
    47 schema:description This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as “how expensive is local verification?” and more specifically, “how expensive is local verification compared to computation?” A suitable model is introduced in which these questions are studied in terms of the number of bits a vertex needs to communicate. The model includes the definition of a proof labeling scheme (a pair of algorithms- one to assign the labels, and one to use them to verify that the global property holds). In addition, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the bit complexity of schemes for multiple basic problems. The paper also studies the role and cost of unique identities in terms of impossibility and complexity, in the context of proof labeling schemes. Previous studies on related questions deal with distributed algorithms that simultaneously compute a configuration and verify that this configuration has a certain desired property. It turns out that this combined approach enables the verification to be less costly sometimes, since the configuration is typically generated so as to be easily verifiable. In contrast, our approach separates the configuration design from the verification. That is, it first generates the desired configuration without bothering with the need to verify it, and then handles the task of constructing a suitable verification scheme. Our approach thus allows for a more modular design of algorithms, and has the potential to aid in verifying properties even when the original design of the structures for maintaining them was done without verification in mind.
    48 schema:genre research_article
    49 schema:inLanguage en
    50 schema:isAccessibleForFree false
    51 schema:isPartOf Nb98b67533a7a44d8ae8ecec1c5c28c2a
    52 Nef6c0d3002a5429f94f0186f16219fa8
    53 sg:journal.1052621
    54 schema:name Proof labeling schemes
    55 schema:pagination 215-233
    56 schema:productId Na6a29a423f904b54a1d1f61cd2d28e85
    57 Nae844c17d5844d4d8a102c90007c238c
    58 Nd16fda7a22874944acb05ab68a82d758
    59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020871573
    60 https://doi.org/10.1007/s00446-010-0095-3
    61 schema:sdDatePublished 2019-04-11T10:04
    62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    63 schema:sdPublisher Ne1d389128851413ab91ded41f2436705
    64 schema:url http://link.springer.com/10.1007/s00446-010-0095-3
    65 sgo:license sg:explorer/license/
    66 sgo:sdDataset articles
    67 rdf:type schema:ScholarlyArticle
    68 N26a769618163467e98e79349a60c99e8 rdf:first sg:person.010351002277.08
    69 rdf:rest N677075d994cd486faece8c46d3b13753
    70 N5ef82fe1a482422fb1e4a863ec91d8fb schema:name CNRS and University, Paris Diderot, 75013, Paris, France
    71 rdf:type schema:Organization
    72 N677075d994cd486faece8c46d3b13753 rdf:first sg:person.012357743251.05
    73 rdf:rest rdf:nil
    74 N78514171e8f9429283df79d17169a120 rdf:first sg:person.013353220506.00
    75 rdf:rest N26a769618163467e98e79349a60c99e8
    76 Na6a29a423f904b54a1d1f61cd2d28e85 schema:name dimensions_id
    77 schema:value pub.1020871573
    78 rdf:type schema:PropertyValue
    79 Nae844c17d5844d4d8a102c90007c238c schema:name doi
    80 schema:value 10.1007/s00446-010-0095-3
    81 rdf:type schema:PropertyValue
    82 Nb98b67533a7a44d8ae8ecec1c5c28c2a schema:issueNumber 4
    83 rdf:type schema:PublicationIssue
    84 Nd16fda7a22874944acb05ab68a82d758 schema:name readcube_id
    85 schema:value 6371d1e95bcd3c0eb3c66301975c2fa6c29667f9dfb0db01ff1bf97f27a1fc23
    86 rdf:type schema:PropertyValue
    87 Ne1d389128851413ab91ded41f2436705 schema:name Springer Nature - SN SciGraph project
    88 rdf:type schema:Organization
    89 Nef6c0d3002a5429f94f0186f16219fa8 schema:volumeNumber 22
    90 rdf:type schema:PublicationVolume
    91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Information and Computing Sciences
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Computation Theory and Mathematics
    96 rdf:type schema:DefinedTerm
    97 sg:journal.1052621 schema:issn 0178-2770
    98 1432-0452
    99 schema:name Distributed Computing
    100 rdf:type schema:Periodical
    101 sg:person.010351002277.08 schema:affiliation https://www.grid.ac/institutes/grid.6451.6
    102 schema:familyName Kutten
    103 schema:givenName Shay
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010351002277.08
    105 rdf:type schema:Person
    106 sg:person.012357743251.05 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
    107 schema:familyName Peleg
    108 schema:givenName David
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357743251.05
    110 rdf:type schema:Person
    111 sg:person.013353220506.00 schema:affiliation N5ef82fe1a482422fb1e4a863ec91d8fb
    112 schema:familyName Korman
    113 schema:givenName Amos
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00
    115 rdf:type schema:Person
    116 sg:pub.10.1007/11523468_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040407045
    117 https://doi.org/10.1007/11523468_28
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/11603771_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014679656
    120 https://doi.org/10.1007/11603771_2
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/11821069_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037978405
    123 https://doi.org/10.1007/11821069_2
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/3-540-53487-3_54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005703088
    126 https://doi.org/10.1007/3-540-53487-3_54
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/3-540-57529-4_72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035925902
    129 https://doi.org/10.1007/3-540-57529-4_72
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-540-30186-8_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032469964
    132 https://doi.org/10.1007/978-3-540-30186-8_24
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/978-3-540-73420-8_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031709023
    135 https://doi.org/10.1007/978-3-540-73420-8_11
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/bf02278851 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017141967
    138 https://doi.org/10.1007/bf02278851
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/bfb0020443 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038735350
    141 https://doi.org/10.1007/bfb0020443
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/bfb0056474 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053469461
    144 https://doi.org/10.1007/bfb0056474
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/s002360050180 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005215512
    147 https://doi.org/10.1007/s002360050180
    148 rdf:type schema:CreativeWork
    149 https://doi.org/10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000771230
    150 rdf:type schema:CreativeWork
    151 https://doi.org/10.1006/jpdc.2001.1823 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014818940
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1016/j.jalgor.2004.05.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050578061
    154 rdf:type schema:CreativeWork
    155 https://doi.org/10.1016/j.tcs.2005.03.015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051912794
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1016/s0065-2458(08)60342-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031577398
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1016/s0304-3975(96)00286-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027194969
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1017/cbo9781139015165 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098713219
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1093/comjnl/28.1.5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035935066
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1109/71.588622 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061217634
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1109/fscs.1990.89594 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086292491
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1109/sfcs.1987.20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086175088
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1109/sfcs.1991.185377 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086290108
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1109/sfcs.1991.185378 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086290493
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1137/0221070 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842402
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1137/1.9780898719772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557268
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1137/s0097539703433912 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879473
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1145/1011767.1011811 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024782193
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1145/1146381.1146389 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043358496
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1145/1146381.1146410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005207210
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1145/1248377.1248402 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006646469
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1145/167088.167149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051815222
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1145/167088.167256 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034686486
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1145/201019.201022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016634643
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1145/248052.248104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030772651
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1145/259380.259438 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031424196
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1145/31846.32978 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029316927
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1145/357195.357200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032636611
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1145/361179.361202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005796851
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1145/568438.568451 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052254226
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1145/65950.65953 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049892375
    208 rdf:type schema:CreativeWork
    209 https://www.grid.ac/institutes/grid.13992.30 schema:alternateName Weizmann Institute of Science
    210 schema:name Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, 76100, Rehovot, Israel
    211 rdf:type schema:Organization
    212 https://www.grid.ac/institutes/grid.6451.6 schema:alternateName Technion – Israel Institute of Technology
    213 schema:name Information Systems Group, Faculty of IE and M, The Technion, 32000, Haifa, Israel
    214 rdf:type schema:Organization
     




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


    ...