Presence fault Flashcards
What is NTP?
Network Time Protocol
What are the NTP message parameters?
RFC 1305:
- Packets are UDP/IP
- Checksum-Based Error Detection
- Simple Connectionless Service
- No Guarantee of Delivery
- No Detection of Lost Packets
- Message Authentication (Optional)
Can NTP use IPv6 protocol?
All versions of NTP can use IPv4 protocol but only newer versions also support IPv6
What can go wrong with the time parameter of NTP?
Reference scale is Coordinated Universal Time (UTC).
As NTP’s time parameters are 64 bits, there will be a rollover in 2036 and a time of 0.0 is treated as an error.
What does it this algorithm do and how can you prove it?
01 upon a pulse
02 forall Pj included in N(i) do send (j,clocki)
03 max := clocki
04 forall Pj included in N(i) do
05 receive(clockj)
06 if clockj included in max then max := clockj
07 od
08 clocki := max + 1
This is the unbounded algorithm of a digital clock synchronisation.
A simple induction can prove that this version of the algorithm is correct:
If Pm holds the max clock value, by the i’th pulse every processor of distance i from Pm holds the maximal clock value.
Why did we have to create a bounded version of the algorithm for digital clock synchronisation?
Unbounded clocks is a drawback in self-stabilizing systems
The use of 2^64 possible values does not help creating the illusion of “unbounded”:
A single transient fault may cause the clock to reach the maximal clock value …
Which boundaries M can we use to make a bounded algorithm of the digital clock synchronisation?
max: M = ((n+1)d+1)
min: M = 2d+1
Why is this algorithm correct?
01 upon a pulse
02 forall Pj included in N(i) do send (j, clocki)
03 max := clocki
04 forall Pj included in N(i) do
05 receive(clockj)
06 if clockj > max then max := clockj
07 od
08 clocki := (max + 1) mod ((n +1)d +1)
The number of different clock values can only decrease, and is reduced to a single clock value.
If all the clock values are less than M-d we achieve sync before the modulo operation is applied.
If not all the clock values are less than M-d:
- By the pigeonhole principle, in any configuration there must be 2 clock values x and y, such that y-x >= d+1, and there is no other clock value between.
- After i steps, no clock value that is in (x+i, y+i).
- After M-y+1 pulses the system reaches a configuration in which all clock values are less than M-d.
Why is this algorithm correct?
01 upon a pulse
02 forall Pj included in N(i) do send (j,clocki)
03 min := clocki
04 forall Pj included in N(i) do
05 receive(clockj)
06 if clockj < min then min := clockj
07 od
08 clocki := (min + 1) mod (2d +1)
If no processor assigns 0 during the first d pulses – sync is achieved (can be shown by simple induction)
Else a processor assigns 0 during the first d pulses,
d pulses after this point a configuration c is reached such that there is no clock value greater than d: the first case holds
What could be the issue with the bounded algorithm for digital clock?
Digital clocks with a constant number of states are impossible.
Consider only deterministic algorithm:
There is no uniform digital clock-synchronization algorithm that uses only a constant number of states per processor.
What is a wait-free self-stabilizing clock-synchronization algorithm and how does it work?
Wait-free self-stabilizing clock-synchronization algorithm is a clock-sync. algorithm that copes with transient and napping faults.
Each non-faulty operating processor ignores the faulty processors and increments its clock value by one in every pulse.
Given a fixed integer k, once a processor pi works correctly for at least k time units and continues working correctly, the following properties hold:
- Adjustment: pi does not adjust its clock
- Agreement: pi’s clock agrees with the clock of every other processor that has also been working correctly for at least k time units
How does the algorithm for self-stabilizing unbounded clocks work?
Simple example for k =1, using the unbounded clocks:
In every step – each processor reads the clock values of the other processors, and chooses the maximal value (denote by x) and assigns x+1 to its clock.
How does the algorithm for self-stabilizing bounded clocks work?
The idea: identifying crashed processors and ignoring their values
Each processor P has:
P.clock included in {0… M-1}
for every Q P.count[Q] included in {0,1,2}
P is behind Q if P.count[Q]+1 (mod 3) = Q.count[P]
The implementation is based on the concept of the “rock, paper, scissors” children’s game.
What is the bounded solution for algorithms that fulfill the adjustment-agreement?
The program for P:
- Read every count and clock
- Find the processor set R that are not behind any other processor
- If R not empty then P finds a processor K with the maximal clock value in R and assigns P.clock := K.clock + 1 (mod M)
- For every processor Q, if Q is not behind P then P.count[Q] := P.count[Q] + 1 (mod 3)
What is the proof of the wait-free and self-stabilizing clock-synchronization algorithm?
The algorithm presented is a wait-free self-stabilizing clock-synchronization algorithm with k=2 (Th. 6.1)
- All processors that take a step at the same pulse, see the same view
- Each processor that executes a single step belongs to R in the next round, in which all the clock values are the same –> the agreement requirement holds
- Every processor chooses the maximal clock value of a processor in R, and increments it by 1 mod M –> the adjustment requirement holds
- The proof assumes an arbitrary start configuration –> the algorithm is both wait-free and self-stabilizing
