Loosely-self-stabilizing Byzantine-Tolerant Binary Consensus for Signature-Free Message-Passing Systems

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Sökning: id:"swepub:oai:research.chalmers.se:16a25867-d16f-494a-b4eb-c5c98c6f4a12" > Loosely-self-stabil...

1 av 1
Föregående post
Nästa post
Till träfflistan

Georgiou, C.University of Cyprus (författare)

Loosely-self-stabilizing Byzantine-Tolerant Binary Consensus for Signature-Free Message-Passing Systems

Artikel/kapitelEngelska2021

Förlag, utgivningsår, omfång ...

2021-12-02
Cham :Springer International Publishing,2021

Nummerbeteckningar

LIBRIS-ID:oai:research.chalmers.se:16a25867-d16f-494a-b4eb-c5c98c6f4a12
https://research.chalmers.se/publication/528009URI
https://doi.org/10.1007/978-3-030-91014-3_3DOI

Kompletterande språkuppgifter

Språk:engelska
Sammanfattning på:engelska

Ingår i deldatabas

SwePubSwePub

Klassifikation

Ämneskategori:kon swepub-publicationtype
Ämneskategori:ref swepub-contenttype

Anmärkningar

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.

Ämnesord och genrebeteckningar

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
Self-stabilization
Binary consensus
Byzantine fault-tolerance

Biuppslag (personer, institutioner, konferenser, titlar ...)

Marcoullis, I.University of Cyprus (författare)
Raynal, MichelHong Kong Polytechnic University,Université de Rennes 1,University of Rennes 1 (författare)
Schiller, Elad,1974Chalmers tekniska högskola,Chalmers University of Technology(Swepub:cth)elad (författare)
University of CyprusHong Kong Polytechnic University (creator_code:org_t)

Sammanhörande titlar

Ingår i:Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Cham : Springer International Publishing12754 LNCS, s. 36-531611-33490302-9743

Internetlänk

Hitta via bibliotek

Lecture Notes in Computer Science (including subseries Lecture Notes in Artifici... (Sök värdpublikationen i LIBRIS)

Till lärosätets databas

1 av 1
Föregående post
Nästa post
Till träfflistan

Hitta mer i SwePub

Av författaren/redakt...: Georgiou, C.; Marcoullis, I.; Raynal, Michel; Schiller, Elad, ...

Om ämnet

NATURVETENSKAP: NATURVETENSKAP; och Data och informa ...; och Datorteknik

TEKNIK OCH TEKNOLOGIER: TEKNIK OCH TEKNO ...; och Elektroteknik oc ...; och Inbäddad systemt ...

NATURVETENSKAP: NATURVETENSKAP; och Data och informa ...; och Datavetenskap

Artiklar i publikationen: Lecture Notes in ...

Av lärosätet: Chalmers tekniska högskola

Sök utanför SwePub

Sök vidare i:: Google; 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.

LIBRIS.kb.se