Practical Byzantine Fault Tolerance

Miguel Castro, Barbara Liskov, 1999, OSDI

About this paper

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Tiếng Việt
English

Khả năng chịu lỗi Byzantine thực tế

Miguel Castro và Barbara Liskov Phòng thí nghiệm Khoa học Máy tính, Viện Công nghệ Massachusetts, 545 Technology Square, Cambridge, MA 02139 {castro,liskov}@lcs.mit.edu

Tóm tắt Bài báo này mô tả một thuật toán sao chép mới có khả năng chịu được các sự cố Byzantine. Chúng tôi tin rằng các thuật toán chịu sự cố Byzantine sẽ ngày càng trở nên quan trọng trong tương lai vì các cuộc tấn công độc hại và lỗi phần mềm ngày càng phổ biến, đồng thời có thể khiến các nút bị lỗi thể hiện hành vi tùy ý. Trong khi các thuật toán trước đây giả định một hệ thống đồng bộ hoặc quá chậm để được sử dụng trong thực tế, thuật toán được mô tả trong bài báo này mang tính thực tiễn: nó hoạt động trong các môi trường không đồng bộ như Internet và tích hợp một số tối ưu hóa quan trọng giúp cải thiện thời gian đáp ứng của các thuật toán trước đây hơn một bậc độ lớn. Chúng tôi đã triển khai một dịch vụ NFS chịu sự cố Byzantine bằng cách sử dụng thuật toán của mình và đo hiệu năng của nó. Kết quả cho thấy dịch vụ của chúng tôi chỉ chậm hơn 3% so với một NFS chuẩn không sao chép.

Appears in the Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, USA, February 1999

Practical Byzantine Fault Tolerance

Miguel Castro and Barbara Liskov Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139 {castro,liskov}@lcs.mit.edu

Abstract

This paper describes a new replication algorithm that is able to tolerate Byzantine faults. We believe that Byzantine-fault-tolerant algorithms will be increasingly important in the future because malicious attacks and software errors are increasingly common and can cause faulty nodes to exhibit arbitrary behavior. Whereas previous algorithms assumed a synchronous system or were too slow to be used in practice, the algorithm described in this paper is practical: it works in asynchronous environments like the Internet and incorporates several important optimizations that improve the response time of previous algorithms by more than an order of magnitude. We implemented a Byzantine-fault-tolerant NFS service using our algorithm and measured its performance. The results show that our service is only 3% slower than a standard unreplicated NFS.

This section is missing here.

1 Introduction

This section is missing here.

2 System Model

This section is missing here.

3 Service Properties

This section is missing here.

4 The Algorithm

This section is missing here.

5 Optimizations

This section is missing here.

6 Implementation

This section is missing here.

7 Performance Evaluation

This section is missing here.

8 Related Work

This section is missing here.

9 Conclusions

This section is missing here.

Acknowledgments

