# The Dynamic And-Or Quorum System

Ontology type: schema:Chapter

### Chapter Info

DATE

2005

AUTHORS ABSTRACT

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. More... »

PAGES

472-486

### Book

TITLE

Distributed Computing

ISBN

978-3-540-29163-3
978-3-540-32075-3

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11561927_34

DOI

http://dx.doi.org/10.1007/11561927_34

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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"
},
"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",
"gossip protocol",
"message complexity",
"dynamic quorums",
"data structure",
"optimal algorithm",
"second contribution",
"algorithm",
"quorum sets",
"network",
"complexity",
"implementation",
"system",
"processors",
"environment",
"protocol",
"cardinality",
"set",
"good properties",
"quorum",
"issues",
"quality",
"knowledge",
"contribution",
"maintenance",
"use",
"fact",
"same parameters",
"twofold",
"parameters",
"candidates",
"structure",
"dynamics",
"excellent candidate",
"properties",
"algorithmic probe complexity",
"above quorum system",
"De-Bruijn network"
],
"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-01-01T19:10",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_17.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11561927_34"
}
]

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/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'

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.

116 TRIPLES      23 PREDICATES      72 URIs      65 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author Nb15b5177719f40508ebf6ff7fde5f9ac
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 N23f668312e184dfaa8d0e2009c74dd63
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
12 schema:keywords De-Bruijn network
13 above quorum system
16 algorithm
17 algorithmic probe complexity
18 candidates
19 cardinality
20 complexity
21 contribution
22 data structure
23 dynamic data structures
24 dynamic environment
25 dynamic overlay networks
26 dynamic quorums
27 dynamics
28 environment
29 excellent candidate
30 fact
31 good properties
32 gossip protocol
33 implementation
34 issues
35 knowledge
36 maintenance
37 message complexity
38 network
40 optimal algorithm
41 overlay network
42 parameters
43 probe complexity
44 processors
45 properties
46 protocol
47 quality
48 quorum
49 quorum sets
50 quorum systems
51 same parameters
52 second contribution
53 set
54 structure
55 system
56 twofold
57 use
58 schema:name The Dynamic And-Or Quorum System
59 schema:pagination 472-486
61 Nd4f0760b1453497292127227b8ed4f03
62 schema:publisher Naa30fee27e404866ac6c4d7d18b07554
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030120041
64 https://doi.org/10.1007/11561927_34
65 schema:sdDatePublished 2022-01-01T19:10
67 schema:sdPublisher N9381c27649f64a478d735d7fd8d225c9
68 schema:url https://doi.org/10.1007/11561927_34
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
73 schema:value 10.1007/11561927_34
74 rdf:type schema:PropertyValue
75 N23f668312e184dfaa8d0e2009c74dd63 rdf:first N77bf5c81dbfd41f1a38aa833157ebc94
76 rdf:rest rdf:nil
77 N6b5704b90736411a8a29bf71b082b2f5 rdf:first sg:person.07776170271.83
78 rdf:rest rdf:nil
79 N77bf5c81dbfd41f1a38aa833157ebc94 schema:familyName Fraigniaud
80 schema:givenName Pierre
81 rdf:type schema:Person
82 N9381c27649f64a478d735d7fd8d225c9 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 Naa30fee27e404866ac6c4d7d18b07554 schema:name Springer Nature
85 rdf:type schema:Organisation
87 978-3-540-32075-3
88 schema:name Distributed Computing
89 rdf:type schema:Book
90 Nb15b5177719f40508ebf6ff7fde5f9ac rdf:first sg:person.011144305505.38
91 rdf:rest N6b5704b90736411a8a29bf71b082b2f5
92 Nd4f0760b1453497292127227b8ed4f03 schema:name dimensions_id
93 schema:value pub.1030120041
94 rdf:type schema:PropertyValue
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
99 schema:name Computation Theory and Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.011144305505.38 schema:affiliation grid-institutes:grid.12136.37
103 schema:givenName Uri
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011144305505.38
105 rdf:type schema:Person
106 sg:person.07776170271.83 schema:affiliation grid-institutes:None
107 schema:familyName Naor
108 schema:givenName Moni
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
110 rdf:type schema:Person
111 grid-institutes:None schema:alternateName Dept. of Computer Science and Applied Mathematics, The Weizmann Institute
112 schema:name Dept. of Computer Science and Applied Mathematics, The Weizmann Institute
113 rdf:type schema:Organization
114 grid-institutes:grid.12136.37 schema:alternateName Dept. of Computer Science, Tel-Aviv University
115 schema:name Dept. of Computer Science, Tel-Aviv University
116 rdf:type schema:Organization