Leader Election and Synchronizers
Stub. Leader election algorithms — the bully algorithm, maxima-finding on a ring (Chang-Roberts, Franklin's, Peterson's), and election in arbitrary/anonymous networks — plus synchronizers (ABD, and Awerbuch's alpha/beta/gamma family) that let a synchronous algorithm run correctly over an asynchronous network.
Two coordination primitives. Leader election picks a single distinguished process out of a set of peers — by exploiting process IDs and a spanning topology (bully), by finding the maximum ID on a ring (three progressively more message-efficient algorithms), or, harder still, on arbitrary or even anonymous (ID-less) networks. Synchronizers solve a different problem: given an algorithm designed for synchronous rounds, simulate those rounds correctly over an asynchronous network, at a message/time overhead that the ABD and Awerbuch synchronizer families trade off differently.
Outline (TODO — flesh out each)
- The bully algorithm
- Maxima finding on a ring — Chang-Roberts, Franklin’s, Peterson’s algorithms
- Election in arbitrary networks
- Election in anonymous networks
- Synchronizers — the ABD synchronizer
- Awerbuch’s synchronizer — alpha, beta, gamma; performance comparison