References

  1. M. Bellare and D. Micciancio. A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost. In Advances in Cryptology – Eurocrypt 97, 1997.
  2. G. Bracha and S. Toueg. Asynchronous Consensus and Broadcast Protocols. Journal of the ACM, 32(4), 1995.
  3. R. Canneti and T. Rabin. Optimal Asynchronous Byzantine Agreement. Technical Report #92-15, Computer Science Department, Hebrew University, 1992.
  4. M. Castro and B. Liskov. A Correctness Proof for a Practical Byzantine-Fault-Tolerant Replication Algorithm. Technical Memo MIT/LCS/TM-590, MIT Laboratory for Computer Science, 1999.
  5. M. Castro and B. Liskov. Authenticated Byzantine Fault Tolerance Without Public-Key Cryptography. Technical Memo MIT/LCS/TM-589, MIT Laboratory for Computer Science, 1999.
  6. F. Cristian, H. Aghili, H. Strong, and D. Dolev. Atomic Broadcast: From Simple Message Diffusion to Byzantine Agreement. In International Conference on Fault Tolerant Computing, 1985.
  7. S. Deering and D. Cheriton. Multicast Routing in Datagram Internetworks and Extended LANs. ACM Transactions on Computer Systems, 8(2), 1990.
  8. H. Dobbertin. The Status of MD5 After a Recent Attack. RSA Laboratories’ CryptoBytes, 2(2), 1996.
  9. M. Fischer, N. Lynch, and M. Paterson. Impossibility of Distributed Consensus With One Faulty Process. Journal of the ACM, 32(2), 1985.
  10. J. Garay and Y. Moses. Fully Polynomial Byzantine Agreement for n > 3t Processors in t+1 Rounds. SIAM Journal of Computing, 27(1), 1998.
  11. D. Gawlick and D. Kinkade. Varieties of Concurrency Control in IMS/VS Fast Path. Database Engineering, 8(2), 1985.
  12. D. Gifford. Weighted Voting for Replicated Data. In Symposium on Operating Systems Principles, 1979.
  13. M. Herlihy and J. Tygar. How to make replicated data secure. Advances in Cryptology (LNCS 293), 1988.
  14. M. Herlihy and J. Wing. Axioms for Concurrent Objects. In ACM Symposium on Principles of Programming Languages, 1987.
  15. J. Howard et al. Scale and performance in a distributed file system. ACM Transactions on Computer Systems, 6(1), 1988.
  16. K. Kihlstrom, L. Moser, and P. Melliar-Smith. The SecureRing Protocols for Securing Group Communication. In Hawaii International Conference on System Sciences, 1998.
  17. L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM, 21(7), 1978. Read it here
  18. L. Lamport. The Part-Time Parliament. Technical Report 49, DEC Systems Research Center, 1989.
  19. L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), 1982.
  20. B. Liskov et al. Replication in the Harp File System. In ACM Symposium on Operating System Principles, 1991.
  21. N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, 1996.
  22. D. Malkhi and M. Reiter. A High-Throughput Secure Reliable Multicast Protocol. In Computer Security Foundations Workshop, 1996.
  23. D. Malkhi and M. Reiter. Byzantine Quorum Systems. In ACM Symposium on Theory of Computing, 1997.
  24. D. Malkhi and M. Reiter. Unreliable Intrusion Detection in Distributed Computations. In Computer Security Foundations Workshop, 1997.
  25. D. Malkhi and M. Reiter. Secure and Scalable Replication in Phalanx. In IEEE Symposium on Reliable Distributed Systems, 1998.
  26. B. Oki and B. Liskov. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In ACM Symposium on Principles of Distributed Computing, 1988.
  27. B. Preneel and P. Oorschot. MDx-MAC and Building Fast MACs from Hash Functions. In Crypto 95, 1995.
  28. C. Pu, A. Black, C. Cowan, and J. Walpole. A Specialization Toolkit to Increase the Diversity of Operating Systems. In ICMAS Workshop on Immunity-Based Systems, 1996.
  29. M. Reiter. Secure Agreement Protocols. In ACM Conference on Computer and Communication Security, 1994.
  30. M. Reiter. The Rampart Toolkit for Building High-Integrity Services. Theory and Practice in Distributed Systems (LNCS 938), 1995.
  31. M. Reiter. A Secure Group Membership Protocol. IEEE Transactions on Software Engineering, 22(1), 1996.
  32. R. Rivest. The MD5 Message-Digest Algorithm. Internet RFC-1321, 1992.
  33. R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 1978. Read it here
  34. F. Schneider. Implementing Fault-Tolerant Services Using The State Machine Approach: A Tutorial. ACM Computing Surveys, 22(4), 1990.
  35. A. Shamir. How to share a secret. Communications of the ACM, 22(11), 1979.
  36. G. Tsudik. Message Authentication with One-Way Hash Functions. ACM Computer Communications Review, 22(5), 1992.
  37. M. Wiener. Performance Comparison of Public-Key Cryptosystems. RSA Laboratories’ CryptoBytes, 4(1), 1998.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 6. Translated from the English.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.