Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Distributed Algorithms > Time > Flashcards

Time Flashcards

1
Q

How is Consistency Maintenence achieved?

A

CM is acheived by knowing which update is the most recent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are 3 examples of where consistency maintenence is important?

A

Air traffic controllers
Authentication services (Kerberos)
Wireless sensor networks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an asynchronous system?

A

A system with no fixed upper bound on how long a messages take to deliver or on the time between processes. (Independence of timing)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a synchronous system?

A

A system that executes in rounds to ensure that processes are coordinated.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What happens in each round of execution in a synchronous system? (3)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are 3 types of synchronisation?

A

(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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

When are logical clocks used?

A

When only time ordering of certain events matters.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is UTC

A

Coordinated Universal Time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Centralised Algorithm?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the process of the Passive Time Server Centralised algorithm? (3)

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How can PTSCA be improved? (2)

A

Use multiple time servers to improve availability and accuracy of estimates.
Send multiple requests to improve accuracy.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the process of the Active Time Server Centralised Algorithm? (4)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What value does the ATSCA send?

A

THE CHANGE THAT NEEDS TO BE MADE TO THE TIME, not the actual new time value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the drawbacks of Centralised Algorithms? (2)

A

Single point of failure.
Not scalable for large systems.
Heavy burden on single nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What do Centralised Algorithms work well for? (1)

A

Intranets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the NTP?

A

Network Time Protocol

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How does the NTP operate?

A

Using layers. Primary servers access time directly from time source, secondary servers synchronise with primary servers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Why is event causality used for partial ordering?

A

We can’t get full synchronisation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Which events can be ordered? (2)

A

Events in the same process can be ordered using local time.

Pairs of events (send/receive)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are the 3 conditions of HBR?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

How is concurreny defined in HBR?

A

If there is no path from a -> b or b -> a.

a || b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the idea of Lamport’s Logicall Clocks?

A

Each system event has a timestamp associated to it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What are the conditions that LLC algorithms must satisfy?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is Lamport’s Algorithm? (3)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What property holds for Lamport’s Algorithm?

A

a->b implies Ci(a) <= Ci(b)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is the goal of a vector clock?

A

To detect causality.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What does a Vector Clock define? (2)

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is the implementation of Vector Clocks? (4)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What assumptions can be made on commuication channels? (2)

A

Reliable communication channels between processes (all messages are eventually sent).
Failed links between processes are eventually repaired.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is a disadvantage of Vector Clocks?

A

Poor scalability, vector clocks grow with system size.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What assumptions can be made on process behaviour? (1)

A

Processes only fail by crashing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is a correct process?

A

A correct process is a process that doesn’t fail at any point in the execution under consideration.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What are the 3 types of failure? (Define each)

A

Omission Failure : Process/channel fails to perform intended action.
Arbitary failure : Wrong process/channel behaviour.
Timing Failure : (Synchronous Systems)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What is a Failure Detector?

A

A service that processes queries regarding process failures.

35
Q

How are Failure Detectors usually implemented?

A

Using Local Failure Detectors. (One detector for each process)

36
Q

What is the process of an unreliable Failure Detector? (2)

A

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.

37
Q

What does a Reliable Failure Detector return?

A

Unsuspected or Failure (guarenteed)

38
Q

What is mutal exclusion?

A

A protocol that allows processes to enter, execute and exit critical sections one at a time.

39
Q

What are the 3 properties for a mutual exclusion protocol?

A

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.

40
Q

What is deadlock?

A

The event of no process being able to do steps to make progress.

41
Q

What is livelock?

A

The event of processes being able to complete steps but for none to be able to progress.

42
Q

Why do we need distributed mutal exclusion? (3)

A

To prevent interference/ensure consistency of shared resources.
Avoid concurrent updates.
Implement atomic operations

43
Q

What assumptions can be made about distributed mutual exclusion? (4)

A

N processes
Network is reliable but asynchronous
No process fails.
Processes spend finite time in CS

44
Q

What are the correctness aspects of distributed mutual exclusion? (3)

A

Safety : At most 1 process in CS.
Liveness: Requests to enter/exit CS succeed eventually.
Fairness: Access to CS happens in HBO.

45
Q

What are the performance aspects of distributed mutual exclusion?

A

Minimise messages in/out
Minimise client delay
Minimise synchronisation delay (in/out between processes)

46
Q

What is the process a Server Centralised Algorithm?

A

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.

47
Q

What are the correctness aspects of a Server Centralised Algorithm? (3)

A

Safety: Yes
Liveness: Yes
HBO: No

48
Q

What are the performance aspects of a Server Centralised Algorithm? EO,ED,EO,ED,SD

A

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)

