Chapter 5: Coordination & Agreement

Question 1

Synchronous distributed system model

Answer 1

• Each message transmitted over a channel is received within a known bounded time
• Time to execute each step of a process has known lower and upper bounds
• Each process has a local clock whose driftrate from real time has a known bound

Question 2

Asynchronous distributed system model NN

Answer 2

• Messages may need an arbitrary time to be transmitted
• Each step of a process may take an arbitrary time to complete
• Clock driftrates are arbitrary

Question 3

Thought experiment - Some takeaways

Answer 3

• Asynchronous model is representative for Internet and many practical distributed applications
• Solution valid for asynchronousd distributed systems are also valid for synchronous ones
• Many design problems can not besolved in an asynchronous world (e.g., when vs. who leads attack)
• Applyt timeouts and timing constraints to reduce uncertainty and to bring synchronous model into the picture

Question 4

Failure models

Answer 4

• Process and communication channel may fail, i.e., depart from correct and expected behaviour
• Failure model offers understanding for effects of failures
• Failure types
  
  • Omission failures (one ore more responses fail)
  • Arbitrary failures (wrong value)
  • Timing failures (outside interval)

Question 5

Process omission failures

Answer 5

• Fails by halting, i.e., crashes (e.g. bluescreen)
• Fail‐stop failure
  
  • Process halts and remains halted
  • Others can detect this state
• Crash failure
  
  • Process halts and remains halted
  • Others can (only) suspect this state

Question 6

Communication omission failure

Answer 6

• Receiving process does not receive message
• Typically becaue of
  • Buffer overlfow
  • Network partition
• Failure types
  
  • Send-omission
  • Receive-omission
  • Channel-omission
• Process vs. communication failure: Generally, impossible to distinguish

Question 7

In our thought experiment NN

Answer 7

• Could Army i detect whether Army j has been defeated? (i.e., process failed?)
• Assuming the enemy could attack
• While undefeated, send periodic message (e.g. hearbeat)
  
  • Assume enemy can not corrupt message

Question 8

Arbitrary failures

Answer 8

• Encompasses prior failure classes
• Process not just stops or crashes but processes requests incorrectly, corrupts state, produces inconsistent & incorrect output (commission failures)
• Does not follow agreed protocol, messages get corrupted, messages introduced
• Result:Systembehavesunpredictable
• A.k.a. Byzantine failures / Produces –> produces wrong output

Question 9

Access to shared variables and RACE condition

Answer 9

• Imaging a globally shared variable counter in a process accessible to multiple threads:
  
  • counter ++
  • counter –
  • Register could be 4, 6 or 5
• Race condition:
  
  • Several threads manipulate shared data concurrently. The final value of the data depends upon which thread finishes last.
  • To prevent race conditions, concurrent processes must be synchronized
• ​The statements: counter++; counter‐‐; must each be executed atomically.
• Atomic operation means an operation that completes in its entirety without interruption.
• This is achieved through synchronization primitives
• Shared variable accessed in critical section, protected by synchronization primitives
• Known as the critical section problem or as mutual exclusion

Question 10

Distributed mutual exclusion

Answer 10

• In distributed systems, mutual exclusion is more complex due to lack of:
  
  • Shared memory
  • Timing issues
  • Lack of a global clock
  • Event ordering
• Applications
  
  • Accessing a shared resource in distributed systems
  • Communicating over a wireless channel 802.11

Question 11

Critical section (CS) problem: No shared memory

Answer 11

• System with n processes
• Processes access shared resources in CS
• Coordinate access to CS via message passing
• Application‐level protocol for accessing CS
  
  • Enter_CS() – enter CS, block if necessary
  • ResourceAccess() – access shared resource in CS
  • Exit_CS() – leave CS

Question 12

Assumptions for CS NN

Answer 12

• System is asynchronous
  
  • No bound on delays, no bound on clock drift, etc.
• Processes do not fail
• Message delivery is reliable
  
  • Any message sent, is eventually delivered intact and exactly once
• Client processes are well‐behaved and spent finite time accessing resources in the CS

Question 13

Mutual exclusion requirements CS

Answer 13

• Safety
  
  • At most one process in the critical section at a time
• Liveness
  
  • Requests to enter & exit CS eventually succeed
  • No deadlock
• Fairness (order & starvation)
  
  • If one request to enter CS happened‐before another one, then entry to CS is granted in that order
  • Requests are ordered such that no process enters the critical section twice while another waits to enter (i.e., no starvation)

