Time Flashcards
How is Consistency Maintenence achieved?
CM is acheived by knowing which update is the most recent.
What are 3 examples of where consistency maintenence is important?
Air traffic controllers
Authentication services (Kerberos)
Wireless sensor networks
What is an asynchronous system?
A system with no fixed upper bound on how long a messages take to deliver or on the time between processes. (Independence of timing)
What is a synchronous system?
A system that executes in rounds to ensure that processes are coordinated.
What happens in each round of execution in a synchronous system? (3)
A process can send a message to all its neighbours.
A process can receive messages.
A process can do computation based upon the messages it receives.
What are 3 types of synchronisation?
(Full) synchronisation - Not 100%, but can be achieved within a certain bound of accuracy.
External synchronisation - Processes are synchronised to an external time source - like a time server.
Internal synchronisation - Using external coordinator.
When are logical clocks used?
When only time ordering of certain events matters.
What is UTC
Coordinated Universal Time
What is a Centralised Algorithm?
An algorithm that uses a ‘time server node’ to act as the time reference for the whole system.
All nodes are synchronised to this clock.
What is the process of the Passive Time Server Centralised algorithm? (3)
Processes send ‘t=?’ to time server node (TS).
TS replies with time according to its clock.
P updates its time to t = t + T(round)/2.
How can PTSCA be improved? (2)
Use multiple time servers to improve availability and accuracy of estimates.
Send multiple requests to improve accuracy.
What is the process of the Active Time Server Centralised Algorithm? (4)
Node M is elected as master.
M polls all nodes actively and periodically for their clocks.
M estimates the local time using averages and round trip times.
M replies to each process with the changes to be made to their clock.
What value does the ATSCA send?
THE CHANGE THAT NEEDS TO BE MADE TO THE TIME, not the actual new time value.
What are the drawbacks of Centralised Algorithms? (2)
Single point of failure.
Not scalable for large systems.
Heavy burden on single nodes.
What do Centralised Algorithms work well for? (1)
Intranets
What is the NTP?
Network Time Protocol
How does the NTP operate?
Using layers. Primary servers access time directly from time source, secondary servers synchronise with primary servers.
Why is event causality used for partial ordering?
We can’t get full synchronisation.
Which events can be ordered? (2)
Events in the same process can be ordered using local time.
Pairs of events (send/receive)
What are the 3 conditions of HBR?
If a and b are in the same process, and a occurs first, then a -> b.
If a is sending message m and b is the receipt of message m, then a -> b.
If a -> b, b -> c, then a -> c. (Transitive)
How is concurreny defined in HBR?
If there is no path from a -> b or b -> a.
a || b
What is the idea of Lamport’s Logicall Clocks?
Each system event has a timestamp associated to it.
What are the conditions that LLC algorithms must satisfy?
If a and b are in the same process Pi, and a -> b, then Ci(a) < Ci(b).
If Pi sends a message m as a, and Pj receives message m as b, then Ci(a) < Ci(b).
A clock Ci associated with Pi must always go forwards. (Monotonically ascending).
What is Lamport’s Algorithm? (3)
Pi increments Ci before assigining a timestamp to an event.
When Pi sends m at event a, m contains a timestamp Tm = Ci(a).
When Pj receives m, it sets Cj greater than or equal to its present value, but greater than Tm.
What property holds for Lamport’s Algorithm?
a->b implies Ci(a) <= Ci(b)
What is the goal of a vector clock?
To detect causality.
What does a Vector Clock define? (2)
A mapping V : {Ev -> [int]} - A set of events to list of ints (vector clocks).
An ordering : For all a,b : a < B <=> V(a) < V(b)
What is the implementation of Vector Clocks? (4)
Initialise all vector clocks to 0.
For each local event in Pi, increment the ith vector clock.
When process i sends a message, it includes the updated V.
When process j receives a message from Pi, it updates V[j] and the rest of the clocks if its value of them at position k is less than the vector clock from Pi.
What assumptions can be made on commuication channels? (2)
Reliable communication channels between processes (all messages are eventually sent).
Failed links between processes are eventually repaired.
What is a disadvantage of Vector Clocks?
Poor scalability, vector clocks grow with system size.
What assumptions can be made on process behaviour? (1)
Processes only fail by crashing
What is a correct process?
A correct process is a process that doesn’t fail at any point in the execution under consideration.
What are the 3 types of failure? (Define each)
Omission Failure : Process/channel fails to perform intended action.
Arbitary failure : Wrong process/channel behaviour.
Timing Failure : (Synchronous Systems)
What is a Failure Detector?
A service that processes queries regarding process failures.
How are Failure Detectors usually implemented?
Using Local Failure Detectors. (One detector for each process)
What is the process of an unreliable Failure Detector? (2)
Returns ‘Unsuspected’ or ‘Suspected’.
Each process sends alive message to everyone else every T seconds.
If LFD doesn’t receive an alive message in T + (MaxTrans) seconds, it reports ‘Suspected’ failure.
What does a Reliable Failure Detector return?
Unsuspected or Failure (guarenteed)
What is mutal exclusion?
A protocol that allows processes to enter, execute and exit critical sections one at a time.
What are the 3 properties for a mutual exclusion protocol?
Safety : Only 1 process at a time in CS.
Freedom from deadlock : At least 1 process can enter or exit a CS at a time.
Progress : Every process waiting for a CS will eventually be let in.
What is deadlock?
The event of no process being able to do steps to make progress.
What is livelock?
The event of processes being able to complete steps but for none to be able to progress.
Why do we need distributed mutal exclusion? (3)
To prevent interference/ensure consistency of shared resources.
Avoid concurrent updates.
Implement atomic operations
What assumptions can be made about distributed mutual exclusion? (4)
N processes
Network is reliable but asynchronous
No process fails.
Processes spend finite time in CS
What are the correctness aspects of distributed mutual exclusion? (3)
Safety : At most 1 process in CS.
Liveness: Requests to enter/exit CS succeed eventually.
Fairness: Access to CS happens in HBO.
What are the performance aspects of distributed mutual exclusion?
Minimise messages in/out
Minimise client delay
Minimise synchronisation delay (in/out between processes)
What is the process a Server Centralised Algorithm?
Server controls a token.
A requet is sent to the server.
If the server has the token, it grants it to the process, otherwise the process waits.
When the process exits the CS, it returns the token to the server.
What are the correctness aspects of a Server Centralised Algorithm? (3)
Safety: Yes
Liveness: Yes
HBO: No
What are the performance aspects of a Server Centralised Algorithm? EO,ED,EO,ED,SD
Enter overhead: 2 messages (grant/release)
Exit overhead : 1 message (release)
Enter Delay: Time between request and grant.
Exit Delay: None
Synchronisation Delay: 2 messages (grant/release)
What are the 3 issues with a Server Centralised Algorithm?
Single point of failure
Server is bottleneck
Must elect server
What is the Ring-Based Algorithm? (4)
Processes are arranged in logical ring.
Token is passed around the ring.
Enter CS if holding token.
Send token to next process when exiting the CS.
What is are the correctness aspects for the Ring-Based Algorithm?
Safety: Yes
Liveness: yes
HBO: No
What are the performance aspects of the Ring-Based Algorithm? BC, EO,EO,ED,ED,SD
Bandwidth consumption: Token keeps circulating
Enter overhead: 0 - N messages
Exit overhead : 1 message
Enter Delay: Delay for 0 - N messages
Exit Delay: None
Synchronisation Delay: Delay for 1 - N messages.
What is the processof a multicast algorithm? (3)
Process Pi sends a REQUEST for the token to all processes.
Pi can enter the CS if all other processes reply.
If Pi receives a REQUEST, it can only reply if the requests timestamp is less than its own.
What is the process of Ricart and Agrawala’s Algorithm?
Start, Enter CS, Received newRequest, Exit
(Start) Set state to RELEASED. (To enter CS) Set state to WANTED. Send a RESQUEST to all, with timestamp T. Wait for all responses Set state to HELD (Received newRequest) if (state == HELD) || T < newT, add newRequest to queue. else reply immediately. (Exit) Set state to RELEASED Reply to any requests on queue.
What are the correctness aspects for Ricart and Agrawala’s Algorithm?
Safety: Yes
Liveness: Yes
HBO: Yes (always pick the lowest timestamp)
What are the performance aspects of Ricarts and Agrawala’s Algorithm? BC,EO,EO,ED,ED,SD
Bandwidth Consumption: No token circulating
Enter Overhead: 2(N-1)
Exit Overhead 0 - N messages
Entry Delay: Delay between request and getting all replies.
Exit Delay: None
Synchronisation Delay: Delay for one message only (message from process leaving CS)
What is the process of Maekawa’s Algorithm?
Processes split into a number of subsets of size K.
If processes Pi and Pj wish to enter CS, an arbitrator is chosen from (Si/\Sj).
The arbitrator chooses which process can enter and defers the other.
What are the 5 stepsof Maekawa’s Algorithm?
To enter its CS, Pi sends a timestamped request to all processes in Si.
Processes in Si respond to the lowest timestamped request.
Pi enters its CS when it receives replys from all processes of Si.
During the exit from its CS, Pi sends a release message to all processes in Si.
Processes in Si reply to the lowest timestamped request.
What is Maekawa’s Voting Algorithm?
Start, enter CS, receive Pi at Pj
(Start)
state = RELEASED
voted = FALSE
(Enter CS)
state = WANTED
multicast REQUEST to all
wait for K replies
state = HELD
(Receive request from Pi at Pj)
if(state == HELD || voted == TRUE)
queue request
else
send VOTE to Pi
voted = TRUEWhat is Maekawa’s Voting Algorithm? (exit CS, receiving release from Pi at Pj)
(Exit CS)
state = RELEASED
multicast RELEASE to all processes
(Receiving release from Pi at Pj)
if(queue is not empty)
send VOTE to queue[head]
dequeue(queue)
voted = TRUE
else
voted = FALSEWhat are the correctness aspects for Maekawa’s Voting Algorithm? (3)
Safety: Yes
Liveness: No, deadlock can occur
HBO: No
What are the performace aspects of Maekawa’s Voting Algorithm?
EO,EO,ED,ED,SD
Enter overhead: k requests + k replies
Exit overhead: k releases
Enter/Exit delay: as in prev algorithms
Synchronisation delay: 2 messages
How can deadlock be avoided in Maekawa’s Voting Algorithm?
Include timestamps within the request messages.
Which algorithm can be adapted to handle faults?
Ricart and Agrawala’s algorithm can be adapted to tolerate process crashes, assuming that a reliable Fault Detector is available.
Why do distributed systems need Leaders?
Leaders are needed to perform special tasks.
What features must processes have for Leader Elections? (2)
Each process Pi needs a unique identifier, uid(i) from a totally ordered set V.
Each process Pi needs a variable L(i) which represents the indentifier of its leader.
What condition must hold for Leader Election?
All processes must agree on a leader and this leader must be non-faulty.
What assumptions can be made for Leader Election? (6)
N processes with unique, totally ordered indentifiers.
Process with largest id must win election.
Messages are eventually delivered.
Each process can only call one election.
Multiple concurrent elections can be called by different processes.
What is a participant?
A process engaged in an election.
What is safety in Leader Election?
A participant Pi has elected(i) = Falsity or elected(i) = P, where P is a non-crashed process with the largest identifier.
What is liveness for Leader Election?
All processes participate and eventually set elected(i) = P or crash.
What do we look to minimise in Leader Election algorithms? (2)
Total number of messages sent. Turnaround time (number of serialised message transmissions in a singe run).
What is a Ring-Based Algorithm?
Process P1 to Pn arranged in logical ring.
Each process knows and can communicate with its successor.
In which systems are Ring-Based Algorithms used (leader election)?
In asynchronous systems.
What is the Ring-Based Leader Election algorithm? (6)
A process Pi notices failure of coordinator.
Pi creates an election message, adds itself to the message and sends it to successor.
Each process nominates itself by adding its id to the message and passes it around the ring.
The initialiser notices when the message returns since the message contains its own id.
Pi selects new coordinator from highest id in the list, and sends a coordinator message around the ring to notify all processes of the new coordinator.
The coordinator message goes round the ring once and is then removed.
What is the correctness of the Ring-Based LE algorithm?
Safety: Yes, only process with highest id can be elected.
Liveness: Yes, all live processes participate and and know who the new leader is.
What is the performance of the Ring-Based LE algorithm?
Best case: Initiating process has highest id.
N election messages.
N elected messages
Turnaround: 2N messages
What are the assumptions of the Bully Algorithm? (5)
Processes can crash
Message delivery reliable
Each process knows all other processes and can communicate with them.
Each process knows which processes have higher ids.
The process with the largest id out of non-failing processes must be elected leader.
What are the message types in the Bully Algorithm? (3)
Election, answer, coordinator
In which systems is the Bully Algorithm used for LE?
In synchronous systems, with timeouts used to detect failure.
What is the Bully Algorithm (6)?
Process Pi detects failure of leader and starts election message to every process with higher id.
If it receives a response, it waits for a coordinator message from the new leader.
If no node responds, Pi assumes it is the new leader and sends coordinator message to all processes.
If Pi is expecting a coordinator message and doesn’t receive one within a timeout period, it assums the new leader has failed and starts a new election.
Receiving an election message - Send answer back if higher.
Receiving coordinator message - Set elected(i) to new coordinator.
What is the correctness of the Bully Algorithm?
Safety: No, if a failed process is replaced during an election, lower-id processes may have conflicting coordinators.
Liveness: Yes, all live processes take part and know the new coordinator.
What is the performance of the Bully Algorithm? Best case?
Best case: Highest id process detects failure and elect themselves.
Overhead: N-2 coordinator messages
Delay: 1 message
What is the performance of the Bully Algorithm? Worst case?
Worst case:
Overhead : Each Pi sends n-i messages.
Each Pj sends j-1 replies.
If the would-be leader doesn’t fail, it will send n-1
coordinator messages.
If it does fail, each Pi will start a new election and repeat
steps 1 and 2.
Since n-1 processes can fail, these steps are repeated n-
1 times.
Time complexity = O(n^3)
Delay: Delay experience sendign election and answer messages.
