View in EDS PDF Full Text

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, David1 peleg@wisdom.weizmann.ac.il, Wool, Avishai2 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
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 12856371
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: HOW TO BE AN EFFICIENT SNOOP,OR THE PROBE COMPLEXITY OF QUORUM SYSTEMS.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Peleg%2C+David%22">Peleg, David</searchLink><relatesTo>1</relatesTo><i> peleg@wisdom.weizmann.ac.il</i><br /><searchLink fieldCode="AR" term="%22Wool%2C+Avishai%22">Wool, Avishai</searchLink><relatesTo>2</relatesTo><i> yash@acm.org</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Discrete+Mathematics%22">SIAM Journal on Discrete Mathematics</searchLink>. 2002, Vol. 15 Issue 3, p416-433. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Backup+processing+alternatives+in+electronic+data+processing%22">Backup processing alternatives in electronic data processing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Data+replication%22">Data replication</searchLink><br /><searchLink fieldCode="DE" term="%22Electronic+systems%22">Electronic systems</searchLink><br /><searchLink fieldCode="DE" term="%22Information+dissemination%22">Information dissemination</searchLink><br /><searchLink fieldCode="DE" term="%22Information+science%22">Information science</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=12856371
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/S0895480198343819
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 416
    Subjects:
      – SubjectFull: Backup processing alternatives in electronic data processing
        Type: general
      – SubjectFull: Computer systems
        Type: general
      – SubjectFull: Data replication
        Type: general
      – SubjectFull: Electronic systems
        Type: general
      – SubjectFull: Information dissemination
        Type: general
      – SubjectFull: Information science
        Type: general
    Titles:
      – TitleFull: HOW TO BE AN EFFICIENT SNOOP,OR THE PROBE COMPLEXITY OF QUORUM SYSTEMS.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Peleg, David
      – PersonEntity:
          Name:
            NameFull: Wool, Avishai
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 05
              Text: 2002
              Type: published
              Y: 2002
          Identifiers:
            – Type: issn-print
              Value: 08954801
          Numbering:
            – Type: volume
              Value: 15
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: SIAM Journal on Discrete Mathematics
              Type: main
ResultId 1