Time Flashcards

Question

What property holds for Lamport's Algorithm?

Answer 1

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

Answer 2

To detect causality.

Answer 3

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)

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

Answer 5

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

Answer 6

Poor scalability, vector clocks grow with system size.

Answer 7

Processes only fail by crashing

Answer 8

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

Answer 9

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

Answer 10

A service that processes queries regarding process failures.

Answer 11

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

Answer 12

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.

Answer 13

Unsuspected or Failure (guarenteed)

Answer 14

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

Answer 15

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.

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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

Answer 22

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.

Answer 23

Safety: Yes Liveness: Yes HBO: No

Answer 24

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)

Answer 25

Single point of failure Server is bottleneck Must elect server

Answer 26

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.

Answer 27

Safety: Yes Liveness: yes HBO: No

Answer 28

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.

Answer 29

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.

Answer 30

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

Answer 31

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

Answer 32

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)

Answer 33

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.

Answer 34

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.

Answer 35

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

Answer 36

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

Answer 37

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

Answer 38

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

Answer 39

Include timestamps within the request messages.

Answer 40

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

Answer 41

Leaders are needed to perform special tasks.

Answer 42

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.

Answer 43

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

Answer 44

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.

Answer 45

A process engaged in an election.

Answer 46

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

Answer 47

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

Answer 48

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

Answer 49

Process P1 to Pn arranged in logical ring. | Each process knows and can communicate with its successor.

Answer 50

In asynchronous systems.

Answer 51

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.

Answer 52

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

Answer 53

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

Answer 54

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.

Answer 55

Election, answer, coordinator

Answer 56

In synchronous systems, with timeouts used to detect failure.

Answer 57

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.

Answer 58

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.

Answer 59

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

Answer 60

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.