Shared Flashcard Set


Comp2005 - Lecture 7 - Distributed Algorithms 2
Alejandro Saucedo - Comp2005 Lecture 7 FlashCard Set
Computer Science
Undergraduate 2

Additional Computer Science Flashcards




What is the principles of the leader election problem?

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 ±
What are the correctness and performance properties of the Leader election algorithm?
  • 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
What are the assumptions made in a ring-based algorithm?
  • Processes p1 ... parranged in logical ring
  • pi sends messages to p(i+1)mod n
  • Does not tolerate failures
  • Asynchronous System 
How does the Ring-Based election algorithm operate?
  • 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
What is the correctness of the Ring-based election algorithm?
  • Safety is preserved - only the process with the largest id can send an elected message
  • Liveness is preserved, assuming there are no crashes
What is the performance of the Ring-based election algorithm?
  • 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
What are the principles of the Bully Election Algorithm?
  • 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
Show an example of a ring-based algorithm
How does the Bully election algorithm operate?
  • 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
Show an example of the Bully election algorithm
What are the characteristics of correctness of the bully election algorithm?
  • 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
Give an example of a safety violation in the bully election algorithm
  • 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
What are the characteristics of performance for the Bully election algorithm?
  • 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
What are the characteristics of a Reliable multicast?
  • 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
Why is IP Multicast unreliable?
  • Packets may arrive in any order
  • No delivery guarantees
  • Doesn't tolerate Multicast router failure
What are the principles of Multicast Communication?
  • 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
What are the principles of a basic multicast?
  • 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)
What does a reliable multicast guarantee?
  • 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")
How does the reliable multicast algorithm operate?
  • 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
Show the reliable multicast algorithm
  • 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;
What is the correctness of the Reliable Multicast Algorithm?
  • 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
What are the principles of ordered multicast?
  • 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
What are the several ordering guarantees by Ordered multicast?
  • 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'
Give an example of ordered multicast
What is FIFO ordering implemented?
  • 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
How is total ordering implemented?

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

How is Casual ordering implemented?
  • 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 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
Show an example of CO-Multicast
Show the algorithm for Casual ordering using Vecor timestamps
Supporting users have an ad free experience!