11 - Coordination

Question 1

Mutual Exclusion

Answer 1

Processes share a resource which must be exclusive access

Question 2

Centralised algorithm

Answer 2

Single coordinator stores a queue and grants permission when applicable

Question 3

Distributed Algorithm

Answer 3

Process sends message to all other processes (with res name, pID and logical timestamp)

Process returns OK if no interest in resource or is waiting with lower priority. Reply is deferred otherwise

High knowledge and comms requirement. Every process is a point of failure. Not scalable

Question 4

Token Ring

Answer 4

Processes organised in logical ring
Token passed between them

Some topology knowledge. High comms due to constant passing of token. Problematic fault tolerance and limited scalability

Question 5

Election Algorithm Requirements

Answer 5

Uniqueness (of a leader)
Termination (must end)
Agreement (for all processes)

Question 6

Bully algorithm Strong assumptions

Answer 6

Each process knows all higher pID processes
Synchronous Comms - timeouts useful
Reliable message delivery
Processes allowed to crash

Question 7

Bully algorithm

Answer 7

Elect active process with highest ID

Pk: ELECTION message is sent to all processes with higher IDs.
If no response then Pk wins and sends COORDINATOR message to all others.
If OK response, then Pk waits for COORDINATOR message or restarts election if timeout

Question 8

Rough number of messages in bully algorithm

Answer 8

N^2

Question 9

Ring Algorithm Assumptions

Answer 9

Processes in ring (knows successor)
Async comms enough
Reliable message delivery
Processes allowed to crash

Question 10

Ring algorithm election

Answer 10

Any process starts by sending ELECTION to successor with a list
Receiver ACKs, passes it on with itself in the list
Once message returns, it sends COORDINATOR message around with list of all living processes
Highest pID is new coordinator

Question 11

num of messages in ring algorithm

Answer 11

N messages

Question 12

Election in Wireless assumtpions

Answer 12

Processes know current neighbors
Async comms enough (if neighbours are known, comms reliable and no crashing)
Reliable message delivery
Processes should not crash

Question 13

Wireless Net Election

Answer 13

Elect most suitable process (eg with highest battery capacity)

Any process can broadscast ELECTION

if received for first time:
- set sender as parent
- Broadcast to neighbourhood N, not parent
- Wait until every process has ACK broadcast
- ACK to parent
- Recive info from each child
- Determine best process and send info to parent

Otherwise:
- ACK