SHARING MEMORY WITH SEMI-BYZANTINE CLIENTS AND FAULTY STORAGE SERVERS
Abstract
This paper presents fault-tolerant simulations of a single-writer multi-reader regular register in storage systems. One simulation tolerates fail-stop failures of storage servers and requires a majority of nonfaulty servers, while the other simulation tolerates Byzantine failures and assumes that two-thirds of the servers are nonfaulty. A construction of Afek et al. [3] is used to mask semi-Byzantine failures of clients that result in erroneous write operations. The simulations are used to derive Paxos algorithms that tolerate semi-Byzantine failures of clients as well as fail-stop or Byzantine failures of storage servers.
A preliminary version of this paper appeared in the 22nd IEEE Symposium on Reliable Distributed Systems (SRDS '03), October 2003, pp. 371-378.
References
- Distributed Computing 18, 387 (2006), DOI: 10.1007/s00446-005-0151-6. Crossref, ISI, Google Scholar
A. Acharya , M. Uysal and J. H. Saltz , Active disks: Programming model, algorithms and evaluation,Architectural Support for Programming Languages and Operating Systems (1998) pp. 81–91. Google Scholar- Journal of the ACM 42, 1231 (1995), DOI: 10.1145/227683.227688. Crossref, ISI, Google Scholar
- Journal of the ACM 42, 124 (1995), DOI: 10.1145/200836.200869. Crossref, ISI, Google Scholar
- Journal of the ACM 32, 824 (1985), DOI: 10.1145/4221.214134. Crossref, ISI, Google Scholar
- ACM Trans. Comput. Syst. 20, 398 (2003), DOI: 10.1145/571637.571640. Crossref, ISI, Google Scholar
- Distributed Computing 18, 73 (2002), DOI: 10.1007/s00446-005-0123-x. Crossref, ISI, Google Scholar
- Journal of the ACM 32, 374 (1985), DOI: 10.1145/3149.214121. Crossref, ISI, Google Scholar
E. Gafni and L. Lamport , Disk paxos, International Symposium on Distributed Computing (2000) pp. 330–344. Google Scholar- Distributed Computing 16, 1 (2003), DOI: 10.1007/s00446-002-0070-8. Crossref, ISI, Google Scholar
- Communications of the ACM 17, 453 (1974), DOI: 10.1145/361082.361093. Crossref, ISI, Google Scholar
- Distributed Computing 1, 77 (1986), DOI: 10.1007/BF01786227. Crossref, ISI, Google Scholar
- ACM Transactions on Computer Systems 16, 133 (1998), DOI: 10.1145/279227.279229. Crossref, ISI, Google Scholar
- ACM Trans. on Prog. Lang. and Sys. 4, 382 (1982), DOI: 10.1145/357172.357176. Crossref, ISI, Google Scholar
- Distributed Computing 16, 37 (2003), DOI: 10.1007/s00446-002-0075-3. Crossref, ISI, Google Scholar
- Distributed Computing 11, 203 (1998), DOI: 10.1007/s004460050050. Crossref, ISI, Google Scholar
- J.-P. Martin, L. Alvisi, and M. Dahlin, Minimal Byzantine storage, Technical Report TR-02-38, University of Texas at Austin, Department of Computer Sciences, August 2002 . Google Scholar
-
B. Oki and B. Liskov , Viewstamped replication: A new primary copy method to support highly available distributed systems , Proc. 7th ACM Symposium on Principles of Distributed Computing ( 1988 ) . Google Scholar - IEEE Computer 34, 68 (2001). Crossref, ISI, Google Scholar
- SNIA, Storage networking industry association, http://www.snia.org/ . Google Scholar


