Author: pats
Date: Sat Mar 26 02:36:29 2011
New Revision: 1085629
URL: http://svn.apache.org/viewvc?rev=1085629&view=rev
Log:
Added a paper on Byzantine fault tolerance.
Modified:
river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.pdf
river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.tex
river/jtsk/skunk/patsFaultTolerance/raw_bibliography.bib
Modified: river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.pdf
URL:
http://svn.apache.org/viewvc/river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.pdf?rev=1085629&r1=1085628&r2=1085629&view=diff
==============================================================================
Binary files - no diff available.
Modified: river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.tex
URL:
http://svn.apache.org/viewvc/river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.tex?rev=1085629&r1=1085628&r2=1085629&view=diff
==============================================================================
--- river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.tex (original)
+++ river/jtsk/skunk/patsFaultTolerance/annotated_bibliography.tex Sat Mar 26
02:36:29 2011
@@ -23,12 +23,35 @@
\section{Transactions}
+\subsection{A survey on the history of transaction management: from flat to
grid transactions}
+
In ``A survey on the history of transaction management: from flat to grid
transactions'',
Wang et. al. discuss the development of transaction systems
from the ``Stone Age'' before the use of transactions through early 21st.
century grid
computing \cite{Wang:2008:SHT:1371053.1371077}. This article is useful
for high level background, terminology, and citations. It does not discuss
implementation, algorithms, or protocols.
+\section{Fault Tolerant State Machines}
+
+A fault tolerant state machine could be used as the basis for either
transactions or JavaSpace. It provides a general mechanism for having multiple
servers collectively carry out client requests with the ability to continue
functioning after some subset has failed, and introducing or reintroducing
computers to bring the system back to full strength.
+
+\subsection{From Viewstamped Replication to Byzantine Fault Tolerance}
+
+Barbar Liskov describes two implementations in ``From Viewstamped Replication
to Byzantine Fault Tolerance'' \cite{DBLP:conf/replication/Liskov10}. The
earlier implementation, Viewstamped Replication, was designed to protect
against simple failures in which a server stops responding. It was later
extended to handle Byzantine failures, in which a server or its communication
paths may be under the control of a malicious agent attempting to subvert or
disrupt the application.
+
+The last paragraph of the article mentions several subsequent developments
with references:
+
+\begin{itemize}
+ \item Techniques for heterogeneous
+replication to avoid the problem of correlated failures causing many replicas
to fail
+simultaneously \cite{Castro:2003:BUA:859716.859718,HRDB-SOSP}.
+ \item Study of system properties when more than f replicas fail
+simultaneously \cite{DBLP:conf/nsdi/LiM07}.
+ \item Avoiding the use of a primary, either entirely or during normal
+case processing
\cite{Abd-El-Malek:2005:FBF:1095809.1095817,DBLP:conf/osdi/CowlingMLRS06}.
+ \item Reducing the latency of normal case processing
\cite{DBLP:conf/sosp/KotlaADCW07,DBLP:conf/nsdi/WesterCNCFL09}.[12, 33]
+\end{itemize}
+
\bibliographystyle{alpha}
\bibliography{raw_bibliography}
Modified: river/jtsk/skunk/patsFaultTolerance/raw_bibliography.bib
URL:
http://svn.apache.org/viewvc/river/jtsk/skunk/patsFaultTolerance/raw_bibliography.bib?rev=1085629&r1=1085628&r2=1085629&view=diff
==============================================================================
--- river/jtsk/skunk/patsFaultTolerance/raw_bibliography.bib (original)
+++ river/jtsk/skunk/patsFaultTolerance/raw_bibliography.bib Sat Mar 26
02:36:29 2011
@@ -17,3 +17,200 @@
keywords = {Grid transaction, Historic survey, Transaction management,
Transaction model, Web services transaction, Workflow transaction},
}
+@inproceedings{DBLP:conf/replication/Liskov10,
+ author = {Barbara Liskov},
+ title = {From Viewstamped Replication to Byzantine Fault Tolerance},
+ booktitle = {Replication},
+ year = {2010},
+ pages = {121-149},
+ ee = {http://dx.doi.org/10.1007/978-3-642-11294-2_7},
+ crossref = {DBLP:conf/replication/2010},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@proceedings{DBLP:conf/replication/2010,
+ editor = {Bernadette Charron-Bost and
+ Fernando Pedone and
+ Andr{\'e} Schiper},
+ title = {Replication: Theory and Practice},
+ booktitle = {Replication},
+ publisher = {Springer},
+ series = {Lecture Notes in Computer Science},
+ volume = {5959},
+ year = {2010},
+ isbn = {978-3-642-11293-5},
+ ee = {http://dx.doi.org/10.1007/978-3-642-11294-2},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@article{Castro:2003:BUA:859716.859718,
+ author = {Castro, Miguel and Rodrigues, Rodrigo and Liskov, Barbara},
+ title = {BASE: Using abstraction to improve fault tolerance},
+ journal = {ACM Trans. Comput. Syst.},
+ volume = {21},
+ issue = {3},
+ month = {August},
+ year = {2003},
+ issn = {0734-2071},
+ pages = {236--269},
+ numpages = {34},
+ url = {http://doi.acm.org/10.1145/859716.859718},
+ doi = {http://doi.acm.org/10.1145/859716.859718},
+ acmid = {859718},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+ keywords = {Byzantine fault tolerance, N-version programming, asynchronous
systems, proactive recovery, state machine replication},
+}
+
+@inproceedings{HRDB-SOSP,
+ author = {Ben Vandiver and Hari Balakrishnan and Barbara Liskov and Sam
+ Madden},
+ title = {Tolerating Byzantine Faults in Database Systems using Commit
+ Barrier Scheduling},
+ booktitle = {Proceedings of the 21st ACM Symposium on Operating Systems
+ Principles (SOSP)},
+ address = {Stevenson, Washington, USA},
+ month = oct,
+ year = {2007}
+}
+
+@inproceedings{DBLP:conf/nsdi/LiM07,
+ author = {Jinyuan Li and
+ David Mazi{\`e}res},
+ title = {Beyond One-Third Faulty Replicas in Byzantine Fault Tolerant
+ Systems},
+ booktitle = {NSDI},
+ year = {2007},
+ ee = {http://www.usenix.org/events/nsdi07/tech/li.html},
+ crossref = {DBLP:conf/nsdi/2007},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@proceedings{DBLP:conf/nsdi/2007,
+ title = {4th Symposium on Networked Systems Design and Implementation
+ (NSDI 2007), April 11-13, 2007, Cambridge, Massachusetts,
+ USA, Proceedings},
+ booktitle = {NSDI},
+ publisher = {USENIX},
+ year = {2007},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@article{Abd-El-Malek:2005:FBF:1095809.1095817,
+ author = {Abd-El-Malek, Michael and Ganger, Gregory R. and Goodson, Garth R.
and Reiter, Michael K. and Wylie, Jay J.},
+ title = {Fault-scalable Byzantine fault-tolerant services},
+ journal = {SIGOPS Oper. Syst. Rev.},
+ volume = {39},
+ issue = {5},
+ month = {October},
+ year = {2005},
+ issn = {0163-5980},
+ pages = {59--74},
+ numpages = {16},
+ url = {http://doi.acm.org/10.1145/1095809.1095817},
+ doi = {http://doi.acm.org/10.1145/1095809.1095817},
+ acmid = {1095817},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+ keywords = {byzantine fault-tolerance, fault-scalability, quorums, replicated
state machines, services},
+}
+
+@inproceedings{Abd-El-Malek:2005:FBF:1095810.1095817,
+ author = {Abd-El-Malek, Michael and Ganger, Gregory R. and Goodson, Garth R.
and Reiter, Michael K. and Wylie, Jay J.},
+ title = {Fault-scalable Byzantine fault-tolerant services},
+ booktitle = {Proceedings of the twentieth ACM symposium on Operating systems
principles},
+ series = {SOSP '05},
+ year = {2005},
+ isbn = {1-59593-079-5},
+ location = {Brighton, United Kingdom},
+ pages = {59--74},
+ numpages = {16},
+ url = {http://doi.acm.org/10.1145/1095810.1095817},
+ doi = {http://doi.acm.org/10.1145/1095810.1095817},
+ acmid = {1095817},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+ keywords = {byzantine fault-tolerance, fault-scalability, quorums, replicated
state machines, services},
+}
+
+@inproceedings{DBLP:conf/osdi/CowlingMLRS06,
+ author = {James A. Cowling and
+ Daniel S. Myers and
+ Barbara Liskov and
+ Rodrigo Rodrigues and
+ Liuba Shrira},
+ title = {HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault
+ Tolerance},
+ booktitle = {OSDI},
+ year = {2006},
+ pages = {177-190},
+ ee = {http://www.usenix.org/events/osdi06/tech/cowling.html},
+ crossref = {DBLP:conf/osdi/2006},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@proceedings{DBLP:conf/osdi/2006,
+ title = {7th Symposium on Operating Systems Design and Implementation
+ (OSDI '06), November 6-8, Seattle, WA, USA},
+ booktitle = {OSDI},
+ publisher = {USENIX Association},
+ year = {2006},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@inproceedings{DBLP:conf/sosp/KotlaADCW07,
+ author = {Ramakrishna Kotla and
+ Lorenzo Alvisi and
+ Michael Dahlin and
+ Allen Clement and
+ Edmund L. Wong},
+ title = {Zyzzyva: speculative byzantine fault tolerance},
+ booktitle = {SOSP},
+ year = {2007},
+ pages = {45-58},
+ ee = {http://doi.acm.org/10.1145/1294261.1294267},
+ crossref = {DBLP:conf/sosp/2007},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@proceedings{DBLP:conf/sosp/2007,
+ editor = {Thomas C. Bressoud and
+ M. Frans Kaashoek},
+ title = {Proceedings of the 21st ACM Symposium on Operating Systems
+ Principles 2007, SOSP 2007, Stevenson, Washington, USA,
+ October 14-17, 2007},
+ booktitle = {SOSP},
+ publisher = {ACM},
+ year = {2007},
+ isbn = {978-1-59593-591-5},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@inproceedings{DBLP:conf/nsdi/WesterCNCFL09,
+ author = {Benjamin Wester and
+ James A. Cowling and
+ Edmund B. Nightingale and
+ Peter M. Chen and
+ Jason Flinn and
+ Barbara Liskov},
+ title = {Tolerating Latency in Replicated State Machines Through
+ Client Speculation},
+ booktitle = {NSDI},
+ year = {2009},
+ pages = {245-260},
+ ee =
{http://www.usenix.org/events/nsdi09/tech/full_papers/wester/wester.pdf},
+ crossref = {DBLP:conf/nsdi/2009},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
+
+@proceedings{DBLP:conf/nsdi/2009,
+ editor = {Jennifer Rexford and
+ Emin G{\"u}n Sirer},
+ title = {Proceedings of the 6th USENIX Symposium on Networked Systems
+ Design and Implementation, NSDI 2009, April 22-24, 2009,
+ Boston, MA, USA},
+ booktitle = {NSDI},
+ publisher = {USENIX Association},
+ year = {2009},
+ bibsource = {DBLP, http://dblp.uni-trier.de}
+}
