id:"swepub:oai:research.chalmers.se:16a25867-d16f-494a-b4eb-c5c98c6f4a12"
Search: id:"swepub:oai:research.chalmers.se:16a25867-d16f-494a-b4eb-c5c98c6f4a12" > Loosely-self-stabil...
- 1 of 1
- Previous record
- Next record
- To hitlist
Loosely-self-stabilizing Byzantine-Tolerant Binary Consensus for Signature-Free Message-Passing Systems
-
- Georgiou, C. (author)
- University of Cyprus
-
- Marcoullis, I. (author)
- University of Cyprus
-
- Raynal, Michel (author)
- Hong Kong Polytechnic University,Université de Rennes 1,University of Rennes 1
- show more...
- show less...
- (creator_code:org_t)
- 2021-12-02
- 2021
- English.
- In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 12754 LNCS, s. 36-53
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- At PODC 2014, A. Mostéfaoui, H. Moumen, and M. Raynal presented a new and simple randomized signature-free binary consensus algorithm (denoted here as MMR) that copes with the net effect of asynchrony and Byzantine behaviors. Assuming message scheduling is fair and independent from random numbers, MMR is optimal in several respects: it deals with up to t Byzantine processes, where t< n/ 3, n being the number of processes, O(n2) messages, and O(1 ) expected time. The present article presents a non-trivial extension of MMR to an even more fault-prone context, namely, in addition to Byzantine processes, it considers also that the system can experience transient failures. To this end it considers self-stabilization techniques to cope with communication failures and arbitrary transient faults, i.e., any violation of the assumptions according to which the system was designed to operate. The proposed algorithm is the first loosely-self-stabilizing Byzantine fault-tolerant binary consensus algorithm suited to asynchronous message-passing systems. This is achieved via an instructive transformation of MMR to a loosely-self-stabilizing solution that can violate safety requirements with probability Pr = O(1 / (2 M) ), where M is a predefined constant that can be set to any positive integer at the cost of 3 Mn+ log M bits of local memory. In addition to making MMR resilient to transient faults, the obtained loosely-self-stabilizing algorithm preserves its properties of optimal resilience and termination, i.e., t< n/ 3 and O(1 ) expected time. Furthermore, it only requires a bounded amount of memory.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Engineering (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Inbäddad systemteknik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Embedded Systems (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Self-stabilization
- Binary consensus
- Byzantine fault-tolerance
Publication and Content Type
- kon (subject category)
- ref (subject category)
Find in a library
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artifici... (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Georgiou, C.
- Marcoullis, I.
- Raynal, Michel
- Schiller, Elad, ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Enginee ...
-
- ENGINEERING AND TECHNOLOGY
- ENGINEERING AND ...
- and Electrical Engin ...
- and Embedded Systems
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Lecture Notes in ...
- By the university
- Chalmers University of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
