# Shared Flashcard Set

## Details

Comp2005 - Lecture 7 - Distributed Algorithms 2
Alejandro Saucedo - Comp2005 Lecture 7 FlashCard Set
29
Computer Science
05/18/2013

Term
 What is the principles of the leader election problem?
Definition
 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 ±
Term
 What are the correctness and performance properties of the Leader election algorithm?
Definition
 Safety - a participant process pi has electedi = ± or  electedi = P where P is the non-crashed process with the largest identifier Liveness - All processes participate and eventually set electedi != ± or crash Bandwidth consumption: Total number of messages sent Turnaround time: number of serialised message transmissions in a single run
Term
 What are the assumptions made in a ring-based algorithm?
Definition
 Processes p1 ... pN arranged in logical ring pi sends messages to p(i+1)mod n Does not tolerate failures Asynchronous System
Term
 How does the Ring-Based election algorithm operate?
Definition
 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
Term
 What is the correctness of the Ring-based election algorithm?
Definition
 Safety is preserved - only the process with the largest id can send an elected message Liveness is preserved, assuming there are no crashes
Term
 What is the performance of the Ring-based election algorithm?
Definition
 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
Term
 What are the principles of the Bully Election Algorithm?
Definition
 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 = 2Ttransmitting + Tprocessing Each process knows all other processes and can communicate with them Each process knows which processes have higher identifiers
Term
 Show an example of a ring-based algorithm
Definition
 [image]
Term
 How does the Bully election algorithm operate?
Definition
 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
Term
 Show an example of the Bully election algorithm
Definition
 [image]
Term
 What are the characteristics of correctness of the bully election algorithm?
Definition
 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
Term
 Give an example of a safety violation in the bully election algorithm
Definition
 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
Term
 What are the characteristics of performance for the Bully election algorithm?
Definition
 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
Term
 What are the characteristics of a Reliable multicast?
Definition
 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
Term
 Why is IP Multicast unreliable?
Definition
 Packets may arrive in any order No delivery guarantees Doesn't tolerate Multicast router failure
Term
 What are the principles of Multicast Communication?
Definition
 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
Term
 What are the principles of a basic multicast?
Definition
 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)
Term
 What does a reliable multicast guarantee?
Definition
 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")
Term
 How does the reliable multicast algorithm operate?
Definition
 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
Term
 Show the reliable multicast algorithm
Definition
 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;
Term
 What is the correctness of the Reliable Multicast Algorithm?
Definition
 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
Term
 What are the principles of ordered multicast?
Definition
 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
Term
 What are the several ordering guarantees by Ordered multicast?
Definition
 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'
Term
 Give an example of ordered multicast
Definition
 [image]
Term
 What is FIFO ordering implemented?
Definition
 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
Term
 How is total ordering implemented?
Definition
 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
Term
 How is Casual ordering implemented?
Definition
 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 pi maintains its own vector timestamp Vi. 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 (Vj, m) from pj is B-delivered at pi (i != j), pi places it in holdback queue until it has delivered all messages that casually precede it; it needs to check: pi has delivered any earlier messages sent by pj pi has delivered any message that pj had delivered at the time it multicast the message
Term
 Show an example of CO-Multicast
Definition
 [image]
Term
 Show the algorithm for Casual ordering using Vecor timestamps
Definition
 [image]
Supporting users have an ad free experience!