English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The implementation of registers from (potentially) weaker registers is aclassical problem in the theory of distributed computing. Since Lamport'spioneering work [13], this problem has been extensively studied in the contextof asynchronous processes with crash failures. In this paper, we investigatethis problem in the context of Byzantine process failures, with and withoutprocess signatures.  We first prove that, without signatures, there is no wait-free linearizableimplementation of a 1-writer n-reader register from atomic 1-writer 1-readerregisters. In fact, we show a stronger result, namely, even under theassumption that the writer can only crash and at most one reader can bemalicious, there is no linearizable implementation of a 1-writer n-readerregister from atomic 1-writer (n-1)-reader registers that ensures that everycorrect process eventually completes its operations. In light of thisimpossibility result, we give two implementations of a 1-writer n-readerregister from atomic 1-writer 1-reader registers that work under differentassumptions. The first implementation is linearizable (under any combination ofprocess failures), but it guarantees that every correct process eventuallycompletes its operations only under the assumption that the writer is corrector no reader is malicious -- thus matching the impossibility result. The secondimplementation assumes process signatures; it is bounded wait-free andlinearizable under any combination of process failures. Finally, we show thatwithout process signatures, even if we assume that the writer is correct and atmost one of the readers can be malicious, it is impossible to guarantee thatevery correct reader completes each read operation in a bounded number ofsteps.

On implementing SWMR registers from SWSR registers in systems with Byzantine failures