Algorithms in DS Flashcards Preview

COMP18112 - Distributed Systems > Algorithms in DS > Flashcards

Flashcards in Algorithms in DS Deck (21)
Loading flashcards...
1
Q

What is Deadlock?

A

Trains approach each other at a crossing, both come to a full stop. Neither shall start up again until the other has gone

2
Q

Conditions for Deadlock? (4)

A

Mutual Exclusion- one resource must be non-shareable

Hold and Wait- A process is holding a resource and is requesting one currently held by a different process

No Preemption- Once a process has acquired a resource, nothing can force it to relinquish

Circular Wait- Processes waiting for one another in such a way that there is a cycle of dependencies between them

3
Q

Strategies for dealing with deadlock?

A

Prevent- make sure the four conditions are never possible at the same time

Avoid- Even if it is possible for all 4 conditions to be true at the same time, make sure it doesn’t happen

Detect- if all 4 conditions do hold at the same time, do something about it

4
Q

What two architectures have we seen for DS? Describe

A

Client-Server: server processes coordinate communication on behalf of clients. Roles are different.

Peer-to-Peer: Processes talk directly to one another to avoid the overhead of going through a server. Peers are more or less homogeneous.

5
Q

What is a thin client?

A

The terminal can’t provide much functionality. All the processing and interpretation is being done on the server which takes on most of the work. Every client you add increases the load.

6
Q

What is a thick client?

A

Has a fair amount of functionality that can operate independently of its corresponding server.
Increased administrative overhead.

7
Q

What is Data synchronisation and Process synchronisation?

A

Data synchronisation: keeping multiple copies of a dataset in coherence with one another.

Process Synchronisation: multiple process need to act together to achieve a certain overall purpose

8
Q

Describe the two generals problem

A

two generals are only able to communicate with one another by sending a messenger through enemy territory. The experiment asks how they might reach an agreement on the time to launch an attack, while knowing that any messenger they send could be captured.

9
Q

Give the argument for reductio ad absurdum for the two generals problem

A

Take an exchange of messages that appears in a coordinated solution. Assume the last message gets lost, if they still succeed the message wasn’t vital. Repeat until no messages are exchanged. No messages isn’t a solution so our original assumption was wrong

10
Q

What is the only thing we can say about when a message will be received?

A

a message wont arrive at its destination before it is sent

11
Q

What is a logical clock?

A

can be used to give a distributed incremental pseudo time to events in a DS

12
Q

Give an example of a logical clock

A

Lamport Clocks:
each processor has a logical clock
when an event occurs on a processor, it increments its clock by 1
When a processor sends a message it also sends it logical clock to the other processor.
When the processor receives the message, if its logical clock < (other clock + 1) then clock = (other clock + 1) else keep its clock

13
Q

What is a critical section?

A

A sequence of events that have to occur successfully in a particular order otherwise abort

14
Q

How do you create a critical section?

A

Create a Mutex (mutual exclusion lock). Once one client has locked the mutex, noone else can. Once finished, it is unlocked

15
Q

Describe the process of a process wanting to enter a critical section

Describe how processes respond

A

Generate timestamp
Send request (process, timestamp) to everyone
Wait for a reply from everyone to say its ok
Enter critical section

Response: if already in critical section, defer reply. Otherwise send reply. If this process wants to enter critical section and its time stamp is > other, allow the other. Otherwise, defer reply

16
Q

How do we allow for ‘rollback’ i.e. undoing intermediate stems to return to a safe state?

A

Two-phase Commit

17
Q

Describe the Two-phase commit protocol

A

Coordinator node requests transaction, sends a request to all participants
All participants respond: VOTE_COMMIT or VOTE_ABORT
Log their current state and perform transaction
Log their vote
Coordinator looks at votes
If everyone commits, GLOBAL_COMMIT otherwise GLOBAL_ABORT
Participants record this decision locally.
If it was ABORT, all participants ROLL BACK to their previous safe state

18
Q

How is a coordinator chosen from a set of nodes? Describe the algorithm

A

Bully Algorithm

P sends an ELECTION message to all processes of a higher number
If no-one responds, P has won and is coordinator. It informs all nodes.
If one of the higher nodes Q answers, P concedes it is not the winner, Q begins election process again.

19
Q

What are the two assumptions of the bully algorithm?

A

It is possible to assign ordering to nodes

relies on the use of timeouts to decide when to give up waiting for responses from nodes that have potentially died.

20
Q

Describe Cristian’s Algorithm for clock synchronisation

A

P requests time from S
S prepares response and appends time T from its clock
P sets its time as T + RTT/2

21
Q

Describe The Berkeley Algorithm for clock synchronisation

A

1) A master is chosen via an election process such as the bully algorithm
2) Master polls slaves who reply with their time
3) Master observers RTT and estimates the time of each slave and itself
4) Master averages clock times, ignoring anomalies
5) Master sends out the amount each slave must adjust its clock