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

d04nels_p4ds 2/13/08 10:11 AM Page 32 Core Technology THE BYZANTINE GENERALS PROBLEM Figure 1: The case in which the source process is faulty. Figure 2: The case in which P3 is faulty. continued from page 30 You can see the difficulty P2 faces in this situation. Regardless of which configuration it is in, the incoming data is the same. P2 has no way to distinguish between the two configurations, and no way to know which of the two other processes to trust. This situation doesn’t necessarily get better just by throwing more nonfaulty processes at the problem. A naïve algorithm (as in Figures 1 and 2) would have each process tell every other process what it received from P 1 . A process would decide the correct decision by simple majority. It’s relatively easy to show that, regardless of how many processes are in the system. A subversive source process with one collaborator can cause half the processes to choose to attack, and half the processes to retreat, leading to maximum confusion. The Lamport, Pease, and Shostak Algorithm In 1982, Lamport, Pease, and Shostak published a straightforward solution to this problem (research.microsoft.com/users/ lamport/pubs/byz.pdf ). The algorithm assumes that there are n processes, with m faulty processes, where n>3m. Thus, for a scenario such as that in Figures 1 and 2 with one faulty process, there would have to be a minimum of four processes in the system to come to agreement. (For purposes here, n refers to the count of processes, and m to the number of faulty processes.) The definition of the algorithm in the original paper is short and succinct, but can be confusing for programmers who don’t have experience with distributed algorithms. Lamport’s algorithm is a recursive definition, with a base case for m=0, and a recursive step for m>0: ❒ Algorithm OM(0) 1. The general sends his value to every lieutenant. 2. Each lieutenant uses the value he receives from the general. Figure 3: The Tree Layout for 5 processes with 1 faulty process. Sender = P2 Dest Msg P2 P3 P4 P5 P6 P7 {0,12} {0,12} {0,12} {0,12} {0,12} {0,12} Sender = P3 Dest Msg P2 P3 P4 P5 P6 P7 {0,13} {0,13} {0,13} {0,13} {0,13} {0,13} Sender = P4 Dest Msg P2 P3 P4 P5 P6 P7 {0,14} {0,14} {0,14} {0,14} {0,14} {0,14} Sender = P5 Dest Msg P2 P3 P4 P5 P6 P7 {1,15} {1,15} {1,15} {1,15} {1,15} {1,15} Sender = P6 Dest Msg P2 P3 P4 P5 P6 P7 {1,16} {1,16} {1,16} {1,16} {1,16} {1,16} Sender = P7 Dest Msg P2 P3 P4 P5 P6 P7 {1,17} {1,17} {1,17} {1,17} {1,17} {1,17} Table 1: Messages sent by all six lieutenant processes in Round 1. ❒ Algorithm OM(m), m>0 1. The general sends his value to each lieutenant. 2. For each i, let vi be the value lieutenant i receives from the general. Lieutenant i acts as the general in Algorithm OM(m–1) to send the value vi to each of the n–2 other lieutenants. 3. For each i, and each j≠i, let vi be the value lieutenant i received from lieutenant j in step 2 (using Algorithm (m–1)). Lieutenant i uses the value majority(v1, v2,…vn ). 32 Dr. Dobb’s Journal l www.ddj.com l April 2008 http://research.microsoft.com/users/lamport/pubs/byz.pdf http://research.microsoft.com/users/lamport/pubs/byz.pdf 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.