1. A Centrifuge lease is a deterministic finite state machine (FSM).  It has a
finite set of possible states (e.g., held by node i, free).  State
changes are initiated by specific events: clock events and messages in
the protocol.  Draw the state machine.  Your states do not need to
track any intermediate states of operations in progress on the lease.

2. The Centrifuge lease FSM is replicated on the manager primary and on
the owner.  Either the manager or the owner may initiate a state
change (event or operation).  If either initiates a state change, it
sends a notification message to the other, which applies the event to
transition the state of its local replica. The lease is atomic: events
on a lease are applied in the same sequence at both replicas, and both
copies of the state machine transition through the same sequence of
states.  Each operation completes at both nodes before the next
operation can begin.  Briefly summarize the techniques used to achieve
this behavior.  Can they be implemented entirely at the network
protocol level?

3. What happens if both replicas (manager and owner) initiate
conflicting state transitions concurrently?  How are ordering and
atomicity enforced?

4. What happens if there is a network partition between the manager and
owner, e.g., the network delays message delivery for longer than the
lease time?  How are ordering and atomicity enforced?
 
5. The Centrifuge lease state machine is also replicated on the clients
(lookup nodes).  This replica uses an eventual consistency model: it
returns "hints" about the state of the lease, and these hints may be "stale".

(a) Does the client-side replica observe all events seen by the
primary and owner?  Is the order of events preserved?  Why are these
consistency properties useful or necessary?  Briefly summarize how
these properties are enforced.

(b) What happens if the state of a lease is stale on the lookup node?  How
does this affect the execution of a request that depends on that
state?  How does the service tolerate these stale "hints"?

(c) Why did the designers of Centrifuge decide to permit such stale hints?
How might Centrifuge implement strong consistency for the replicas on
the lookup nodes, to prevent stale hints?  What impact would this
choice have on the performance and scalability of the service?

6. A Centrifuge owner may hold tens of leases, e.g., at least one for
each virtual node that it hosts.  These leases may expire
independently.  For example, if the network is unreliable or the owner
is slow, it may lose some of its leases due to expiration, but not all
of them.  Similarly, if the owner fails, some of its leases may expire
quickly, while others may stall for the full term of the lease before
the master grants them to another owner.  Are these properties useful?
Why?

7. Like Chubby, the Centrifuge lock master is replicated using the
Paxos consensus algorithm so that the lock service "cannot fail".
What if it does fail?  How will a Centrifuge-based application service
behave?  

8. Ed the Engineer decides to attempt the west slope of the CAP triangle.
The task is to build a service with multiple servers that work
together to implement a single variable with read and write
operations.  A client may direct a read or write request to any
server.  Ed can assume that a network partition can never occur, but
the service should be consistent and available across failures of the
servers (assume a fail-stop model).  Consistency means that the
variable is atomic: it behaves as if it has only one copy.  More
precisely: reads and writes execute in some sequence (total order),
and a read always returns the result of the previous write.
Availability means that if any non-faulty server receives a request
from a client, then the request must execute and result in a response.
Outline a solution to meet these goals.

9. The summary questions for Centrifuge:

The paper says: "The design of Centrifuge is motivated by the needs of
in-memory server pools".  The "owners" in a Centrifuge cluster store
their data records in memory.  How should a Centrifuge-based system
recover lost data records if an owner fails?  What should the system
do if an owner's memory is not large enough to store all of the data
records that it owns?