CS633
Out date: 11/25/02
In date : 12/13/02
Lab 5: Leader Election

Object : To implement leader election in distributed systems by two different algorithms :

Bully and Ring Algorithms Distributed Deadlock Detection by Chandy Alg.

Procedure : The nodes will be simulated by threads communicating via
FIFOs and managing buffer space by buffer pools as before.

A. Bully Algorithm

A.1. Implement the Bully algorithm to elect a leader for threads
A.2. Provide 7 Solaris kernel threads T1,T2,T3,T4,T5,T6,T7 such that :
T7 is the leader and finishes execution (dies) and T5 is the first
thread that finds out.
A.3. Show that threads cooperate to find the new leader.

B. Ring Algorithm

B.1. Implement the Ring Algorithm to elect a leader for threads
B.2. Provide 7 Solaris kernel threads T1,T2,T3,T4,T5,T6,T7 in a ring
such that :
T7 is the leader and finishes execution (dies) and T3 is the first
thread that finds out.
B.3. Show that threads cooperate to find the new leader.

C. Chandy-Misra-Haas Algorithm for Deadlock Detection

C.1. Implement the Chandy-Misra-Haas Algorithm to detect deadlocks.
C.2. Provide 3 Solaris kernel threads T1,T2 and T3 which are deadlocked
as in the text example (T1 finds the deadlock and starts the
algorithm)
B.3. Show that the algorithm detects the deadlock and breaks it