Tight Bounds for Shared Memory Systems Accessed by Byzantine
Processes
Rebecca Wright
Stevens Institute of Technology
Friday, October 4, 2:00PM
Lieb 3rd floor Conference Room
Abstract
We provide efficient constructions and strong lower bounds for shared
memory systems accessed by n processes, up to t of which may exhibit
Byzantine faults, in a model previously explored by Malkhi et
al. (DISC 2000). We show that sticky bits are universal in the
Byzantine failure model provided n is at least 3t+1, an improvement
over the previous result requiring n to be at least (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. (This is 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.
This is joint work with Michael Merritt, Omer Reingold, and Gadi
Taubenfeld, and will be appearing in DISC '02.