Asynchronous Byzantine Agreement in Incomplete Networks

This discussion delves into the concept of Asynchronous Byzantine Agreement in the context of incomplete networks, analyzing the challenges and solutions proposed by Ye Wang and Roger Wattenhofer from ETH Zurich's Distributed Computing department. The images and scenarios presented shed light on the complexities of achieving agreement in such network configurations.

• Asynchronous Byzantine
• Incomplete Networks
• Distributed Computing
• ETH Zurich
• Network Complexity

shawley_r Follow

Uploaded on Mar 04, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Asynchronous Byzantine Agreement in Incomplete Networks Ye Wang and Roger Wattenhofer ETH Zurich ETH Zurich Distributed Computing www.disco.ethz.ch

2. Send Message from Zurich to New York Ye@Zurich AFT@New York

3. Send Message from Zurich to New York Basel Paris Ye@Zurich London AFT@New York

4. Incomplete Network

5. Incomplete Network

6. Byzantine Agreement in Incomplete Networks

7. Byzantine Agreement in Incomplete Networks

8. Byzantine Agreement in Incomplete Networks

9. Byzantine Agreement in Incomplete Networks

10. Byzantine Agreement in Incomplete Networks

11. Byzantine Agreement in Incomplete Networks

12. Byzantine Agreement in Incomplete Networks

13. Asynchronous Byzantine Agreement in Incomplete Networks An undirected network ? with ? nodes, where ? nodes are Byzantine.

14. Asynchronous Byzantine Agreement in Incomplete Networks Necessary & Sufficient Conditions for Asynchronous Byzantine Agreement ? is 2? + 1 connected

15. Hierarchy of the Algorithms Byzantine Agreement Algorithm Byzantine Reliable Broadcast Message Delivery in Incomplete Networks

16. Hierarchy of the Algorithms Byzantine Agreement Algorithm Byzantine Reliable Broadcast Message Delivery in Incomplete Networks

17. Sufficient Condition sender ? intermediate ? receiver ?

18. Sufficient Condition 2? + 1 Disjoint paths

19. Sufficient Condition sender ? intermediate ? receiver ?

20. Asynchronous Byzantine Agreement in Incomplete Networks An undirected network ? with ? nodes, where ? nodes are Byzantine. Necessary & Sufficient Conditions for Asynchronous Byzantine Agreement ? is 2? + 1 connected

21. Necessary Condition If the connectivity of ? is smaller than 2? + 1 ? ? ? ? ? ? ? ?

22. Necessary Condition If the connectivity of ? is smaller than 2? + 1 ? ? ? ?

23. Necessary Condition If the connectivity of ? is smaller than 2? + 1 ?0 ?1 ? ?1 ?0 ?1 ?0 ? ? ?0 ?1 ?

24. Necessary Condition If the connectivity of ? is smaller than 2? + 1 ?0 ?1 ?0 ?1 ?0 ?1 ?0 ?1 ?0 ?0 ?0 ?1 ?0

25. Necessary Condition If the connectivity of ? is smaller than 2? + 1 ?0 ?1 ?1 ?0 ?1 ?1 ?0 ?1 ?0 ?1 ?0 ?1 ?1

26. Necessary Condition If the connectivity of ? is smaller than 2? + 1 ?0 ?1 ?0 ?0 ?1 ?1 ?0 ?1 ?1 ?0 ?0 ?1 ?1

27. Byzantine Agreement in Incomplete Networks

28. Thanks! Questions & Comments? ETH Zurich Distributed Computing www.disco.ethz.ch