The Byzantine GeneralsProblemPaper by Leslie Lamport, RobertShostak, and Marshall PeasePresentation by David ZageWhat is the problem?Why Byzantine Generals?n Its much more interesting to writeabout treacherous generals then a cpufailingn Basic goals° A: All loyal generals decide on same planof action° B: A small number of traitors cannotcause a bad plan to be adopted.Basic Ideasn To satisfy condition A° Have all the general use the same method ofcombing information to come up with a plann To satisfy condition B° Use a robust method (median function of somesort)n Why not just use the median?° Traitors lie and not everyone may have thesame information!Formal Problem Definitionn Assume we have one commandinggeneral and his subordinate lieutenantgenerals.n IC1: All loyal lieutenants obey thesame ordern IC2: If the commanding general isloyal, then every loyal lieutenant obeysthe order he sends.Here comes the problemn Oral, easily changed messagesn No solution works unless more thantwo-thirds of the generals are loyaln Even with just three generals, onetraitor makes the protocol fail!Proving the impossibilityAttack!Attack!General said “Retreat!”Lieutenant 1Lieutenant 2IC2: If the commandinggeneral is loyal, thenevery loyal lieutenantobeys the order he sends.Proving the impossibility(2)Attack!Retreat!General said “Retreat!”Lieutenant 1 Lieutenant 2IC1: All loyallieutenants obey thesame orderGeneral said “Attack!”General Impossibilityn No solution for fewer than 3m+1 generals in the presence ofm traitorsn Impossibility exists irrespective of exact or approximateagreement.m lieutenants m lieutenantsCommander and m-1 lieutenantsA Solution with Oral Messagesn Assumption on oral messaging° Every message that is sent is delivered correctlyn Traitors may not interfere with communication betweengenerals° Receiver knows who sent the messagen Traitors may not confuse the loyal generals by sendingextra messages° Absence can be detectedn Traitors can not break the solution by not sendinganythingn Default message is “Retreat”Oral Message Algorithmn Recursive algorithm° Each general (a.k.a. lieutenant) forwards onreceived values to all other lieutenant° The commander send his value to everylieutenant° For each lieutenant i, broadcast the values to allother lieutenants who have not had the value.° Take the majority function of the receivedvalues.° To distinguish between messages from different“rounds”, index them using the lieutenant’snumber iExample with m=1 and n=4XYZXYXYZZEach lieutenant obtains v1 = x, v2= y, v3=z, which all results in the same valuewhen the majority is takenThe dreaded PROOFn For any m, algorithm OM(m) satisfiesconditions IC1 (All loyal lieutenantsobey the same order) and IC2 (If thecommanding general is loyal, thenevery loyal lieutenant obeys the orderhe sends) if there are more than 3mgenerals and at most m traitors.n Induction on m proves true in allcases.What if the messages aresignedn One more assumption on oralmessaging° A loyal general’s signature cannot beforged or changed and anyone can verifyauthenticityn Three general solutions now exist!n Works for any n >= m+2 (1 non-faultycommander and 1 loyal lieutenant)Signed Message Algorithmn General sends a signed order to all his lieutenantsn Each lieutenant signs and forwards on the messagehe received to all the other lieutenants until everymessage has been signed by everyone else.n Each lieutenant keeps track of the properly signedorders he has received° Possible orders are attack, retreat, attack & retreatn Use choice method to have everyone choose samevalueWhat’s going on here?n Every loyal lieutenant eventually has thesame set of signed messages, resulting inthe same choicen If commander is loyal, then all loyallieutenants will have correct messagesn If the commander is a traitor, lieutenantsreceive conflicting messages and but stillend up choosing the same choice (retreat).Missing Network Pathsn What happens if we don’t have a fullyconnected network?n Definitions:° Regular set of neighbors of node In Each node is a neighbor of node In For every node not in the set, there exists a path notpassing through I from a node in the set° A graph is p-regular if each node has p regularneighborsn 3m-regular graph has a minimum of 3m+1 nodesMissing Network Paths(2)n Variant of the Oral Message Algorithmsolves the Byzantine GeneralsProblem for 3m-regular graphs with atmost m traitors.° Can not have the message handled bytraitorsn With signed messages, if loyallieutenants are connected, the problemcan be solvedPractical Implicationsn Majority Voting° Input synchronization so all processes decide on the samevalue° If the input is not faulty, then all non-faulty processes usethe valuen Every message that is sent is delivered correctly° Failure of the communication medium acts as anothertraitorn Receiver knows who sent° Completely connected network° If using signed messages, this becomes unnecessaryPractical Implications(2)n Absence can be detected° Timeout mechanisms are needed° Synchronous Communicationn A signature cannot be forged orchanged and anyone can verifyauthenticity° Message signed by i= (M, S(M))° Crypto and modular arithmeticConclusionn Byzantine Generals Problem solutionsare expensive° Lots of hardware° Even more messagesn Must decide how much performanceversus reliabilityn Performance can be improved throughsmarter messaging and fewer
View Full Document
Unlocking...