Question 14

Deadlock & starvation

Answer 14

• Deadlock: Two or more processes become stuck indefinitely while attempting to enter and exit the CS, by virtue of their mutual dependency
• Starvation: The indefinite postponement of entry to CS for a process that has requested it.
• Can we order entry to the CS by the times processes requested it?

Question 15

Performance metrics NN

Answer 15

• Bandwidth: Number of messages sent, received or both
• Synchronization delay: Time between one process exiting the critical section and the next entering
• Client delay: Delay at entry and exit (response time)
• We do not measure client access to resources protected by the critical section (assume finite)

Question 16

Solution strategies Deadlocks

Answer 16

• Centralized strategy
  
  • Divide processes into master and slaves, master dictates actions of slaves
• Distributed strategy: Each process independently decides actions, based on local knowledge of others’ state
  
  • Token‐based: A node is allowed in the critical section (CS) if it has a token. Tokens are passed from site to site, in some (priority) order.
  • Non‐token‐based: A node enters CS when an assertion becomes true. A node communicates with other nodes to obtain their states and decides whether the assertion is true or false.

Question 17

Centralized strategy

Answer 17

1. Elect a leader (details, cf. second part of this lecture)
   * Meets requirements: Safety, liveness, no starvation
   * Does solution meet the ordering requirement?
   * Advantages
   
   • Simple to implement
     * Disadvantages
   • Single point of failure
   • Bottleneck, network congestion, timeout
   • Deadlock potential for multiple resources with separate servers
     * Enter_CS()
   • Two messages: Request & Grant
   • Delays the requesting process by round trip for messages
     * Exit _CS()
   • One message: Release message
   • Assuming asynchronous message passing, incurs no delay

Question 18

Distributed strategy

Answer 18

• In a distributed algorithm, the same decision must be made on each node, independent of the other nodes in the system.
• Selected algorithms
  
  • Ring‐based algorithm
  • Logical clocks‐based algorithm (Lamport, 1976)
  • Ricart & Agrawala, 1981
  • Maekawa, 1985
  • Many more

Question 19

Ring‐based algorithm

Answer 19

• Logical ring of processes
• Each Pi knows its successor, P(i+1) mod N
• Logical topology a priori unrelated to physical topology

Analysis:

• Safe: Node enters CS only if it holds the token
• Live: Since finite work is done by each node (can’t

re‐enter), the token eventually gets to each node

• Fair: Ordering is based on ring topology
• Performance
  
  • Constantly consumes network bandwidth, even when no processes seek entry, except when inside the CS

Synchronization delay: Between 1 and N messages – Client delay: Between 0 and N messages; 1 for exit

• Problems
  
  • Lost token
  • Duplicated token
  • Failed node

Question 20

Ricart & Agrawala, 1981, algorithm

Answer 20

• Basic idea
  
  • Processes wanting to enter CS, multicast a request to all processes
  • Enter CS, once all have granted request
• Use Lamport timestamps… logical loch value to order requests: , t process identities T the timestamp, P_i the process identifier
• Each process is in one of three states
  
  • Released ‐ Outside the CS
  • Wanted ‐ Wanting to enter CS
  • Held ‐ Inside CS
• If a process requests to enter CS and all other processes are in the Released state, entry is granted by each process
• If a process, Pi, requests to enter CS and another process, Pk, is inside the CS (Held state), then Pk will not reply, until it is finished with the CS

Question 21

Ricart & Agrawala algorithm

Answer 21

Question 22

Fault‐tolerance aspects
of mutual exclusion algorithms

Answer 22

• None of the algorithms tolerates message loss
• Ring‐based algorithm cannot tolerate crash of single process
• Centralized algorithm can tolerate crash of clients that are neither in the CS, nor have requested entry
• Described R & A does not tolerate faults either

Question 23

Leader election

Answer 23

• Problem: A group of processes, P1, …, Pn, must agree on some unique Pk to be the “leader”
• Often, the leader then coordinates another activity
• Election runs when leader (a.k.a., coordinator) failed
• Any process who hasn’t heard from the leader in some predefined time interval may call for an election
• False alarm is a possibility (new election initiated, while current leader still alive)
• Several processes may initiate elections concurrently
• Algorithm should allow for process crash during election

Question 24

Process identifier

Answer 24

