HOW TO BE AN EFFICIENT SNOOP,OR THE PROBE COMPLEXITY OF QUORUM SYSTEMS.

Saved in:

Bibliographic Details
Title:	HOW TO BE AN EFFICIENT SNOOP,OR THE PROBE COMPLEXITY OF QUORUM SYSTEMS.
Authors:	Peleg, David¹ peleg@wisdom.weizmann.ac.il, Wool, Avishai² yash@acm.org
Source:	SIAM Journal on Discrete Mathematics. 2002, Vol. 15 Issue 3, p416-433. 18p.
Subjects:	Backup processing alternatives in electronic data processing, Computer systems, Data replication, Electronic systems, Information dissemination, Information science
Abstract:	A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information. When the elements may fail, a user of a distributed protocol needs to quickly find a quorum all of whose elements are alive or evidence that no such quorum exists. This is done by probing the system elements, one at a time, to determine if they are alive or dead. This paper studies the probe complexity PC(S) of a quorum system 8, defined as the worst case number of probes required to find a live quorum or to show its nonexistence in 8, using the best probing strategy. We show that for large classes of quorum systems, all ii elements must be probed in the worst case. Such systems are called evasive. However, not all quorum systems are evasive; we demonstrate a system where O(log n) probes always suffice. Then we prove two lower bounds on the probe complexity in terms of the minimal quorum cardinality c(S) and the number of minimal quorums m(S). Finally, we show a universal probe strategy which never makes more than c(S)² - c(S) + 1 probes; thus any system with c(S) ≤ n is nonevasive. [ABSTRACT FROM AUTHOR]
	Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual exclusion, data replication, and dissemination of information. When the elements may fail, a user of a distributed protocol needs to quickly find a quorum all of whose elements are alive or evidence that no such quorum exists. This is done by probing the system elements, one at a time, to determine if they are alive or dead. This paper studies the probe complexity PC(S) of a quorum system 8, defined as the worst case number of probes required to find a live quorum or to show its nonexistence in 8, using the best probing strategy. We show that for large classes of quorum systems, all ii elements must be probed in the worst case. Such systems are called evasive. However, not all quorum systems are evasive; we demonstrate a system where O(log n) probes always suffice. Then we prove two lower bounds on the probe complexity in terms of the minimal quorum cardinality c(S) and the number of minimal quorums m(S). Finally, we show a universal probe strategy which never makes more than c(S)² - c(S) + 1 probes; thus any system with c(S) ≤ n is nonevasive. [ABSTRACT FROM AUTHOR]
ISSN:	08954801
DOI:	10.1137/S0895480198343819