Algorithm used to elect a unique process from a group - for example to choose a central coordinator

• All processes must agree on the choice of the leader
• Must deal with process failure
• N processes with unique and totally ordered "identifiers" (Often 1/workload to make process with the lowest current workload become leader)
• Each process can only call one election
• Must handle mutilple concurrent elections being called by different processes
• Process with the largest ID must win election
• Each process starts with an elected variable initialized to ±

• Safety - a participant process p_i has elected_i = ± or  elected_i = P where P is the non-crashed process with the largest identifier
• Liveness - All processes participate and eventually set elected_i != ± or crash
• Bandwidth consumption: Total number of messages sent
• Turnaround time: number of serialised message transmissions in a single run

• Processes p_{1 ...} p_N arranged in logical ring
• pi sends messages to p(i+1)mod n
• Does not tolerate failures
• Asynchronous System 

• Calling an eleciton
• Mark itself as participant
• Create election message, containing id
• Send message to neighbour
• When receiving an election message
• If myid < msgid: forward message and mark self as participant
• If myid > msgid check my-participant-flag
• If Not participant: A new election is started, put our id into the message instead and mark ourselves as participant
• If participant already: We are taking part in an election, stop forwarding the messages for the new one
• IDs are equal: We won the election. Set elected = myID and send elected message with myid. Mark self as non-participant
• When receiving an elected message
• If id in message is same as ours: Stop forwarding, message has gone all the way around the ring
• Else: 
• Set elected to be the id in the message
• Mark self as non-participant

• Safety is preserved - only the process with the largest id can send an elected message
• Liveness is preserved, assuming there are no crashes

• One election, best case (Initiating process has highest identifier)
• N election messages, N elected messages
• Turnaround: 2N messages
• One election, worse case (Anti-clockwise neighbour has highest identifier)
• 2N - 1 election messages, N elected messages
• Turnaround: 3N - 1 messages
• Works if more than one process starts an election

• The process with the largest identifier out of the non-failing ones must be elected
• Messages: Election, answer, Coordinator
• Processes can crash
• Message delivery reliable
• Synchronous system, use timeouts to detect process crashes
• T = 2T_transmitting + T_processing
• Each process knows all other processes and can communicate with them
• Each process knows which processes have higher identifiers

• If we detect a coordinator failure through timeouts
• Send eleciton message to all processes with higher IDs (Except the failed coordinator)
• If there are no answers after time T - You are the coordinator, send coordinator message with your id to all processes with lower id
• If there is an answer, wait for a coordinator message. Starting a new election if there is a timeout
• If we receive election message
• Send an answer message back
• If this process hasn't already started an election, send an election message to all higher-id processes (including the "failed" coordinator)
• If we receive coordinator message
• Set elected to the new coordinator

• Safety
• A lower id process always yields to a higher-id one
• However during an election, if a failed process is replaced
• The low id processes might have two different coordinators: The newly elected coordinator and the new process
• Failure detection might be unreliable
• Liveness
• All processes participate and know the coordinator at the end

• If a higher process fails, and then is replaced (Or the higher process is running very slowly and incorrect timeout values are used)
• While a lower process sends coordinator message, so does the higher one
• The lowest process may conclude the lower is the coordinator, while the lower and the higher conlcude the higher is the coordinator

