PDS - algorithms

Cristian’s algorithm

• Client sends request at T₀

• Server replies with T_server

• Client receives reply at T₁

• RTT = T₁-T₀

• Client sets clock to: T_server+RTT/2

• max skew: RTT/2 - δ_min

The algorithm takes the average delay as the average of lower and upper bound under the assumption of symmetric delays

Network time protocol (NTP)

Considering 2 processes that need to be synchronized, and exchange 2 messages, r and a, using the following sequence:

• q sends request (r) to p, q timestamps this as T_i-3

• p receives the message and timestamps the receipt with T_i-2

• p replies (a) sending it’s current clock T_i-1 to q

• q receives message a and timestamps the receipt as T_i

• q adapts clock C_q=C_p+o

Good to know:

• NTP has different operational modes: multicast (useful in low delay situations e.g. LAN), procedure call (see Cristian’s algorithm) and symmetric mode (algorithm given above).

• NTP achieves accuracies in the order of 1 to 50 ms.

Berkeley algorithm

1. Coordinator polls all machines for their time

2. Machines reply with their local time

3. Coordinator calculates the average time

4. Coordinator sends adjustment to each machine

5. All machines adjust to synchronized time

The key takeaway here is that this algorithm does not try to use an external reference time but just adjust to the average of all machines in the system.

IMPORTANT: if a clock needs to be updated to an earlier time, we don’t let it jump backwards in time but we let it run slower (or halt in the worst case) until other clocks catchup.

Distributed mutual exclusion - central approach

• Client sends request to server to enter the critical section

• Server grants access to client (if token available)

• Client notifies server it leaves the critical section

Token ring algorithm

All processes communicate in a logical ring structure, passing a token around. If a process doesn’t need the token it just passes it to the neighboring process, when a process does need the token it waits until it gets it and then enters the critical section.

Ricart-Agrawala algorithm

Each process in the system has following things:

• logical clock (to guarantee fairness)

• message queue to store pending requests

• state variable (Released, Wanted, Held)

The algorithm works as follows:

• REQUEST(p_i,T_i): multicast to all other processes

• Wait for N replies from all processes

• Enter CS when all replies are received

• Exit CS and send deferred reply

When a request is received:

• No interest in CS → REPLY immediately

• In CS → defer REPLY

• Wants CS → compare clocks (lower wins)

Maekawa voting

This algorithm tries to solve the scalability issues with Ricart-Agrawala by not multicasting to each process but by multicasting to a subset of processes (called the voting set).

The main thing here is knowing how to construct such a voting set and then it works like Ricart-Agrawala. It’s important to have logical clocks here to ensure the algorithm can’t get stuck and be in a deadlock.

Suzuki-Kasami algorithm

An extension of a token passing algorithm that not only works in ring-based networks but also in general networks.

When a process wants to enter the CS:

• increment it’s own request number

• multicast REQUEST to all other nodes

When a process gets the REQUEST:

• update request queue with this request

• If this process has the token send it to the requester

When the token holder finishes with CS:

• update the last array to indicate it is done

• if Q is non-empty forward token to the first process in the queue

• if Q is empty just hold the token

Raymond’s algorithm

A token passing algorithm for tree-based networks.

The root node of the tree is the token holder, at any time if a process wants access to the CS it sends a request towards the root via its parent.

The root changes, by swapping the parent variables between the processes, the node with the token becomes the new root.

Chang-Roberts (election) algorithm

assumes all processes are organized in a logical ring, where each node communicates with its successor.

• process that starts election sends <n, ID>

• all other processes compare received ID with its own

  • if the current ID is bigger, send <n, ID> through the ring

  • if the current ID is smaller, become inactive and just forward the received messages

• If the received <n, ID> is of the receiving node this node becomes the leader

• The leader sends <n> through the network in an announcement round.

Garcia-Molina (election) algorithm

This algorithm assumes that each process knows all other processes, and has a set of processes with larger ID values and a set of processes with smaller ID values.

• A process (p_j) starts an election by sending an election message to its set of processes with larger ID values.

• p_i gets this message and has not crashed it sends a reply back. and if it has not initiated an election, it will do so now

• If p_j gets replies it knows it’s not the process with the largest ID and will therefore not become the leader.

• When a process doesn’t get an answer after a time out T, it knows it’s the process with largest ID value and still active, so it will become the leader

• The newly elected leader will send a Coordinator message to all processes (with lower ID).

Franklin’s algorithm

A variation on the Chang-Roberts election algorithm, based on bidirectional communication. Each round, each active process follows the following steps:

• Sends token with process ID to both its neighbors

• Examines the 2 tokens received from its neighbors, if one or two tokens have an ID that’s bigger, the process turns passive (only forwarding tokens to neighbors)

• When only one active process is left (process receives its own token), this process becomes the leader

• One additional round is needed to announce the leader to all processes

Peterson’s algorithm

A variant of the Chang Roberts election algorithm, that also uses unidirectional communication in a ring. The difference here is that processes communicate with an alias, which can change from one round to another. Also the leader is not necessarily the process with the largest ID, but the largest alias.

each round, each active process follows following steps:

• sending alias to successor

• receives the alias from predecessor: alias(PD)

• if alias = alias(PD) → process is leader

