Distributed Systems ETH 2020

No.

If a system is in a bivalent configuration it must reach a critical configuration within finite time or it does not always solve consensus.

If a config tree contains a critical configuration crashing a single node can create a bivalent leaf

--> NO

It achieves binary consensus with expected runtime O(2^n) if up to f < n/2 nodes crash.

(there is no consensus algorithm for the asynchronous model that tolerates f >= n/2 failures)

Use a shared coin instead of choosing v_i completely randomly.

A node which can have arbitrary behaviour (also malicious) is called byzantine.

1. any-input validity: decision value must be the input of any node
2. correct-input validity: decision value must the the input of a correct node
3. all-same validity: if all correct nodes start with the same input v, the decision value must be v
4. median validity: if the input values are orderable byzantine outliers can be prevented by agreeing on a value close to the median of the correct input values

f < n/3

There is at least one phase with a correct king and after such a phase the correct nodes will not change their value anymore.

f+1

Ben-Or for f < n/10
worst case running time: exponential in number of nodes n
If on line 12 a random oracle call is used instead only a constant number of rounds is expected

The blackboard is a trusted authority which supports two operations: write message, read all written values.

uses an optimal n^2 coin flips

cannot tolerate a single byzantine

• best effort broadcast: ensures that a message that is sent from a correct node to another will eventually be received and accepted
• reliable broadcast: ensures that the nodes eventually agree on all accepted messages

FIFO reliable broadcast defines an order in which the messages are accepted in the system.

Tolerates f<n/3 byz, f<n/2 crashes

Let t,n ∈ N with 1 ≤ t ≤ n. An algorithm that distributes a secret among n participants such that t participants need to collaborate to recover the secret is called a (t, n)-threshold secret sharing scheme.

1: Each node has a public key that is known to all nodes.
2: Let r be the current round of Algorithm 17.21
3: Broadcast msg(r)u, i.e., round number r signed by node u
4: Compute hv = hash(msg(r)v) for all received messages msg(r)v 5: Let hmin = minv hv
6: return least significant bit of hmin

An execution E is a set of operations on one or multiple objects executed by a set of nodes.

An execution restricted to a single node is a sequential execution. All operations are executed sequentially.

Two executions are semantically equivalent if they contain exactly the same operations and each pair of corresponding operations has the same effect in both executions

An execution E is called linearizable if there is a sequence of operations S such that

• S is correct and semantically equivalent to E
• whenever f<g for two operations then also f<g in S

E is linearizable iff there exist linearization points (some point f_ in f) such that the sequential execution S that results in ordering the operations according to those is semantically equivalent to E.

E is called sequentially consistent if there is a sequence of operations S such that

• S is correct and semantically equivalent to E
• whenever f<g for two operations on the same node in E then also f<g in S

E is called quiescently consistent if there is a sequence of operations S such that 

• S is correct and semantically equivalent to E
• let t be some quiescent point, for every t and every pair of operations g<t and h>t we also have g<h in S

linearizability --> sequential and quiescent consistency

nothing else

A system is called linearizable if it ensures that every possible execution is linearizable. (same for the consistencies)

A consistency model is called composable if it holds:
If for every object o the restricted execution E|o (only operations involving o) is consistent then also E is consistent.

Linearizability is composable.
Sequential consistency is not composable.

An execution E is called happened-before consistent if there is a sequence of operations S such that:

• S is correct and semantically equivalent to E
• whenever f -> g for two operations also f < g in S

This is equal to sequential consistency.

A logical clock is a family of functions c_u that map every operation on node u to some logical time c_u(f) such that the happened before relation -> is respected:

g -> h --> c_u(g) < c_u(h)

strong logical clock: <-->

Lamport clocks are logical clocks.

With define c_u < c_v iff so for all entries -> vector clocks are strong logical clocks.

A cut C (prefix of distributed execution) is a consistent snapshot if for every operation g in C with f -> g C also contains f

The concurrency measure of an execution E = (S_1, ..., S_n) is defined as the ratio:

\(m(e) = { \mu - \mu_s \over \mu_c - \mu_s}\)

With \(\mu\) being the number of consistent snapshots of E.

A span s is a named and timed operation representing a contiguous sequence of operations on one node. A span has a start and finish time. (= Tasks)

A span may causally depend on other spans -> ChildOf: parent depends on result of child / FollowsFrom: just invokes child.

A trace is the graph representing the hierarchy of spans.

No SoF, however one node crashes -> requestion node waits forever.

Clock error / skew is the difference between two clocks 

\(t = (1 + \delta)t^* + \zeta(t^*)\)

Drift \(\delta\) is the predictable clock error.
Jitter \(\zeta\) is the unpredictablle random noise of the clock error