Last ClassToday: Still More Canonical ProblemsElection AlgorithmsBully AlgorithmBully Algorithm DetailsBully Algorithm ExampleSlide 7Ring-based ElectionA Ring AlgorithmComparisonDistributed SynchronizationCentralized Mutual ExclusionMutual Exclusion: A Centralized AlgorithmPropertiesDistributed AlgorithmA Distributed AlgorithmSlide 17A Token Ring AlgorithmSlide 19TransactionsACID PropertiesCS677: Distributed OSComputer ScienceLecture 12, page 1Last Class•Vector timestamps•Global state–Distributed Snapshot•Election algorithmsCS677: Distributed OSComputer ScienceLecture 12, page 2Today: Still More Canonical Problems•Election algorithms–Bully algorithm–Ring algorithm•Distributed synchronization and mutual exclusion•Distributed transactionsCS677: Distributed OSComputer ScienceLecture 12, page 3Election Algorithms•Many distributed algorithms need one process to act as coordinator–Doesn’t matter which process does the job, just need to pick one•Election algorithms: technique to pick a unique coordinator (aka leader election)•Examples: take over the role of a failed process, pick a master in Berkeley clock synchronization algorithm•Types of election algorithms: Bully and Ring algorithmsCS677: Distributed OSComputer ScienceLecture 12, page 4Bully Algorithm•Each process has a unique numerical ID•Processes know the Ids and address of every other process•Communication is assumed reliable•Key Idea: select process with highest ID•Process initiates election if it just recovered from failure or if coordinator failed•3 message types: election, OK, I won•Several processes can initiate an election simultaneously–Need consistent result•O(n2) messages required with n processesCS677: Distributed OSComputer ScienceLecture 12, page 5Bully Algorithm Details•Any process P can initiate an election•P sends Election messages to all process with higher Ids and awaits OK messages•If no OK messages, P becomes coordinator and sends I won messages to all process with lower Ids•If it receives an OK, it drops out and waits for an I won•If a process receives an Election msg, it returns an OK and starts an election•If a process receives a I won, it treats sender an coordinatorCS677: Distributed OSComputer ScienceLecture 12, page 6Bully Algorithm Example•The bully election algorithm•Process 4 holds an election•Process 5 and 6 respond, telling 4 to stop•Now 5 and 6 each hold an electionCS677: Distributed OSComputer ScienceLecture 12, page 7Bully Algorithm Exampled) Process 6 tells 5 to stope) Process 6 wins and tells everyoneCS677: Distributed OSComputer ScienceLecture 12, page 8Ring-based Election•Processes have unique Ids and arranged in a logical ring•Each process knows its neighbors –Select process with highest ID•Begin election if just recovered or coordinator has failed•Send Election to closest downstream node that is alive–Sequentially poll each successor until a live node is found•Each process tags its ID on the message•Initiator picks node with highest ID and sends a coordinator message•Multiple elections can be in progress–Wastes network bandwidth but does no harmCS677: Distributed OSComputer ScienceLecture 12, page 9A Ring Algorithm•Election algorithm using a ring.CS677: Distributed OSComputer ScienceLecture 12, page 10Comparison•Assume n processes and one election in progress•Bully algorithm–Worst case: initiator is node with lowest ID•Triggers n-2 elections at higher ranked nodes: O(n2) msgs–Best case: immediate election: n-2 messages•Ring–2 (n-1) messages alwaysCS677: Distributed OSComputer ScienceLecture 12, page 11Distributed Synchronization•Distributed system with multiple processes may need to share data or access shared data structures–Use critical sections with mutual exclusion•Single process with multiple threads–Semaphores, locks, monitors•How do you do this for multiple processes in a distributed system?–Processes may be running on different machines•Solution: lock mechanism for a distributed environment–Can be centralized or distributedCS677: Distributed OSComputer ScienceLecture 12, page 12Centralized Mutual Exclusion•Assume processes are numbered•One process is elected coordinator (highest ID process)•Every process needs to check with coordinator before entering the critical section•To obtain exclusive access: send request, await reply•To release: send release message•Coordinator:–Receive request: if available and queue empty, send grant; if not, queue request–Receive release: remove next request from queue and send grantCS677: Distributed OSComputer ScienceLecture 12, page 13Mutual Exclusion: A Centralized Algorithma) Process 1 asks the coordinator for permission to enter a critical region. Permission is grantedb) Process 2 then asks permission to enter the same critical region. The coordinator does not reply.c) When process 1 exits the critical region, it tells the coordinator, when then replies to 2CS677: Distributed OSComputer ScienceLecture 12, page 14Properties•Simulates centralized lock using blocking calls•Fair: requests are granted the lock in the order they were received•Simple: three messages per use of a critical section (request, grant, release)•Shortcomings:–Single point of failure–How do you detect a dead coordinator?•A process can not distinguish between “lock in use” from a dead coordinator–No response from coordinator in either case–Performance bottleneck in large distributed systemsCS677: Distributed OSComputer ScienceLecture 12, page 15Distributed Algorithm•[Ricart and Agrawala]: needs 2(n-1) messages•Based on event ordering and time stamps•Process k enters critical section as follows– Generate new time stamp TSk = TSk+1–Send request(k,TSk) all other n-1 processes–Wait until reply(j) received from all other processes–Enter critical section•Upon receiving a request message, process j–Sends reply if no contention–If already in critical section, does not reply, queue request–If wants to enter, compare TSj with TSk and send reply if TSk<TSj, else queueCS677: Distributed OSComputer ScienceLecture 12, page 16A Distributed Algorithma) Two processes want to enter the same critical region at the same moment.b) Process 0 has the lowest timestamp, so it wins.c) When process 0 is done, it sends an OK also, so 2 can now enter the critical region.CS677: Distributed OSComputer ScienceLecture 12, page