Exact Byzantine Consensus on Undirected Graphs: Local Broadcast Model
This research focuses on achieving exact Byzantine consensus on undirected graphs under the local broadcast model, where communication is synchronous with known underlying graphs. The model reduces the power of Byzantine nodes and imposes connectivity requirements. The algorithm involves flooding values and identifying the output value based on byzantine nodes. The hybrid model introduces varying connectivity based on the number of equivocating nodes. Efficient algorithms are proposed for achieving at least 2f connectivity. Overall, while the model is interesting, the solutions may appear repetitive yet beneficial due to network topology awareness.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model Authors: Muhammad Samir Khan , Syed Shalan Naqvi , and Nitin H. Vaidya Presentation by Joseph Oglio
Setting Synchronous communication Undirected underlying communication graph known to all nodes FIFO channels Local Broadcast model
Local Broadcast model A message sent by a node is received identically by all of it s neighbors This reduces the power of byzantine nodes as they can no longer equivocate This results in a 3/2f + 1 connectivity requirement as opposed to the standard 2f + 1. Degree is also required to be no less than 2f.
Algorithm All nodes flood their values a number of times equal to the number of combinations of possible byzantine nodes - F Every nodes received value is calculated for the round by calculating a single route from u to v excluding the current F. Zv 0 Nv 1 Once all combinations are exhausted output gamma
Hybrid Model Some number of byzantine nodes t may equivocate This condition changes the minimum connectivity of the network by imposing these conditions For t = f and t = 0 the conditions reduce to 3f + 1 and 2f + 1 (the same as the point to point and local broadcast models respectively)
Efficient Algorithm for connectivity at least 2f Flood values Flood heard values, find 2f disjoint paths and identify byzantine nodes to determine the output value Flood the output value for nodes who couldn t identify all the byzantine nodes
Thoughts Model is interesting but the solutions do seem a little boring Knowing the network topology helps a lot Solutions are very similar to the standard dolev algorithms
