Dr. Dobb's Journal - April 2008 - (Page 36)

d04nels_p4ds 2/20/08 1:29 PM Page 36 Core Technology THE BYZANTINE GENERALS PROBLEM Sender = P2 {0,132} {0,142} {1,152} {1,162} {1,172} Sender = P3 {0,123} {0,143} {1,153} {1,163} {1,173} Sender = P4 {0,124} {0,134} {1,154} {1,164} {1,174} Sender = P5 {0,125} {0,135} {0,145} {1,165} {1,175} Sender = P6 {0,126} {0,136} {0,146} {1,156} {1,176} Sender = P7 {0,127} {0,137} {0,147} {1,157} {1,167} Table 2: Messages sent by all six processes in Round 2. Obviously, if we just voted on the majority of the messages we had received, we would be susceptible to falling for the wrong value. Fortunately, the layout of the tree guarantees that we will actually get a correct value. In Figure 4, the rollup of the output values hasn’t occurred yet, so every node has a question mark in the output value. In Figure 5, the output values are shown. The leaf rank has the output values set to the input values, with X used to indicate unknown values from faulty processes. When the leaf rank is rolled up to the second rank, the nodes with paths 12, 13, 14, and 15 all have clear majority values of 0 for their output values, with 16 and 17 set to X, as their values are uncertain. The final rollup to the top rank successfully sets the output value to 0, as four of the inputs are set to 0 and only 2 are set to X. Mission accomplished. To help with visualization, the program outputs the tree for a given process in the format used by the graphviz program called dot (part of the free Graphviz program; www.graphviz.org). You can then use dot to create a picture of the output graph (all the figures in this article were created with dot). As supplied, the program has n=7 and m=2. These are some good exercises to perform while experimenting with it : • Attempt to invalidate the program or the algorithm by getting incorrect results with some particular combination of faulty messages. • Add a third faulty process and show that it is relatively easy to get invalid output when n=7 and m=3. • Reduce n to 6 and show that it is relatively easy to get invalid output with two faulty processes. • Move up to m=3 and n=10. Experiment with various combinations of faulty Generals and lieutenants and see if you can create incorrect results. DDJ The Sample Code I’ve included a C++ program (available online; see “Resource Center,” page 5) that implements this algorithm. It has a Process class used to send/receive messages, as well as to roll up the decision tree. A Traits class defines the number of processes, number of faulty processes, source process, and values the faulty processes sent in various rounds. I/O Controls x x x x x High-Speed for Real-Time applications Built-In custom Property Editors Automatic and Custom Sizing. No Restrictive Bitmaps Look and Feel of Real Hardware Includes : Switches, Gauges, Sliders, Led’s, Led Bar, Led Spiral, Integer/Binary/Hexadecimal Displays, Tanks, Valves, Motors, LCD Matrix, Spectrum Display, Percent and Pie Graph, Odometers, Analog Clock, Image Display, Rotation Display, and Mode Combo Box. Plot Control x x x x x x x x High-Speed for Real-Time applications Unlimited Number of Channels & Axes Full Customizable External Toolbar Legends, Tables, Limits, Labels, Annotations, Cursors Gradient Backgrounds Log Files and Data Export and Import Save images to BMP, PNG, JPEG, TIF, GIF and EMF Many built in channel types : Tracy, Trace-XY, Bar, Bubble, Fill, Bi-Fill, Digital, Differential and Sweep Interval (EKG) Std Pack .Net x 28 Controls x Basic I/O Controls ActiveX & VCL Also Available Pro Pack .Net x 55 Controls x Basic & Advanced I/O Controls Single Developer : $1099 Additional Developer : $379 ActiveX & VCL Also Available Plot Pack .Net x Plotting : Scientific, Engineering, Strip-Chart, Digital, EKG, and more ActiveX & VCL Also Available Ultra Pack .Net x 56 Controls x Basic & Advanced I/O Controls plus Plotting Single Developer : $1699 Additional Developer : $579 ActiveX & VCL Also Available Single Developer : $559 Additional Developer : $189 Single Developer : $859 Additional Developer : $289 www.iocomp.com 888-599-2929 +1-407-226-3456 7081 Grand National Drive Suite 112, Orlando, FL 32819 36 Dr. Dobb’s Journal l www.ddj.com l April 2008 http://www.graphviz.org http://www.iocomp.com http://www.iocomp.com http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - April 2008

Dr. Dobb's Journal - April 2008 Contents Hmmmm Alia Vox Developer Diaries Dr. Dobb's Excellence in Programming Award Conversations Fast String Search on Multicore Processors The Byzantine Generals Problem Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Random Numbers in a Range Using Generic Programming The Agile Edge Effective Concurrency Swaine's Flames

Dr. Dobb's Journal - April 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.