View in EDS PDF Full Text

Eventual election of multiple leaders for solving consensus in anonymous systems.

Saved in:
Bibliographic Details
Title: Eventual election of multiple leaders for solving consensus in anonymous systems.
Authors: Jiménez, Ernesto ernes@eui.upm.es, Arévalo, Sergio1 sergio.arevalo@eui.upm.es, Herrera, Carlos2 carlos.herrera@epn.edu.ec, Tang, Jian1 tjapply@gmail.com
Source: Journal of Supercomputing. Oct2015, Vol. 71 Issue 10, p3726-3743. 18p.
Subjects: Distributed computing, Computer system failure prevention, Computer storage capacity, Computer network reliability, Electronic data processing
Abstract: In classical distributed systems, each process has a unique identity. Today, new distributed systems have emerged where a unique identity is not always possible to be assigned to each process. For example, in many sensor networks a unique identity is not possible to be included in each device due to its small storage capacity, reduced computational power, or the huge number of devices to be identified. In these cases, we have to work with anonymous distributed systems where processes cannot be identified. Consensus cannot be solved in classical and anonymous asynchronous distributed systems where processes can crash. To bypass this impossibility result, failure detectors are added to these systems. It is known that $$\varOmega $$ is the weakest failure detector class for solving consensus in classical asynchronous systems when a majority of processes never crashes. Although $${ A }\varOmega $$ was introduced as an anonymous version of $$\varOmega ,$$ to find the weakest failure detector in anonymous systems to solve consensus when a majority of processes never crashes is nowadays an open question. Furthermore, $${ A }\varOmega $$ has the important drawback that it is not implementable. Very recently, $${ A }\varOmega '$$ has been introduced as a counterpart of $$\varOmega $$ for anonymous systems. In this paper, we show that the $${ A }\varOmega '$$ failure detector class is strictly weaker than $${ A }\varOmega $$ (i.e., $${ A }\varOmega '$$ provides less information about process crashes than $${ A }\varOmega $$ ). We also present in this paper the first implementation of $${ A }\varOmega '$$ (hence, we also show that $${ A }\varOmega '$$ is implementable), and, finally, we include the first implementation of consensus in anonymous asynchronous systems augmented with $${ A }\varOmega '$$ and where a majority of processes does not crash. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Supercomputing is the property of Springer Nature 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: 109475503
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Eventual election of multiple leaders for solving consensus in anonymous systems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Jiménez%2C+Ernesto%22">Jiménez, Ernesto</searchLink><i> ernes@eui.upm.es</i><br /><searchLink fieldCode="AR" term="%22Arévalo%2C+Sergio%22">Arévalo, Sergio</searchLink><relatesTo>1</relatesTo><i> sergio.arevalo@eui.upm.es</i><br /><searchLink fieldCode="AR" term="%22Herrera%2C+Carlos%22">Herrera, Carlos</searchLink><relatesTo>2</relatesTo><i> carlos.herrera@epn.edu.ec</i><br /><searchLink fieldCode="AR" term="%22Tang%2C+Jian%22">Tang, Jian</searchLink><relatesTo>1</relatesTo><i> tjapply@gmail.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Supercomputing%22">Journal of Supercomputing</searchLink>. Oct2015, Vol. 71 Issue 10, p3726-3743. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+system+failure+prevention%22">Computer system failure prevention</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+storage+capacity%22">Computer storage capacity</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+network+reliability%22">Computer network reliability</searchLink><br /><searchLink fieldCode="DE" term="%22Electronic+data+processing%22">Electronic data processing</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In classical distributed systems, each process has a unique identity. Today, new distributed systems have emerged where a unique identity is not always possible to be assigned to each process. For example, in many sensor networks a unique identity is not possible to be included in each device due to its small storage capacity, reduced computational power, or the huge number of devices to be identified. In these cases, we have to work with anonymous distributed systems where processes cannot be identified. Consensus cannot be solved in classical and anonymous asynchronous distributed systems where processes can crash. To bypass this impossibility result, failure detectors are added to these systems. It is known that $$\varOmega $$ is the weakest failure detector class for solving consensus in classical asynchronous systems when a majority of processes never crashes. Although $${ A }\varOmega $$ was introduced as an anonymous version of $$\varOmega ,$$ to find the weakest failure detector in anonymous systems to solve consensus when a majority of processes never crashes is nowadays an open question. Furthermore, $${ A }\varOmega $$ has the important drawback that it is not implementable. Very recently, $${ A }\varOmega '$$ has been introduced as a counterpart of $$\varOmega $$ for anonymous systems. In this paper, we show that the $${ A }\varOmega '$$ failure detector class is strictly weaker than $${ A }\varOmega $$ (i.e., $${ A }\varOmega '$$ provides less information about process crashes than $${ A }\varOmega $$ ). We also present in this paper the first implementation of $${ A }\varOmega '$$ (hence, we also show that $${ A }\varOmega '$$ is implementable), and, finally, we include the first implementation of consensus in anonymous asynchronous systems augmented with $${ A }\varOmega '$$ and where a majority of processes does not crash. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Supercomputing is the property of Springer Nature 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=109475503
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s11227-015-1460-6
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 3726
    Subjects:
      – SubjectFull: Distributed computing
        Type: general
      – SubjectFull: Computer system failure prevention
        Type: general
      – SubjectFull: Computer storage capacity
        Type: general
      – SubjectFull: Computer network reliability
        Type: general
      – SubjectFull: Electronic data processing
        Type: general
    Titles:
      – TitleFull: Eventual election of multiple leaders for solving consensus in anonymous systems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Jiménez, Ernesto
      – PersonEntity:
          Name:
            NameFull: Arévalo, Sergio
      – PersonEntity:
          Name:
            NameFull: Herrera, Carlos
      – PersonEntity:
          Name:
            NameFull: Tang, Jian
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2015
              Type: published
              Y: 2015
          Identifiers:
            – Type: issn-print
              Value: 09208542
          Numbering:
            – Type: volume
              Value: 71
            – Type: issue
              Value: 10
          Titles:
            – TitleFull: Journal of Supercomputing
              Type: main
ResultId 1