Computer Science 432 Operating Systems Williams College Fall 2006

Agenda

• Announcements
  • End-of-semester party tomorrow 2:30 PM in the CS Lounge. Be there.
• Final Projects
  • Get the paper drafts to me tomorrow (any time) - I will read them over the weekend
  • Talks on Monday
    • Start at 1:30 sharp, TCL 206
    • Mitch/Myron/Jessica will go first
    • Any other constraints?
    • The talks are open to the public, so feel free to invite friends
  • If you would like to demonstrate software, arrange to do so by Friday, 12/15
• Distributed Agreement
  • Lots of interesting ideas in SG&G Chapter 18
  • We will look briefly at just a few
  • Assume we have a collection of n processes P₀, ..., P_n
  • Processes communicate by sending message to each other
  • Problem: we assume that the processing nodes and communication links may be unreliable
  • Election Algorithms - see SG&G slides 18.43-18.48
    • many distributed algorithms need a coordinator process
    • how to choose one?
    • bully algorithm and ring algorithm
  • Distributed Agreement - see SG&G slides 18.49-18.53
    • how can a set of peers agree on a value (decision)?
    • unreliable communication
    • unreliable or adversarial processes
    • Byzantine Generals problem: "One day in ancient times, the Turkish sultan led an invasion into Byzantium. The Emperor called out his armies to meet the invading Turks. Each of the armies was led by its own general.
      The armies that marched out of Constantinople to meet the Turks were strong enough to resist the Sultan's army if their action was coordinated (either attack or retreat). After marching for several days, the Byzantine armies camped near to the Turkish armies. The Byzantine generals planned that night for an attack at dawn. Each general has his own appraisal of the strength of the Turkish army and had his own preference about whether to attack or retreat. Since the attacks had to be coordinated, each general had agreed to follow the consensus decision. So, the generals sent messengers to each other's camps throughout the night to determine the consensus decision.
      There was only one problem with the generals' plan. Byzantine generals were notoriously treacherous, and some of the generals might have been in the pay of the Sultan. The loyal generals knew that if their attack was coordinated, they would be victorious (or escape to fight again), but if some of the loyal generals attacked while the others retreated, they would be defeated. The disloyal generals would attempt to deceive the loyal generals to prevent a coordinated attack. The loyal generals therefore agreed to follow a protocol that ensured a distributed agreement.
      
    • If each loyal general can agree on the opinion V_j of every other (loyal or disloyal) general p_j, the loyal generals will all reach the same decision. Therefore, the Byzantine armied can reach agreement if there is a protocol for reliable broadcast. Each general p_i will transmit its opinion V_i to the other generals subject to the following two conditions, called interactive consistency:
      1. if the sender p_s is loyal, the generals will agree on V_s
      2. if the sender p_s is treacherous, the loyal generals will agree on the same value for V_s
    • For 3 generals, 2 loyal and 1 disloyal, no agreement can be reached.
    • For 4 generals, 3 loyal and 1 disloyal, agreement can be reached
• Course Evaluations