CPSC 668 Set 17: Fault-Tolerant Register Simulations 1
CPSC 668
Distributed Algorithms and
Systems
Spring 2008
Prof. Jennifer Welch
CPSC 668 Set 17: Fault-Tolerant Register Simulations 2
Fault-Tolerant Shared Memory
Simulations
•
Previous algorithms implemented shared
variable on top of message passing,
assuming no failures.
•
What if some processors might crash?
•
Can we still provide a shared read/write
variable on top of message passing?
•
Yes, even in an asynchronous system, if we
have enough nonfaulty processors.
•
First, we must specify a failure-prone shared
memory.
CPSC 668 Set 17: Fault-Tolerant Register Simulations 3
Specification of f-Resilient
Shared Memory
•
Inputs are invocations on the shared object.
•
Outputs are responses of the shared object.
•
A sequence of inputs and outputs is allowable iff:
–
there is a partitioning of proc. indices into "faulty" and
"nonfaulty"
–
Correct Interaction: each proc. alternates invocations
and matching responses
–
Nonfaulty Liveness: Every invocation by a nonfaulty
proc. has a matching response
–
Extended Linearizability: Linearizability holds for all
the completed operations and some subset of the
pending operations
CPSC 668 Set 17: Fault-Tolerant Register Simulations 4
Assumptions for Algorithm
•
Each read/write variable ("register") to be
simulated has
–
one reader and
–
one writer
–
(next topic will be to build more powerful variables
out of these)
•
There are n procs. which are cooperating to
simulate a collection of such variables
•
Underlying communication system is
asynchronous message passing
•
n > 2f (less than half the processors can crash)
CPSC 668 Set 17: Fault-Tolerant Register Simulations 5
Main Ideas of Algorithm
•
Each simulated register has a replica stored
at each of the n procs., not just at the
designated reader and writer of that register.
•
Use the redundant storage to provide fault-
tolerance.
•
Describe algorithm just for one simulated
register; use a separate copy of the same
algorithm in parallel for each simulated
register.
- 1
- 2
前往页