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)