2005
AUTHORS ABSTRACTWe investigate issues related to the probe complexity of the And-Or quorum system and its implementation in a dynamic environment. Our contribution is twofold: We first analyze the algorithmic probe complexity of the And-Or quorum system, and present two optimal algorithms. The first is a non-adaptive algorithm with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}log n)$\end{document} probe complexity, which matches a known lower bound. The second is an adaptive algorithm with a probe complexity that is linear in the cardinality of a quorum set (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n})$\end{document}), and requires at most O(loglogn) rounds. To the best of our knowledge, all other adaptive algorithms with same parameters (load and probe complexity) require \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\theta(\sqrt{n})$\end{document} rounds.Our second contribution is presenting the ‘dynamic And-Or’ quorum system – an adaptation of the above quorum system to a dynamic environment, where processors join and leave the network. It is based on a dynamic overlay network that emulates the De-Bruijn network and maintains the good properties of the quorum system(e.g.,load and availability). The algorithms suggested for the maintenance of these dynamic data structures are strongly coupled with the dynamic overlay network. This fact enables the use of gossip protocols which saves in message complexity and keeps the protocols simple and local. All these qualities make the ‘dynamic And-Or’ an excellent candidate for an implementation of dynamic quorums. More... »
PAGES472-486
Distributed Computing
ISBN
978-3-540-29163-3
978-3-540-32075-3
http://scigraph.springernature.com/pub.10.1007/11561927_34
DOIhttp://dx.doi.org/10.1007/11561927_34
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1030120041
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, Tel-Aviv University",
"id": "http://www.grid.ac/institutes/grid.12136.37",
"name": [
"Dept. of Computer Science, Tel-Aviv University"
],
"type": "Organization"
},
"familyName": "Nadav",
"givenName": "Uri",
"id": "sg:person.011144305505.38",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011144305505.38"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Dept. of Computer Science and Applied Mathematics, The Weizmann Institute",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Dept. of Computer Science and Applied Mathematics, The Weizmann Institute"
],
"type": "Organization"
},
"familyName": "Naor",
"givenName": "Moni",
"id": "sg:person.07776170271.83",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
],
"type": "Person"
}
],
"datePublished": "2005",
"datePublishedReg": "2005-01-01",
"description": "We investigate issues related to the probe complexity of the And-Or quorum system and its implementation in a dynamic environment. Our contribution is twofold: We first analyze the algorithmic probe complexity of the And-Or quorum system, and present two optimal algorithms. The first is a non-adaptive algorithm with \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(\\sqrt{n}log n)$\\end{document} probe complexity, which matches a known lower bound. The second is an adaptive algorithm with a probe complexity that is linear in the cardinality of a quorum set (\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(\\sqrt{n})$\\end{document}), and requires at most O(loglogn) rounds. To the best of our knowledge, all other adaptive algorithms with same parameters (load and probe complexity) require \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\theta(\\sqrt{n})$\\end{document} rounds.Our second contribution is presenting the \u2018dynamic And-Or\u2019 quorum system \u2013 an adaptation of the above quorum system to a dynamic environment, where processors join and leave the network. It is based on a dynamic overlay network that emulates the De-Bruijn network and maintains the good properties of the quorum system(e.g.,load and availability). The algorithms suggested for the maintenance of these dynamic data structures are strongly coupled with the dynamic overlay network. This fact enables the use of gossip protocols which saves in message complexity and keeps the protocols simple and local. All these qualities make the \u2018dynamic And-Or\u2019 an excellent candidate for an implementation of dynamic quorums.",
"editor": [
{
"familyName": "Fraigniaud",
"givenName": "Pierre",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11561927_34",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-29163-3",
"978-3-540-32075-3"
],
"name": "Distributed Computing",
"type": "Book"
},
"keywords": [
"dynamic overlay networks",
"quorum systems",
"overlay network",
"probe complexity",
"dynamic environment",
"dynamic data structures",
"adaptive algorithm",
"de Bruijn networks",
"data structure",
"gossip protocol",
"message complexity",
"optimal algorithm",
"non-adaptive algorithms",
"dynamic quorums",
"second contribution",
"algorithm",
"quorum sets",
"network",
"complexity",
"implementation",
"system",
"processors",
"environment",
"protocol",
"cardinality",
"set",
"issues",
"good properties",
"quorum",
"quality",
"knowledge",
"contribution",
"adaptation",
"maintenance",
"use",
"twofold",
"fact",
"same parameters",
"parameters",
"structure",
"candidates",
"dynamics",
"excellent candidate",
"properties"
],
"name": "The Dynamic And-Or Quorum System",
"pagination": "472-486",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1030120041"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11561927_34"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11561927_34",
"https://app.dimensions.ai/details/publication/pub.1030120041"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:48",
"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_365.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11561927_34"
}
]
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/11561927_34'
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/11561927_34'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11561927_34'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11561927_34'
This table displays all metadata directly associated to this object as RDF triples.
114 TRIPLES
23 PREDICATES
70 URIs
63 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/11561927_34 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0802 |
3 | ″ | schema:author | N977d8f070d9c4e19adabb6bb6369f107 |
4 | ″ | schema:datePublished | 2005 |
5 | ″ | schema:datePublishedReg | 2005-01-01 |
6 | ″ | schema:description | We investigate issues related to the probe complexity of the And-Or quorum system and its implementation in a dynamic environment. Our contribution is twofold: We first analyze the algorithmic probe complexity of the And-Or quorum system, and present two optimal algorithms. The first is a non-adaptive algorithm with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}log n)$\end{document} probe complexity, which matches a known lower bound. The second is an adaptive algorithm with a probe complexity that is linear in the cardinality of a quorum set (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n})$\end{document}), and requires at most O(loglogn) rounds. To the best of our knowledge, all other adaptive algorithms with same parameters (load and probe complexity) require \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\theta(\sqrt{n})$\end{document} rounds.Our second contribution is presenting the ‘dynamic And-Or’ quorum system – an adaptation of the above quorum system to a dynamic environment, where processors join and leave the network. It is based on a dynamic overlay network that emulates the De-Bruijn network and maintains the good properties of the quorum system(e.g.,load and availability). The algorithms suggested for the maintenance of these dynamic data structures are strongly coupled with the dynamic overlay network. This fact enables the use of gossip protocols which saves in message complexity and keeps the protocols simple and local. All these qualities make the ‘dynamic And-Or’ an excellent candidate for an implementation of dynamic quorums. |
7 | ″ | schema:editor | N37db01bbd45d40ecaa7140371353dd84 |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | false |
11 | ″ | schema:isPartOf | N635efd3087e8408384016435ac38fce2 |
12 | ″ | schema:keywords | adaptation |
13 | ″ | ″ | adaptive algorithm |
14 | ″ | ″ | algorithm |
15 | ″ | ″ | candidates |
16 | ″ | ″ | cardinality |
17 | ″ | ″ | complexity |
18 | ″ | ″ | contribution |
19 | ″ | ″ | data structure |
20 | ″ | ″ | de Bruijn networks |
21 | ″ | ″ | dynamic data structures |
22 | ″ | ″ | dynamic environment |
23 | ″ | ″ | dynamic overlay networks |
24 | ″ | ″ | dynamic quorums |
25 | ″ | ″ | dynamics |
26 | ″ | ″ | environment |
27 | ″ | ″ | excellent candidate |
28 | ″ | ″ | fact |
29 | ″ | ″ | good properties |
30 | ″ | ″ | gossip protocol |
31 | ″ | ″ | implementation |
32 | ″ | ″ | issues |
33 | ″ | ″ | knowledge |
34 | ″ | ″ | maintenance |
35 | ″ | ″ | message complexity |
36 | ″ | ″ | network |
37 | ″ | ″ | non-adaptive algorithms |
38 | ″ | ″ | optimal algorithm |
39 | ″ | ″ | overlay network |
40 | ″ | ″ | parameters |
41 | ″ | ″ | probe complexity |
42 | ″ | ″ | processors |
43 | ″ | ″ | properties |
44 | ″ | ″ | protocol |
45 | ″ | ″ | quality |
46 | ″ | ″ | quorum |
47 | ″ | ″ | quorum sets |
48 | ″ | ″ | quorum systems |
49 | ″ | ″ | same parameters |
50 | ″ | ″ | second contribution |
51 | ″ | ″ | set |
52 | ″ | ″ | structure |
53 | ″ | ″ | system |
54 | ″ | ″ | twofold |
55 | ″ | ″ | use |
56 | ″ | schema:name | The Dynamic And-Or Quorum System |
57 | ″ | schema:pagination | 472-486 |
58 | ″ | schema:productId | N6d794916402d414fad17d3892ffdc1e7 |
59 | ″ | ″ | Nc70bf092b0ba4e659b44a31e9ad9a499 |
60 | ″ | schema:publisher | N7a5a462bc790477bb479e99ec38f4c4f |
61 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1030120041 |
62 | ″ | ″ | https://doi.org/10.1007/11561927_34 |
63 | ″ | schema:sdDatePublished | 2022-05-10T10:48 |
64 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
65 | ″ | schema:sdPublisher | N93d622aeeead48c48d2f9821d9d20819 |
66 | ″ | schema:url | https://doi.org/10.1007/11561927_34 |
67 | ″ | sgo:license | sg:explorer/license/ |
68 | ″ | sgo:sdDataset | chapters |
69 | ″ | rdf:type | schema:Chapter |
70 | N37db01bbd45d40ecaa7140371353dd84 | rdf:first | Nf5c6c8c462c948f280531b07cd5d53af |
71 | ″ | rdf:rest | rdf:nil |
72 | N56b3b181491949f083165fb219b9354c | rdf:first | sg:person.07776170271.83 |
73 | ″ | rdf:rest | rdf:nil |
74 | N635efd3087e8408384016435ac38fce2 | schema:isbn | 978-3-540-29163-3 |
75 | ″ | ″ | 978-3-540-32075-3 |
76 | ″ | schema:name | Distributed Computing |
77 | ″ | rdf:type | schema:Book |
78 | N6d794916402d414fad17d3892ffdc1e7 | schema:name | dimensions_id |
79 | ″ | schema:value | pub.1030120041 |
80 | ″ | rdf:type | schema:PropertyValue |
81 | N7a5a462bc790477bb479e99ec38f4c4f | schema:name | Springer Nature |
82 | ″ | rdf:type | schema:Organisation |
83 | N93d622aeeead48c48d2f9821d9d20819 | schema:name | Springer Nature - SN SciGraph project |
84 | ″ | rdf:type | schema:Organization |
85 | N977d8f070d9c4e19adabb6bb6369f107 | rdf:first | sg:person.011144305505.38 |
86 | ″ | rdf:rest | N56b3b181491949f083165fb219b9354c |
87 | Nc70bf092b0ba4e659b44a31e9ad9a499 | schema:name | doi |
88 | ″ | schema:value | 10.1007/11561927_34 |
89 | ″ | rdf:type | schema:PropertyValue |
90 | Nf5c6c8c462c948f280531b07cd5d53af | schema:familyName | Fraigniaud |
91 | ″ | schema:givenName | Pierre |
92 | ″ | rdf:type | schema:Person |
93 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
94 | ″ | schema:name | Information and Computing Sciences |
95 | ″ | rdf:type | schema:DefinedTerm |
96 | anzsrc-for:0802 | schema:inDefinedTermSet | anzsrc-for: |
97 | ″ | schema:name | Computation Theory and Mathematics |
98 | ″ | rdf:type | schema:DefinedTerm |
99 | sg:person.011144305505.38 | schema:affiliation | grid-institutes:grid.12136.37 |
100 | ″ | schema:familyName | Nadav |
101 | ″ | schema:givenName | Uri |
102 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011144305505.38 |
103 | ″ | rdf:type | schema:Person |
104 | sg:person.07776170271.83 | schema:affiliation | grid-institutes:None |
105 | ″ | schema:familyName | Naor |
106 | ″ | schema:givenName | Moni |
107 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83 |
108 | ″ | rdf:type | schema:Person |
109 | grid-institutes:None | schema:alternateName | Dept. of Computer Science and Applied Mathematics, The Weizmann Institute |
110 | ″ | schema:name | Dept. of Computer Science and Applied Mathematics, The Weizmann Institute |
111 | ″ | rdf:type | schema:Organization |
112 | grid-institutes:grid.12136.37 | schema:alternateName | Dept. of Computer Science, Tel-Aviv University |
113 | ″ | schema:name | Dept. of Computer Science, Tel-Aviv University |
114 | ″ | rdf:type | schema:Organization |