Flashcards in this deck (53)

• What is the purpose of Election Algorithms in distributed systems?

  To elect a new coordinator when the current one fails.
  distributed_systems algorithms
• How does the Bully Algorithm work?

  The highest ID process bullies others to become the coordinator.
  distributed_systems bully_algorithm
• What is a key assumption used by the Bully Algorithm?

  Every process knows the ID of every other process.
  distributed_systems assumptions
• The Bully Algorithm consists of these steps: 1. Process P notices the coordinator is dead. 2. P sends an ELECTION message to processes with IDs higher than its own. 3. If no one responds, P wins and sends a COORDINATOR message. 4. If a higher process responds, it takes over the election and P waits.
  distributed_systems bully_algorithm steps
• The Ring Algorithm is another election method where processes are arranged in a logical ring and messages are passed around to elect a coordinator.
  distributed_systems ring_algorithm
• Compare the Bully Algorithm and the Ring Algorithm.

  • Bully Algorithm: Highest ID wins.
  • Ring Algorithm: Works in a logical ring structure.
  distributed_systems comparison bully ring
• What is the concept of the Ring Algorithm?

  Processes are arranged in a logical ring and election messages are passed around the ring.
  distributed_systems algorithms
• What initiates the election in the Ring Algorithm?

  A process detects failure, creates an ELECTION message, and sends it to its neighbor.
  distributed_systems election
• How does each process contribute in the ring algorithm?

  Each process adds its own ID to the message and passes it on.
  distributed_systems algorithms
• What happens when the election message returns to the initiator?

  The list of IDs is circulated, and the process with the highest ID becomes the coordinator.
  distributed_systems election
• What is the topology of the Ring Algorithm?

  Fully Connected

  Logical Ring

  Star

  Tree
  distributed_systems topology
• How does the traffic of the Ring Algorithm compare to the Bully Algorithm?

  Exponential (O(2^N) messages)

  High (O(N^2) messages)

  Linear (O(N) messages)

  Constant (O(1) messages)
  distributed_systems traffic
• Which algorithm has faster convergence?

  Both

  Neither

  Bully Algorithm

  Ring Algorithm
  distributed_systems convergence
• What is one drawback of the Ring Algorithm?

  It requires ring maintenance.
  distributed_systems complexity
• Explain clock synchronization in distributed systems.

  It ensures all processes have a consistent view of time across the network.
  distributed_systems synchronization
• What are Lamport's Logical Clocks used for?

  They are used to order events in a distributed system without synchronized clocks.
  distributed_systems clock
• What is the Berkeley Algorithm in the context of clock synchronization?

  It averages time from several clocks to synchronize processes in a distributed system.
  distributed_systems clock
• The Ring Algorithm processes are arranged in a logical ring. Election messages are passed around the ring.
  distributed_systems algorithms
• In the Ring Algorithm, the process with the highest ID becomes the coordinator.
  distributed_systems election
• The traffic in the Ring Algorithm is linear compared to the Bully Algorithm's high traffic.
  distributed_systems traffic
• The Berkeley Algorithm helps to average time from clocks to synchronize systematically through clock synchronization.
  distributed_systems synchronization
• Lamport's Logical Clocks provide a way to order events in distributed systems without relying on synchronized clocks.
  distributed_systems clock
• In the Bully Algorithm, election messages can lead to high traffic of O(N^2), while the Ring algorithm has linear traffic of O(N).
  distributed_systems traffic
• What is the primary need for synchronization in a distributed system?

  To order events, such as banking transactions, due to the lack of a global clock.
  synchronization distributed_systems
• What does Lamport's Logical Clocks algorithm prioritize over absolute time?

  The order of events, specifically the happens-before relationship.
  lamport logical_clocks
• What is maintained by each process in Lamport's Logical Clocks?

  A counter C that is incremented before every event.
  lamport clock
• What happens when a process sends a message in Lamport's Logical Clocks?

  It attaches its counter C to the message.
  lamport communication
• How does the receiver update its clock in Lamport's Logical Clocks?

  By setting C_receiver to max(C_receiver, C_message) + 1.
  lamport clock
• What type of algorithm is the Berkeley Algorithm?

  An Active Time Server algorithm for physical clock synchronization.
  berkeley synchronization
• What is the first step in the Berkeley Algorithm?

  The Time Daemon (Master) polls all Slaves for their time.
  berkeley algorithm
• How does the Master calculate the new time in the Berkeley Algorithm?

  By averaging the time reported by slaves, ignoring extreme outliers.
  berkeley calculation
• What does the Master tell slaves to adjust in the Berkeley Algorithm?

  By how much to speed up or slow down their clocks.
  berkeley adjustment
• What does the Master never do in the Berkeley Algorithm?

  It never sets the time back abruptly.
  berkeley synchronization
• In a distributed system, synchronization is essential for ordering events like banking transactions.
  synchronization distributed_systems
• Lamport's Logical Clocks focus on the happens-before relationship rather than absolute time.
  lamport logical_clocks
• Each process in Lamport's Logical Clocks maintains a counter C and increments it before every event.
  lamport clock
• In Lamport's Logical Clocks, a process attaches its counter C to messages when sending them.
  lamport communication
• The receiver updates its clock to max(C_receiver, C_message) + 1 in Lamport's Logical Clocks.
  lamport clock
• The Berkeley Algorithm is an Active Time Server algorithm for syncing physical clocks.
  berkeley synchronization
• The first step of the Berkeley Algorithm is that the Master polls all Slaves for their time.
  berkeley algorithm
• The Master calculates the average time by ignoring extreme outliers in the Berkeley Algorithm.
  berkeley calculation
• The Master directs slaves to adjust their clocks to speed up or slow down in the Berkeley Algorithm.
  berkeley adjustment
• What does RPC stand for?

  Remote Procedure Call
  communication rpc
• What is the role of the Client Stub in RPC?

  It acts as a proxy, packing parameters into a message.
  communication rpc
• What does the Server Stub do in RPC?

  It unpacks parameters from the message and calls the actual server procedure.
  communication rpc
• Describe the first step in the RPC process.

  The client calls the Client Stub (local call).
  communication rpc
• What happens during marshalling in RPC?

  The Client Stub packs parameters into a message.
  communication rpc
• What is the final step in the RPC sequence?

  The Server OS passes the message to the Server Stub.
  communication rpc
• RPC allows a program to call a procedure on a remote machine as if it were a local function call.
  communication rpc
• The sequence in RPC starts with the client calling the Client Stub, which later leads to Server Stub handling the request.
  communication rpc
• Which of the following is NOT a responsibility of the Client Stub?

  Calling the server procedure

  Unpacking parameters

  Receiving messages from the server

  Packing parameters into a message
  communication rpc
• What does the Server Stub handle in the RPC process?

  Unpacking parameters and calling the server procedure

  Sending messages to the client

  Packing parameters into a message

  Computing average time
  communication rpc
• Which diagram represents the Time Daemon in a distributed system?

  
  communication middleware