Tight bounds for shared memory systems accessed by Byzantine processes

Noga Alon, Michael Merritt, Omer Reingold, Gadi Taubenfeld, Rebecca N. Wright

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine failures, in a model previously explored by Malkhi et al. [21]. We show that sticky bits are universal in the Byzantine failure model for n ≥ 3t + 1, an improvement over the previous result requiring n ≥ (2t + 1)(t + 1). Our result follows from a new strong consensus construction that uses sticky bits and tolerates t Byzantine failures among n processes for any n ≥ 3t + 1, the best possible bound on n for strong consensus. We also present tight bounds on the efficiency of implementations of strong consensus objects from sticky bits and similar primitive objects.

Original languageEnglish (US)
Pages (from-to)99-109
Number of pages11
JournalDistributed Computing
Volume18
Issue number2
DOIs
StatePublished - Nov 1 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Keywords

  • Byzantine agreement
  • Distributed consensus
  • Shared memory
  • Sticky bits

Fingerprint Dive into the research topics of 'Tight bounds for shared memory systems accessed by Byzantine processes'. Together they form a unique fingerprint.

  • Cite this