Karten 129 Karten
Lernende 2 Lernende
Sprache English
Stufe Universität
Erstellt / Aktualisiert 15.01.2021 / 23.01.2021
Lizenzierung Keine Angabe
0 Exakte Antworten 129 Text Antworten 0 Multiple Choice Antworten
Fenster schliessen

What is a ticket and what properties does it have?

A ticket is a weaker form of a lock with the following properties:

  1. reissuable: server can issue more tickets even if previous ones not yet returned
  2. expiration: server only accepts most recently issued ticket
Fenster schliessen

What does the Paxos Protocol look like?

Lizenzierung: Keine Angabe

a message propose(t,c) is chosen if it is stored by a majority of servers


if a command c is executed by some servers, all servers eventually execute c

Fenster schliessen

Define consensus and name its properties.

There are n nodes of which at most f might crash (n-f correct). Node i starts with an input value v_i. The nodes must decide for one of those values satisfying the following properties:

  1. agreement: all correct nodes decide for the same value
  2. termination: all correct nodes terminate in finite time
  3. validity: the decision must be an input value of a node
Fenster schliessen

Define configuration and critical configuration.

  • We say that a system is fully defined (at any point during the execution) by its configuration C. The configuration includes the state of every node, and all messages that are in transit (sent but not yet received).
  • C is critical if C is bivalent but all configurations that are direct children of C are univalent
Fenster schliessen

Define univalent and bivalent.

  • A configuration C is univalent if the decision value is determined independently of what happens afterwards (only one decision is possible). (univalent for value v -> v-valent)
    Nodes need not be aware of this!
  • C is bivalent if the nodes might decide for 0 or 1
Fenster schliessen

Define configuration tree.

The configuration tree is a directed tree of configurations. Its root is C0 (fully characterised by the input values), The edges are transitions (characterised by event (u,m), node u receiving message m), every configuration has all applicable transitions as outgoing edges.

Fenster schliessen

Is there a deterministic algorithm which always achieves consensus in the asynchronous model with f>0?


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

Fenster schliessen

What does the randomized Consensus Protocol look like?

Lizenzierung: Keine Angabe

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)