# 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",
"de Bruijn networks",
"data structure",
"gossip protocol",
"message complexity",
"optimal algorithm",
"dynamic quorums",
"second contribution",
"algorithm",
"quorum sets",
"network",
"complexity",
"implementation",
"system",
"processors",
"environment",
"protocol",
"cardinality",
"set",
"issues",
"good properties",
"quorum",
"quality",
"knowledge",
"contribution",
"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",
"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"
}
]

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.

114 TRIPLES      23 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
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
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
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
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
66 schema:url https://doi.org/10.1007/11561927_34
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
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
86 rdf:rest N56b3b181491949f083165fb219b9354c
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
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