Ontology type: schema:ScholarlyArticle
2012-06-29
AUTHORSMarta Kwiatkowska, Gethin Norman, David Parker
ABSTRACTHerman’s self-stabilisation algorithm provides a simple randomised solution to the problem of recovering from faults in an N-process token ring. However, a precise analysis of the algorithm’s maximum execution time proves to be surprisingly difficult. McIver and Morgan have conjectured that the worst-case behaviour results from a ring configuration of three evenly spaced tokens, giving an expected time of approximately 0.15N2. However, the tightest upper bound proved to date is 0.64N2. We apply probabilistic verification techniques, using the probabilistic model checker PRISM, to analyse the conjecture, showing it to be correct for all sizes of the ring that can be exhaustively analysed. We furthermore demonstrate that the worst-case execution time of the algorithm can be reduced by using a biased coin. More... »
PAGES661-670
http://scigraph.springernature.com/pub.10.1007/s00165-012-0227-6
DOIhttp://dx.doi.org/10.1007/s00165-012-0227-6
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1006141989
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": "Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK",
"id": "http://www.grid.ac/institutes/grid.4991.5",
"name": [
"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK"
],
"type": "Organization"
},
"familyName": "Kwiatkowska",
"givenName": "Marta",
"id": "sg:person.011375012273.39",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011375012273.39"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "School of Computing Science, University of Glasgow, Glasgow, UK",
"id": "http://www.grid.ac/institutes/grid.8756.c",
"name": [
"School of Computing Science, University of Glasgow, Glasgow, UK"
],
"type": "Organization"
},
"familyName": "Norman",
"givenName": "Gethin",
"id": "sg:person.016323171577.36",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016323171577.36"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK",
"id": "http://www.grid.ac/institutes/grid.4991.5",
"name": [
"Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK"
],
"type": "Organization"
},
"familyName": "Parker",
"givenName": "David",
"id": "sg:person.014007552600.37",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007552600.37"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-60045-0_48",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002999837",
"https://doi.org/10.1007/3-540-60045-0_48"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-22110-1_47",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027900693",
"https://doi.org/10.1007/978-3-642-22110-1_47"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4684-9455-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003855982",
"https://doi.org/10.1007/978-1-4684-9455-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10703-010-0097-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013198998",
"https://doi.org/10.1007/s10703-010-0097-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10009-010-0146-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008242412",
"https://doi.org/10.1007/s10009-010-0146-x"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-22012-8_37",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006189401",
"https://doi.org/10.1007/978-3-642-22012-8_37"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-05118-0_17",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031653339",
"https://doi.org/10.1007/978-3-642-05118-0_17"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-72522-0_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012626164",
"https://doi.org/10.1007/978-3-540-72522-0_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00446-005-0142-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039696053",
"https://doi.org/10.1007/s00446-005-0142-7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-70545-1_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044553785",
"https://doi.org/10.1007/978-3-540-70545-1_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01211866",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052049375",
"https://doi.org/10.1007/bf01211866"
],
"type": "CreativeWork"
}
],
"datePublished": "2012-06-29",
"datePublishedReg": "2012-06-29",
"description": "Herman\u2019s self-stabilisation algorithm provides a simple randomised solution to the problem of recovering from faults in an N-process token ring. However, a precise analysis of the algorithm\u2019s maximum execution time proves to be surprisingly difficult. McIver and Morgan have conjectured that the worst-case behaviour results from a ring configuration of three evenly spaced tokens, giving an expected time of approximately 0.15N2. However, the tightest upper bound proved to date is 0.64N2. We apply probabilistic verification techniques, using the probabilistic model checker PRISM, to analyse the conjecture, showing it to be correct for all sizes of the ring that can be exhaustively analysed. We furthermore demonstrate that the worst-case execution time of the algorithm can be reduced by using a biased coin.",
"genre": "article",
"id": "sg:pub.10.1007/s00165-012-0227-6",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1136737",
"issn": [
"0934-5043",
"1433-299X"
],
"name": "Formal Aspects of Computing",
"publisher": "Association for Computing Machinery (ACM)",
"type": "Periodical"
},
{
"issueNumber": "4-6",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "24"
}
],
"keywords": [
"maximum execution time",
"execution time",
"probabilistic verification techniques",
"probabilistic model checker PRISM",
"model checker PRISM",
"worst-case execution time",
"algorithm",
"token ring",
"worst-case behavior",
"verification techniques",
"probabilistic verification",
"tokens",
"verification",
"solution",
"faults",
"precise analysis",
"time",
"configuration",
"technique",
"biased coin",
"coins",
"analysis",
"McIver",
"behavior",
"ring configuration",
"date",
"prism",
"conjecture",
"size",
"problem",
"ring",
"Morgan"
],
"name": "Probabilistic verification of Herman\u2019s self-stabilisation algorithm",
"pagination": "661-670",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1006141989"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00165-012-0227-6"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00165-012-0227-6",
"https://app.dimensions.ai/details/publication/pub.1006141989"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-10T10:04",
"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/article/article_566.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00165-012-0227-6"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s00165-012-0227-6'
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/s00165-012-0227-6'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00165-012-0227-6'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00165-012-0227-6'
This table displays all metadata directly associated to this object as RDF triples.
151 TRIPLES
22 PREDICATES
68 URIs
49 LITERALS
6 BLANK NODES