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

d04nels_p4ds 2/13/08 10:05 AM Page 35 The Second Stage While sending messages in each round, processes are also accumulating incoming messages. The messages are stored in a tree format, with each round of messages occupying one rank of the tree. Figure 3 shows the layout of the tree for a simple configuration with six processes, one of which can be faulty. Because m=1, there are just two rounds of messaging: The first, in which the general sends a value to each lieutenant process, and a second, in which each process broadcasts its value to all the other processes. Two rounds of messaging are equivalent to two ranks in the tree. In Figure 3, there are six processes, and the General (P1) is faulty—sending a 1 to the first three lieutenants and 0 to the last two. The subsequent round of messaging results in P2 having an information tree that looks just like that in Figure 3. (Because only the General is faulty, in this case all other processes will have an identical tree.) Once a process has completed building its tree, it is ready to decide on a value. It does this by working its way up from the leaves of the tree, calculating the majority value at each rank, and assigning it to the rank above it. The output value at each level is the third item in the data structure attached to each node, and those values are all undefined during the information gathering stage. Calculating the output values is a threestep process: 1. Each leaf node in the tree (all values at rank m) copies its input value to the output value. 2. Starting at rank m–1 and working down to 0, the output value of each internal node is set to be the majority of the output values of all its children. In the event of a tie, an arbitrary tie-breaker is used to assign a default value. The same default value must be used by all processes. 3. When complete, the process has a decision value in the output of the sole node at rank 0. In Figure 3, step 1 of the process assigns the initial values to the leaf nodes. In the next step, the majority value of {1,1,1,0,0} is evaluated and returns a value of 1, which is assigned to the output value in rank 0. Because that is the top rank, the process is done, and P1 decides on a value of 1. Every lieutenant value in a given exercise will have the same paths for all its nodes, and in this case, because only the General is faulty, we know that all lieutenants will have the same input values on all its leaves. As a result, all processes will agree on the same value, 1, which fulfills the agreement property. A More Complicated Example Getting a good understanding of the algorithm really requires walking through an example that has at least three ranks. Let’s consider an example with n=7 and m=2. We’ll continue with the convention that the General is P1, and instead of having a faulty general, we’ll have P6 and P7 be faulty processes. After the initial three rounds of information exchange, each process has the three-ranked tree in Figure 4. The important thing to note in these trees is that I’ve inserted the value X for the input values of any input value that comes from the two faulty processes. We don’t know what P6 and P7 might send in any given round, so in general, we’ll try to evaluate this without pinning the result down. You’ll see that at rank 1, the values from path 17 and 16 are both set to X. In the first round, the two faulty processes communicated possibly false values to all other processes, and may have arbitrarily changed the values sent to different processes to skew the results. As a result of those bad values in rank 1, we see their frequent occurrence in rank 2. In addition, there are additional bad values in rank 2 that resulted from other messages from the faulty processes. All in all, at the leaf nodes, we have 18 deceptive values at the leaf nodes, and only 12 accurate messages that trace their way all the way back to the general through nothing but correct processes. April 2008 l www.ddj.com l Dr. Dobb’s Journal 35 http://www.servoy.com/sexy http://www.servoy.com/sexy 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.