Consensus

We have in the previous three lectures looked at different algorithms for distributed systems. Today we round this topic off by looking at problems that cannot be solved. As we shall see, there are simple problems for which a solution seems possible that in some kinds of distributed systems cannot be solved.

I will give some information on the study-exercise and  introduce and motivate them.

Literature

[DS] Chapter 12.5

Supplementary Reading

• http://www.geocities.com/TimesSquare/Labyrinth/2398/bginfo/social/war.html
• http://portal.acm.org/citation.cfm?doid=357172.357176

1. Consider the Byzantine general's problem with 4 generals (labelled g1 to g4), one of which may be faulty. The commander is announcing the time of attack.
   1. Assume that the commander (say g1) is correct and proposes to attack at 4pm, but that general g4 is treacherous and proposes respectively 1pm and 3pm to the other generals. At what time will they attack?
   2. Assume that the commander (say g1) is treacherous and he proposes to attack at time 1pm, 4pm, and 4 pm to the other generals respectively. When will they attack?
   3. Assume that the commander (say g1) is treacherous and he proposes to attack at time 1pm, 3pm, and 4 pm to the other generals respectively. When will they attack?
2. [DS] 12.19, 12.20, 12.21.
3. Read the study exercise, and choose a topic.