Tight Bounds for Shared Memory Systems Accessed by Byzantine Processes

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.. We show that sticky bits are universal in the Byzantine failure model for n \ge 3t+1, and improvement over the previous result requiring n \ge (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 \ge 3t+1, the best possible bound on n for strong consensus. We also present tight bounds on the efficiency of implementations of strong consensys objects from sticky bits and similar primitive objects.

Back to publications
Back to previous page