river-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From p...@apache.org
Subject svn commit: r1085629 - in /river/jtsk/skunk/patsFaultTolerance: annotated_bibliography.pdf annotated_bibliography.tex raw_bibliography.bib
Date Sat, 26 Mar 2011 02:36:30 GMT
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}
+}



Mime
View raw message