• else:

  • send alias(PD) to successor

  • receives alias(PD2)

  • if alias(PD) > max(alias, alias(PD2)): alias = alias(PD) and node remains active

  • if alias(PD) < max(alias, alias(PD2)): node turns passive

The idea here is to get same performance as Franklin’s algorithm in a unidirectional ring-based network.

Dolev-Klawe-Rodeh algorithm

The same as Petersons election algorithm: unidirectional in a ring and usage of aliases.

A special leader message is sent by the last active node in order to inform the node with this ID that it is the leader. (This ensures a handover is done from the last active node to the node with the actual greatest ID)

Tree election algorithm

Assuming a tree topology, each node having a list of children and a link to the parent.

On each node:

• waits until messages are received from all neighbors, except one (parent)

• computes max(received IDs, own ID)

• passes max value to parent

• receives a message back from its parent with value max_parent

• compute max(max_p, max_parent)

• passes this max value to neighbors except parent

Echo algorithm with extinction

This algorithm works for any topology. Nodes essentially initiate a wave, and pass the wave messages to their neighbors.

each initiator start a run of the echo algorithm. The wave is tagged with the ID of the initiator. Only the wave with the largest ID completes. This initiator then becomes the leader.

When a node p participates in a wave tagged with q, and receives a message from a wave tagged with r:

• q<r: the sender becomes parent of p, and changes to wave tagged with r (abandons messages tagged with q)

• q>r: the node continues with wave q (drops messages from wave r)

• q=r: the sends a message to its parent once messages from all neighbors have arrived

Gallager-Humblet-Spira algorithm

a distributed Kruskal algorithm, where each tree has two variables: a name and a level (which is the max number of joins by any node in the tree)

edges can have a status: basic (undecided), branch, reject.

Messages are exchanged to determine the core edges, which interconnect two trees, join the trees and update the status of the edges (the core node = the end points of the core edges, with the largest ID can then become the leader)

Bracha-Toueg crash consensus algorithm

This algorithm assumes that less than half of the nodes crash and that each process has 2 variables: b = decision value (0 or 1) and w = weight of the process (approximates the number of processes that voted b in the previous round.

In each round each correct process sends a message (n, b_p, w_p) to all processes. Based on the first N-k messages received:

• messages from earlier or future rounds are dropped

• if w > N/2 for an incoming message: b_p=b

• else:

  • if most messages contain b=1: b_p=1

  • else b_p=0

• if w > N/2 for more than k incoming messages

  • p decides for b

  • p sends messages (n+1,b,N-k) and (n+2,b,N-k)

As soon as a process decides, the termination of the algorithm starts and all other processes are guaranteed to terminate within two rounds.

(This algorithm is a Las Vegas algorithm because it starts with random values for b and tries to reach consensus by exchanging messages)

Consensus with failure detection

Each process randomly chooses a value 0 or 1, the algorithm proceeds in n rounds with process p_n as coordinator:

• if not crashed it broadcasts its value

• each process waits for incoming message from p_n:

  • if the message arrives the process adopts the value for p_n

  • after time-out: it suspects p_n has crashed

• after N rounds, each correct process decides based on its current value

Chandra-Toueg consensus algorithm

This algorithm assumes the failure detector is less accurate. Updated version of the Consensus with failure detection and works with acknowledgment messages. This algorithm works well when k<N/2

Chandra-Toueg Byzantine consensus algorithm

A Byzantine consensus algorithm and is only possible if k < N/3. This algorithm includes a verification phase of votes (it’s assumed that votes can not be trusted and echoed to all processes). Values are accepted if more than (N+k)/2 processes confirm.

Makaney-Schneider algorithm

only works for k < N/3.

• collects clock values from all processes

• discards values for which fewer than N-k report a value (including ±delay)

• replaces all discarded and non-received values by an acceptable value

• takes the average of these N values as its new clock value

Itai-Rodeh election algorithm

Each node generates a random ID and passes this around in the ring. In case there is one largest ID this becomes the leader. Else a next round is done with these nodes only, where each node generates a new random ID and passes this around. These rounds continue until there is only one node with largest ID.

(This is a Las Vega algorithm, it’s always correct and will always terminate)

Echo algorithm with extinction (Anonymous networks)

Each active process at the start of an election round:

• select a random ID from 1 … N

• starts a wave, tagged with n (round number), ID_p, and s (size of subtree)

if a wave message arrives at process p:

• if n > n, or n = n and ID_j>ID_p: p marks the sender as parent, and changes to n and wave j

• if n < n, or n = n and ID_j<ID_p: the message is dropped

• if n = n and ID_j=ID_p: p sends a message to the parent once messages from all neighbors arrived

Itai-Rodeh ring size algorithm

A Monte Carlo algorithm for computing the size of an anonymous ring. The probability of an incorrect outcome can be arbitrarily close to zero, especially when IDs can be selected from a large domain.

a process p waits for message (est, ID, h) to consider following options:

• est < est_p: message is dropped

• est > est_p: p increases est_p:

  • h < est: p sends (est, ID, h+1) and est_p=est

  • h = est: est_p=est+1

• est = est_p:

  • h < est: p sends (est, ID, h+1)

  • h = est:

    • ID ≠ ID_p: est_p = est+1

    • ID = ID_p: message is dropped