49
Q

What are the 3 issues with a Server Centralised Algorithm?

A

Single point of failure
Server is bottleneck
Must elect server

50
Q

What is the Ring-Based Algorithm? (4)

A

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.

51
Q

What is are the correctness aspects for the Ring-Based Algorithm?

A

Safety: Yes
Liveness: yes
HBO: No

52
Q

What are the performance aspects of the Ring-Based Algorithm? BC, EO,EO,ED,ED,SD

A

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.

53
Q

What is the processof a multicast algorithm? (3)

A

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.

54
Q

What is the process of Ricart and Agrawala’s Algorithm?

Start, Enter CS, Received newRequest, Exit

A 
(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.
55
Q

What are the correctness aspects for Ricart and Agrawala’s Algorithm?

A

Safety: Yes
Liveness: Yes
HBO: Yes (always pick the lowest timestamp)

56
Q

What are the performance aspects of Ricarts and Agrawala’s Algorithm? BC,EO,EO,ED,ED,SD

A

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)

57
Q

What is the process of Maekawa’s Algorithm?

A

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.

58
Q

What are the 5 stepsof Maekawa’s Algorithm?

A

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.

59
Q

What is Maekawa’s Voting Algorithm?

Start, enter CS, receive Pi at Pj

A 
(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 = TRUE
60
Q

What is Maekawa’s Voting Algorithm? (exit CS, receiving release from Pi at Pj)

A 
(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 = FALSE
61
Q

What are the correctness aspects for Maekawa’s Voting Algorithm? (3)

A

Safety: Yes
Liveness: No, deadlock can occur
HBO: No

62
Q

What are the performace aspects of Maekawa’s Voting Algorithm?
EO,EO,ED,ED,SD

A

Enter overhead: k requests + k replies
Exit overhead: k releases
Enter/Exit delay: as in prev algorithms
Synchronisation delay: 2 messages

63
Q

How can deadlock be avoided in Maekawa’s Voting Algorithm?

A

Include timestamps within the request messages.

64
Q

Which algorithm can be adapted to handle faults?

A

Ricart and Agrawala’s algorithm can be adapted to tolerate process crashes, assuming that a reliable Fault Detector is available.

65
Q

Why do distributed systems need Leaders?

A

Leaders are needed to perform special tasks.

66
Q

What features must processes have for Leader Elections? (2)

A

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.

67
Q

What condition must hold for Leader Election?

A

All processes must agree on a leader and this leader must be non-faulty.

68
Q

What assumptions can be made for Leader Election? (6)

A

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.

69
Q

What is a participant?

A

A process engaged in an election.

70
Q

What is safety in Leader Election?

A

A participant Pi has elected(i) = Falsity or elected(i) = P, where P is a non-crashed process with the largest identifier.

71
Q

What is liveness for Leader Election?

A

All processes participate and eventually set elected(i) = P or crash.

72
Q

What do we look to minimise in Leader Election algorithms? (2)

A 
Total number of messages sent.
Turnaround time (number of serialised message transmissions in a singe run).
73
Q

What is a Ring-Based Algorithm?

A

Process P1 to Pn arranged in logical ring.

Each process knows and can communicate with its successor.

74
Q

In which systems are Ring-Based Algorithms used (leader election)?

A

In asynchronous systems.

75
Q

What is the Ring-Based Leader Election algorithm? (6)

A

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.

76
Q

What is the correctness of the Ring-Based LE algorithm?

A

Safety: Yes, only process with highest id can be elected.
Liveness: Yes, all live processes participate and and know who the new leader is.

77
Q

What is the performance of the Ring-Based LE algorithm?

A

Best case: Initiating process has highest id.
N election messages.
N elected messages
Turnaround: 2N messages

78
Q

What are the assumptions of the Bully Algorithm? (5)

A

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.

79
Q

What are the message types in the Bully Algorithm? (3)

A

Election, answer, coordinator

80
Q

In which systems is the Bully Algorithm used for LE?

A

In synchronous systems, with timeouts used to detect failure.

81
Q

What is the Bully Algorithm (6)?

A

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.

82
Q

What is the correctness of the Bully Algorithm?

A

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.

83
Q

What is the performance of the Bully Algorithm? Best case?

A

Best case: Highest id process detects failure and elect themselves.
Overhead: N-2 coordinator messages
Delay: 1 message

84
Q

What is the performance of the Bully Algorithm? Worst case?

A

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.

Distributed Algorithms (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions