Time and coordination (5) Flashcards
(29 cards)
What relationship does events that are not related in the “happened- before” relation have?
They are concurrent.
Why do we use logical clocks?
They are a way for processes to be able to agree about the order events have happened in.
Where in the architecture are logical clocks located?
Between app- layer and the network. i.e. inside the middleware.
What are the two rules for logical clocks?
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.
What info does vector clocks give us that logical clocks can not?
Logical clocks capture dependencies as a consequence of message exchange but not causality.
Vector clocks can catch causality as well.
What are the 4 rules for vector clocks?
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.
How is the (local) history of a process modelled?
A history for a process p is a sequence events and corresponding state at p.
How is the global history of a system defined?
A collection of all local histories, on from each process.
What is a cut of a global state?
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.
What is a consistent cut?
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.
What is a linearisation?
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)
What does it mean that state S’ is reachable from state S?
State S’ is reachable from state S if there exists a linearization that starts in S and ends in S’.
What is stable property?
If something is true in S, it is true in any state reachable from S.
What is safety property?
If something is true in any state reachable from S0(initial state) it has the safety property.
What is liveness property?
In any linearisation there is a state reachable from S0 where it is true.
What are the steps in the procedure for starting a snapshot?
P logs its own state
P sends a marker over all outgoing links.
P starts to log incoming messages on all input channels
What are the steps in the procedure for when process P receives a marker over channel c in the snapshot algorithm?
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
What is “the marker sending rule” in the snapshot algorithm?
Processes must send a marker after they have recorded their state, but before they send any other message.
What is “the marker- receiveing rule” in the snapshot algorithm?
A process that has not recorded its state must do so.
What are the use cases of the snapshot algorithm?
checkpointing, i.e. making checkpoint that the application can roll back to after failure.
Debugging.
Deadlock and termination detection.
What are the requirements of a distributed consensus algorithm?
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.
What are the requirements for a reliable multicast algorithm?
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
What are the requirements for a mutual exclusion algorithm?
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)
Which mutual exclusion algorithms have we gone through?
Central server
Ring- based
Ricart & Agrawala algorithm(based on logical clocks)
