For Details about how ring works and it’s algorithm check out. @How Ring Algorithm Works? (Election Coordinator)
Many distributed algorithms require a process to act as a coordinator. The coordinator can be any process that organizes actions of other processes. A coordinator may fail so how is a new coordinator chosen or elected? Ring Algorithm
- Each process has a unique number to distinguish them.
- One process per machine (which suggests that an IP address can be the unique identifier)
- Processes know each other’s process number
- Processes do not know which ones are currently up and which ones are down.
- Any node might detect failure first
- Multiple processes might detect failure at once.
- Must run without coordination
- Must deal with arbitrary process failures
- All nodes must agree on when election is over and who the new coordinator is.
Use a ring (processes are physically or logically ordered, so that each process knows who its successor is).
- When a process notices that coordinator is not functioning:
- Builds an ELECTION message (containing its own process number)
- Sends the message to its successor (if successor is down, sender skips over it and goes to the next member along the ring, or the one after that, until a running process is located).
- At each step, sender adds its own process number to the list in the message.
- When the message gets back to the process that started it all:
- Process recognizes the message that contains its own process number
- Changes message type to COORDINATOR
- Circulates message once again to inform everyone else: Who the new coordinator is (list member with highest number); Who the members of the new ring are.
- When message has circulated once, it is removed.
- Even if two ELECTIONS started at once, everyone will pick same leader since node with highest identifier is picked.
- At best 2(N-1 ) messages are passed
- One round for the ELECTION message
- One round for the COORDINATOR
- Assumes that only a single process starts an election.
- Multiple elections cause an increase in messages but no real harm done.