ABSTRACT
Distributed applications rely on specific forms of coordination among processes to accomplish their goals. Some tasks of coordination can be viewed as a form of preprocessing. Examples include clock synchronization, spanning tree construction, and consensus. In this chapter, we single out two specific coordination algorithms and explain their construction. Our first example addresses leader election, where one among a designated set of processes is chosen as leader and assigned special responsibilities. The second example addresses a problem of model transformation. Recall that asynchrony is hard to deal with in real-life applications due to the lack of temporal guarantees — it is simpler to write algorithms on the synchronous process model (where processes execute actions in lock-step synchrony) and easier to prove their correctness. This motivates the design of synchronizers that transform an asynchronous model into a synchronous one. In this chapter, we discuss several algorithms for leader election and synchronizer construction.
