Abstract
The increasing popularity of distributed systems and applications has generated the need for algorithms guaranteeing high availability and reliability of such solutions. As an answer to this demand, various Byzantine fault-tolerant algorithms have been designed, allowing the systems to provide the correct service even in the presence of faults, either accidental or of malicious origin. However, despite significant efforts recently made, their practicality is still limited by many factors, such as the cost of additional machines or decreased system throughput. Addressing these issues, we propose Apex, a parallel Byzantine fault-tolerant execution algorithm. By processing independent requests in parallel on different multicore machines, we were able to obtain a significant increase in throughput over traditional algorithms. The performed tests have shown that our approach can execute the incoming packs of requests even several times faster than other similar algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Avizienis, A., Laprie, J.-C., Randell, B., Landwehr, C.: Basic concepts and taxonomy of dependable and secure computing. IEEE Trans. Dependable Secur. Comput. 1(1), 11–33 (2004)
Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI’99. USENIX Association, Berkeley, pp. 173–186 (1999)
Chun, B.-C., Maniatis, P., Shenker, S., Kubiatowicz, J.: Attested append-only memory: making adversaries stick to their word. In: Proceedings of the 21st Symposium on Operating Systems Principles (2007)
Correia, M., Neves, N.F., Veríssimo, P.: How to tolerate half less one Byzantine nodes in practical distributed systems. In: Proceedings of the 23rd IEEE Symposium on Reliable Distributed Systems, pp. 174–183, October 2004
Distler, T., Kapitza, R.: Increasing performance in Byzantine fault-tolerant systems with on-demand replica consistency. In: Proceedings of the EuroSys 2011 Conference (EuroSys’11), pp. 91–105 (2011)
Distler, T., Kapitza, R., Popov, I., Reiser, H.P., Schröder-Preikschat, W.: SPARE: replicas on hold. In: Proceedings of the 18th Network and Distributed System Security Symposium (NDSS ’11), pp. 407–420, (2011)
Gawkowski, P., Sosnowski, J.: Dependability evaluation with fault injection experiments. IEICE Trans. Inf. Syst. E86-D(12), 2642–2649 (2003)
Google. App engine outage today, p. 6 (2008). https://groups.google.com/forum/?fromgroups=#!topic/google-appengine/985VmzuLMDs
Hendricks, J., Sinnamohideen, S., Ganger, G.R., Reiter, M.K.: Zzyzx: Scalable fault tolerance through byzantine locking. In: 2010 IEEE/IFIP International Conference on, Dependable Systems and Networks (DSN), pp. 363–372 (2010)
Huang, A.C., Fox, A.: Cheap recovery: a key to self-managing state. ACM Trans. Storage 1(1), 38–70 (2005)
Knight, J.: Fundamentals of Dependable Computing for Software Engineers. Boca Raton, CRC Press, (2012)
Kotla, R., Clement, A., Wong, E., Alvisi, L., Dahlin, M.: Zyzzyva: speculative Byzantine fault tolerance. In: Symposium on Operating Systems Principles (SOSP) (2007)
Kotla, R., Dahlin, M.: High throughput Byzantine fault tolerance. In: Proceedings of the 2004 Conference on Dependable Systems and Networks, pp. 575–584 (2004)
Ladin, R., Liskov, B., Shrira, L., Ghemawat, S.: Providing high availability using lazy replication. ACM Trans. Comput. Syst. 10(4), 360–391 (1992)
Lamport, L.: From Byzantine generals to hackers, p. 5 (2011), http://www.college-de-france.fr/site/martin-abadi/seminar-2011-05-11-11h00-resume.htm
Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Progra. Lang. Syst. 4, 382–401 (1982)
Liskov, B., Ghemawat, S., Gruber, R., Johnson, P., Shrira, L.: Replication in the Harp file system. In: Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, SOSP ’91, pp. 226–238, ACM. New York (1991)
Osier, M.: Shipping delay recap, p. 8 (2008), http://blog.netflix.com/2008/08/shipping-delay-recap.html
Pâris, J.-F.: Voting with witnesses: a consistency scheme for replicated files. In: Proceedings of the 6th International Conference on Distributed Computing Systems, pp. 3–6 (1986)
Urbán, P., Défago, X., Schiper, A.: Neko: A single environment to simulate and prototype distributed algorithms. J. Inf. Sci. Eng. 18(6), 981–997 (2002)
Veronese, G.S., Correia, M., Bessani, A.N., Lung, L.C., Verissimo, P., Efficient Byzantine fault tolerance. IEEE Trans. Comput. p. 99 (2011)
Wood, T., Singh, R., Venkataramani, A., Shenoy, P., Cecchet, E.: ZZ and the art of practical BTF execution. In: Proceedings of the sixth conference on Computer systems, EuroSys’11, pp. 123–138 (2011)
Yin, J., Martin, J.-P., Venkataramani, A., Alvisi, L., Dahlin, M.: Separating agreement from execution for Byzantine fault tolerant services. In: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, pp. 253–267, ACM Press (2003)
Zbierski, M., Iwazaru: The Byzantine sequencer. In: Proceedings of the 26th International Conference on Architecture of Computing Systems, pp. 38–49 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Zbierski, M. (2015). Parallel Byzantine Fault Tolerance. In: Wiliński, A., Fray, I., Pejaś, J. (eds) Soft Computing in Computer and Information Science. Advances in Intelligent Systems and Computing, vol 342. Springer, Cham. https://doi.org/10.1007/978-3-319-15147-2_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-15147-2_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15146-5
Online ISBN: 978-3-319-15147-2
eBook Packages: EngineeringEngineering (R0)