General Algorithms

Question 1

Describe M.E token passing in a Ring-based algorithm

Answer 1

A mutual exclusion token (in the form of a message) is passed from process to process in a single direction (e.g. clockwise)

Question 2

True or False?:

The ring topology is usually unrelated to the physical interconnections between the underlying computers

Answer 2

True

Question 3

In a Ring-based algorithm what 3 actions can a process take when it receives the token?

Answer 3

♦if it does not need to enter the CS, it passes the token onto its neighbour
♦ if it does need to enter the CS, then it keeps the token
♦ to exit CS, it sends the token onto its neighbour

Question 4

In Ricart and Agrawala’s algorithm what is the state at initialization?

Answer 4

On initialization

state := RELEASED;

Question 5

In Ricart and Agrawala’s algorithm what happens when a process wishes to enter the CS?

Answer 5

To enter the critical section
state := WANTED;
Multicast request to all processes; 
T := request’s timestamp;
Wait until (number of replies received = (N – 1));
state := HELD;

Question 6

In Ricart and Agrawala’s algorithm what happens when a process receives a request to enter the CS?

Answer 6

On receipt of a request  at pj (i ≠ j)
if (state = HELD or (state = WANTED and (T, pj) < (Ti, pi)))
then
      queue request from pi without replying;
else
       reply immediately to pi;
end if
To exit the critical section
state := RELEASED;
reply to any queued requests;

Question 7

Give a brief overview of Ricart and Agrawala’s algorithm.

Answer 7

 Implements mutual exclusion between N peer
processes based upon multicast
 Process requiring entry to a critical section multicasts
a request message
♦ Can enter the critical section only when all other
processes have replied to the message

Question 8

What are Election algorithms?

Answer 8

Algorithms for choosing a unique process to play a particular role

Question 9

In an election algorithm a process p can take which roles?

Answer 9

Be a participant – is engaged in some run of the election algorithm
Be a non-participant – not engaged in any election
Or has a variable elected(i), which will contain the identifier of the elected process

Question 10

The elected process chosen will be the one with

the largest ‘identifier’. Give possible examples of identifiers

Answer 10

ID may be any useful value, as long as IDs are unique and totally ordered.

E.g. could elect the process with the lowest computational load by having each process use <1/load,i> as its identifier, where load > 0 and the index i is used to order identifiers with the same load

Question 11

List Cristian’s algorithm for clock synchronisation for a process P, and a time server S — connected to a source of UTC.

Answer 11

1. P requests the time from S
2. After receiving the request from P, S prepares a response and appends the time T from its own clock.
3. P then sets its time to be T + RTT/2