• Elected leader must be unique
• The one with the largest identifier
• Identifier could be any “useful value” – I.e., unique & totally ordered
• E.g., based on OS process identifiers, IP adr., port
• E.g., based on least computational load
  
  • <1/load, i>, load > 0, i is process ID to break ties
• Each process, Pi, has a variable electedi that holds
• the value of the leader or is “┴” (undefined)

Question 25

Applications of leader election

Answer 25

* **Berkeley clock synchronization algorithm** * **Centralized mutual exclusion algorithm** * Primary‐backup replication algorithms * Two‐phase commit protocol * Used in Amazon Dynamo KV‐store (replication) * **Used in Google BigTable & GFS**

Question 26

As compared to mutual exclusion

Answer 26

* **Losers return to what they were doing ... ... instead of waiting** * **Fast election** is important ... ... not starvation avoidance * **All processes must know the result**... ... not just the winner

Question 27

Election algorithm requirement

Answer 27

* **Safety** * A participating process, Pi, has variable electedi = “┴” or electedi = P, where P is chosen as the non‐crashed process at the end of the election run with the largest identifier. * **Liveness** * All processes participate in the election and eventually either set electedi ≠ “┴” or crash. * **Performance** * Total number of messages sent (bandwidth) –...

Question 28

Ring‐based algorithm, 1978: Overview

Answer 28

* Essentially three phases 1. **Initialization** 2. **Election phase** (concurrent calls for election) * Determine election winner (voting phase) * Reach point of message originator 3. **Announce the leader phase** (victory announcement phase)

Question 29

Ring‐based election algorithm

Answer 29

* Construct a ring (cf. ring‐based mutual exclusion) * Assume, **each P has unique ID** * Assume, **no failures and asynchronous system** * **Any Pi may begin an election** **by sending an election message to its successor** * **Election message holds Pi’s ID** * **Upon receiving** an election message, **Pk compares its own** * **ID** to ID in received message * **If message ID is greater:** **Forward** **_election message_** * **If ... smaller:** **Forward _election message_ with Pk’s ID,** unless Pk has already been participating in the current election run * **If ... equal: Pk is now leader.** **Forward _victory message_ to notify all other processes**

Question 30

Different cases - Ring-based algorithm

Answer 30

Question 31

Ring‐based algorithm: Example (Picture only)

Answer 31

* Construct a ring (cf. ring‐based mutual exclusion) * Assume, each P has unique ID * Assume, no failures and asynchronous system * Any Pi may begin an election by sending an election message to its successor * Election message holds Pi’s ID * Upon receiving an election message, Pk compares its own * ID to ID in received message * If message ID is greater: Forward election message * If ... smaller: Forward election message with Pk’s ID, unless Pk has already been participating in the current election run * If ... equal: Pk is now leader. Forward victory message to notify all other processes

Question 32

Ring‐based election algorithm analysis

Answer 32

* **Worst case** * Single process calls for election * **Anti‐clockwise neighbour has highest identifier** * N‐1 messages to reach this neighbour * N messages to reach point of origin * Leader announcement takes another N messages * For a grand total of 3N – 1 messages

Question 33

Bully algorithm, Garcia‐Molina, 1982

Answer 33

* Assumes **each process has a unique ID**, **reliable message delivery, and synchronous system with timeouts** * Assumes **processes know each others’ IDs** and can communicate with one another * **Higher IDs have priority** * Can “bully” lower numbered processes * Initiated by any process that suspects failure of the leader * Employs timeouts to detect failure * Tolerates processes crashing during elections

Question 34

Bully algorithm messages

Answer 34

* Operates with three types of messages * **Election announces an election** * **Answer responds to an election message** * **Coordination announces the identity of leader** * Algorithm is triggered by any process that detects (suspects) the leader to have crashed

Question 35

Pi detects failure of leader

Answer 35

* For any j \< i and any i \< k 1. **Broadcasts election message** 2. **Any Pk receiving election message responds with answe**r message and **starts another election** 3. Any Pj receiving election message does not respond ( as 4. **If P does not receive any answer message (timeout) then it broadcasts victory via coordination message** 5. **If Pi does receive answer message(s) then waits to receive coordinator message** 6. Restarts election, if no coordination message received

Question 36

Upon crash of a process BULLY ALGO

Answer 36

* **Start** of a **new process replacing crashed one with crashed one’s ID (e.g., read from disk)** * **Process may determine that it has the highest identifier, thus, pronounce itself as leader** * Even though system may have an existing leader (elected during crash) * **New process “bullies” current leader**