• Best case (#2 process detects failure of coordinator and elects itself:
• Overhead: N-1 Coordinator messages
• Turnaround delay: One message (No election/Answer messages)
• Worse case (Process with least identifier detects coordinator failure)
• Overhead:
• 1 + 2 + ... + (N-1) + (N-2) 
• = (N-1)(N-2)/2 + (N-2) election messages
• N-2 coordinator messages
• totall = O(N^2)
• Turnaround delay: Delay of election and answer messages

• Tolerates crashes
• assumes closed group
• Delivery guarantees integrity, validity and agreement
• All processes in group must receive copies of the messages sent to the group
• Only one multicast operation is used to send a message to group
• Assumptions
• Group membership is known
• Reliable communication channels
• Process only fail by crashing

• Packets may arrive in any order
• No delivery guarantees
• Doesn't tolerate Multicast router failure

• Basic operations
• Multicast(g, m) sends message m to all members of group g
• Deliver(m) (Accepting or processing message)
• Message m incorporates information about its sender sender(m) and its destination group(m)
• Closed vs open groups:
• Only group members allowed ot multicast to closed groups
• Closed groups often assumed

• Guarantees a correct process will eventually receive the message, as long as the multicaster does not crash
• Only group members receive messages sent to the group
• Uses primitives B-multicast and B-deliver
• Implementation uses reliable one-to-one send opaeration
• to B-multicast(g,m): for each process p in g, send(p, m)
• On receive(m) at p, B-deliver(m) at p
• Above works for open groups
• More efficient algorithm exists (Using IP-multicast as it sends multiple messages, rather than 1, like IP multicast does)

• Integrity: A correct process delivers a message at most once; once group members receive messages sent to the group
• Validity: If a correct process multicasts message m, it will eventually deliver m (ensures liveness for the sender)
• Agreement: If a correct process delivers a message m, all other correct processes in group(m) will eventually deliver m ("all or nothing")

• To R-multicast message m to group g, sender process B-multicasts m to the processes in g (including self)
• When message m is B-delivered for the first time to some process, the recipient (but not the originator) in turn B-multicasts m to the group and then R-delivers the message
• Duplicate messages are identified and not delivered
• Algorithm is inefficient

• On initialization
• Received := {};

• For process p to R-multicast message m to group g
• B-multicast(g,m); //p is in 

• On B-deliver(m) at process q with g = group(m)
• if (m not in Received)
• Received = Received union {m}
• If (q != p) 
• B-multicast(g, m);
• R-deliver m;

• Validity: Yes (Correct processes will eventually R-deliver a message to themselves)
• Integrity: Yes (As duplicates are detected)
• Agreement: Yes (If a correct process does not R-deliver, then it never B-delivered; so no correct process could have B-delivered either
• Uniform agreemend also holds: if a process (correct or not) delivers a message, then all correct processes will eventually deliver the message

• Ensures order on message delivery
• Several possible ordering guarantees
• FIFO Ordering: If a correct process issues multicast(g,m) and then multicast(g, m'), then any correct process delivers m before m'
• casual ordering: if multicast(g,m) -> multicast(g,m) then any correct process delivers m before m' (implies FIFO)
• total ordering: if a correct process delivers m before m', then any correct process delivers m before m' (Does not imply either FIFO or casual)
• Do not assume reliability of multicast primitive

• FIFO: If a correct process issues multicast(g,m) and then multicast(g,m') then any correct process delivers m before m'
• Casual (Implies FIFO): If multicast(g,m) -> multicast(g,m') then any correct process delivers m before m'
• Total (Does not imply any): if a correct process delivers m before m', htne any correct process delivers m before m'

• Each process keeps counter for number of messages it sent to group g
• Each process remembers the sequence number of latest message from process p sent to group g that it delivered
• Attach sequence numbers to multicast messages
• Queue messages until all previous messages from p to g have been delivered
• Works with basic and reliable multicast

Similar to FIFO by keeping group-specific sequence of numbers

Needs sequencer process to assign sequence numbers, or distributed agreement on the assignment of sequence numbers

• If multicast(g,m) -> multicast(g,m') then any correct process delivers m before m'
• Assume non-overlapping closed groups
• Solution uses vector clocks
• Each process p_i maintains its own vector timestamp V_i. Entries in the timestamp count the number of multicast messages from each process that happened so far
• To CO-multicast message m to group g, a process increments ints entry in the timestamp and B-multicasts m along wit its timestamp to g
• When message (V_j, m) from p_j is B-delivered at p_i (i != j), p_i places it in holdback queue until it has delivered all messages that casually precede it; it needs to check:
• p_i has delivered any earlier messages sent by p_j
• p_i has delivered any message that p_j had delivered at the time it multicast the message