Time and coordination (5)

Question 1

What relationship does events that are not related in the “happened- before” relation have?

Answer 1

They are concurrent.

Question 2

Why do we use logical clocks?

Answer 2

They are a way for processes to be able to agree about the order events have happened in.

Question 3

Where in the architecture are logical clocks located?

Answer 3

Between app- layer and the network. i.e. inside the middleware.

Question 4

What are the two rules for logical clocks?

Answer 4

LC1:
Each process must increment its logical clock with 1 before an event on the process is applied.

LC2:
When a process sends a message it piggybacks its own logical clock on the message. The receiver sets its own logical clock to the biggest of the two and applies LC1 before it timestamps the recv event.

Question 5

What info does vector clocks give us that logical clocks can not?

Answer 5

Logical clocks capture dependencies as a consequence of message exchange but not causality.
Vector clocks can catch causality as well.

Question 6

What are the 4 rules for vector clocks?

Answer 6

Each process p maintans a vector clock Vp of size N.
A timestamp for event a at process p: Vp(a)
VC1:
Vp[j] is initially 0 for all nodes j.
VC2:
p increments Vp[p] with 1 before each event timestamp.
VC3:
if p sends a message m, it piggybacks Vp on m.
VC4:
If (m, ts) is received by q, q computes Vq[j] to max(Vq[j], ts[j] for all j. Then it applies VC2.

Question 7

How is the (local) history of a process modelled?

Answer 7

A history for a process p is a sequence events and corresponding state at p.

Question 8

How is the global history of a system defined?

Answer 8

A collection of all local histories, on from each process.

Question 9

What is a cut of a global state?

Answer 9

A union of prefixes from some processes’ local histories. i.e. that we cut all events in the global history from a certain point to reason about it.

Question 10

What is a consistent cut?

Answer 10

If an event e is included in the cut, and an event f -> e, then f must be in the cut as well for it to be consistent.

Question 11

What is a linearisation?

Answer 11

A linearisation is an arbitrary extension of a partial ordering of events in global history. (basically that you also give an ordering to events in the global history that are concurrent)

Question 12

What does it mean that state S’ is reachable from state S?

Answer 12

State S’ is reachable from state S if there exists a linearization that starts in S and ends in S’.

Question 13

What is stable property?

Answer 13

If something is true in S, it is true in any state reachable from S.

Question 14

What is safety property?

Answer 14

If something is true in any state reachable from S0(initial state) it has the safety property.

Question 15

What is liveness property?

Answer 15

In any linearisation there is a state reachable from S0 where it is true.

Question 16

What are the steps in the procedure for starting a snapshot?

Answer 16

P logs its own state

P sends a marker over all outgoing links.

P starts to log incoming messages on all input channels

Question 17

What are the steps in the procedure for when process P receives a marker over channel c in the snapshot algorithm?

Answer 17

If p has not recorded its state:
- P records state
- P forwards the marker over alle out channels
- P sets the state of c to empty
- p starts to record incoming msgs on all other in channels
Else:
- P records the state of c to be all msgs received on c since P recorded its state

Question 18

What is “the marker sending rule” in the snapshot algorithm?

Answer 18

Processes must send a marker after they have recorded their state, but before they send any other message.

Question 19

What is “the marker- receiveing rule” in the snapshot algorithm?

Answer 19

A process that has not recorded its state must do so.

Question 20

What are the use cases of the snapshot algorithm?

Answer 20

checkpointing, i.e. making checkpoint that the application can roll back to after failure.

Debugging.

Deadlock and termination detection.

Question 21

What are the requirements of a distributed consensus algorithm?

Answer 21

Agreement: No two non-fault processes decide on different values.

Termination: If there are non- faulty processes, at least one of them decides.

Integrity(validity/non- triviality): If all non- faulty processes start with the same initial value v, then v is the only possible decision value for a non- faulty process.

Question 22

What are the requirements for a reliable multicast algorithm?

Answer 22

Termination: Every non-faulty process delivers a message.

Agreement: No two non-faulty processes deliver different messages

Validity: no spurious messages

Integrity: If the sender is non-faulty, it delivers the message it sent

Question 23

What are the requirements for a mutual exclusion algorithm?

Answer 23

Safety: At most one process can be in critical section at at a time.

Liveness(avoid starvation): Each request to entry/exit the critical section eventually succeeds.

Ordering: Entrance to the CS must observe the “happened- before” relation. (if f -> e then f should get in before e)

Question 24

Which mutual exclusion algorithms have we gone through?

Answer 24

Central server

Ring- based

Ricart & Agrawala algorithm(based on logical clocks)

Question 25

Which distributed leader election algorithms have we gone through?

Answer 25

The bully algorithm

Ring- based algorithm

(paxos in later lecture)

Question 26

What are the requirements for a distributed leader election algorithm?

Answer 26

Safety: Max one node will be leader at a time
Liveness: A leader will be elected.

Question 27

Explain Ricart and Agrawala algorithm for mutex

Answer 27

Orka ikke skrive inne hele sjekk notes

Question 28

Forklar the snapshot algorithm

Answer 28

P skal sende markør:

P lagrer egen lokal state, så sender den en markør gjennom på kanaler før den kan sende vanlige meldinger igjen.

Når Q mottar markør på kanal C1:

Hvis Q ikke har lagret sin lokale state.(dvs. den ikke har motatt markør tidligere):
- Lagre state på inkommende kanal som tom.
- Følg reglene for å sende markør.
Hvis Q allerede har lagret sin state.(den har motatt en markør tidligere):
- Lagre state for C som sekvensen av meldinger motatt langs C1 etter lokal state ble lagret og før Q mottok foreløpig markør.

Question 29

Forklar the bully algorithm

Answer 29

Prosessen som oppdager at coordinator har feilet sender election melding til prosessene som har større identifikator enn seg selv.
Den venter på ANSWER melding:
1. Om ingen svarer, setter prosessen seg selv til leder og sender COORDINATOR melding til alle prosesser med mindre identifikator.
2. Hvis en ANSWER melding blir motatt lar den prosessen som sendte ANSWER ta over og venter på COORDINATOR melding. Hvis ingen melding blir motatt starter den en ny election.

Hvis en prosess mottar en COORDINATOR melding, lagrer den identifikator i meldingen som ny coordinator.

Hvis en prosess mottar en ELECTION melding, sender den tilbake en answer melding og tar over ved å starte ny election.

Når en prosess recovers eller joiner systemet starter den ny election. Hvis den har størst identifikator gjør den seg selv til leder og annonserer det, selv om det allerede finnes en fungerende leder.