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

d04nels_p4ds 2/13/08 10:12 AM Page 34 Core Technology THE BYZANTINE GENERALS PROBLEM Figure 5: The tree after calculating the output values. sends those messages to all other processes, including itself. (The “where allowed” just means that the process skips any messages where adding its process ID to the list would create a cycle in the string of process IDs.) For example, suppose that in Round 0 that P1, a faulty general, told P2, P3, and P4 that the command value was 0, and told P5, P6, and P7 that the command value was 1. In Round 1, the messages in Table 1 would be sent. Things get more complicated in the second round. From the previous rule, we know that each process now has six values that it received in the previous round—one message from each of the three processes—and it needs to send each of those messages to all of the other processes, which might mean each process would send 36 messages out. In Table 1, I showed the messages being sent to all six processes, which is redundant because the same messages are broadcast to all processes. For Round 2, I just show the set of messages that each process sends to all of its neighbors. The six messages that P2 received in Round 1 were {0,12}, {0,13}, {0,14}, {1,15}, {1,16}, and {1,17}. According to the earlier definition, P2 will append its process ID to the path and forward each resulting message to all other processes. The possible messages it could broadcast in Round 2 are {0,122}, {0,132}, {0,142}, {1,152}, {1,162}, and {1,172}. The first message, {1,122}, contains a cycle in the path value of the tuple, so it is tossed out, leaving five messages to be sent to all processes. The first message that P2 is sending in Round 2, {0,132}, is equivalent to saying, “P2 is telling you that in round 1 P3 told it that in round 0 that P1 (the General) told it that the value was 0.” The five messages shown in P2’s column in Table 2 are sent to all six lieutenant processes, including itself. It’s easy to see that as the number of processes increases, the number of messages being exchanged starts to go up rapidly. If there are N processes, each process sends N–1 messages in Round 1, then (N–1)*(N–2) in Round 2, and (N–1)*(N–2)*(N–3) in Round 3. That can add up to a lot of messages in a big system. 34 Dr. Dobb’s Journal l www.ddj.com l April 2008 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.