-
Show that a predicate
F
satisfies the equation F = Possibly(F) iff
F is
a stable predicate.
-
Show that the set of predicates F that satisfy
Definitely(F) = Possibly(F) is weaker than the set of stable
predicate. Such predicates have been called observer
independent.
-
Give an efficient detection
protocol for observer independent properties.
-
In Section 7.4.1. of
Chapter 7 in Distributed Systems, Second Edition, the following
two conditions were given for agreement:
IC1: All non-faulty
processors agree on the same value.
IC2: If the transmitter
is non-faulty, then all non-faulty processors use its value as the one
on which they agree.
We can add a third
property, namely:
IC3: All processors
that decide agree on the same value.
An agreement protocol
that satisfies this third property is said to be uniform.
-
A protocol that satisfies
the first two properties assuming a failstop failure model is called a
failstop
agreement protocol, and one that satisfies all three properties is
called a uniform failstop agreement protocol. Argue informally that
not all failstop agreement protocols are uniform failstop agreement protocols.
To do so, you will need to argue that a (failstop) faulty process can decide
on one value while a nonfaulty process can decide on another value. You
might consider a simple set of possible decision values, say either 0 or
1.
-
The following is written on page 174:
... If processors
experience only failstop failures, then an ensemble containing t +
1 replicas suffices, and the output of the ensemble can be the output produced
by any of its members.
Argue that for this
statement to be true, a uniform failstop agreement protocol is needed to
disseminate the commands to the state machine. If (nonuniform) failstop
agreement is used instead, what should the output of the ensemble be as
a function of the outputs of the members?