Lakhasly

Why is deadlock detection much more expensive in a distributed
environment than in a centralized environment?
18.2 Consider a hierarchical deadlock-detection algorithm in which the
global wait-for graph is distributed over a number of different controllers,
which are organized in a tree. Each non-leaf controller maintains
a wait-for graph that contains relevant information from the graphs of
the controllers in the subtree below it. In particular, let SA, Sp, and Sc
be controllers such that Sc is the lowest common ancestor of SA and
Sp (Sc must be unique, since we are dealing with a tree). Suppose that
node Ti appears in the local wait-for graph of controllers SA and Sp.
Then ~ must also appear in the local wait-for graph of
Controller Sc
Every controller in the path from Sc to SA
Every controller in the path from Sc to Sp
In addition, if ~ and Tj appear in the wait-for graph of controller So
and there exists a path from Ti to Ti in the wait-for graph of one of the
children of S0 , then an edge ~ -+ Tj must be in the wait-for graph
of So.
Show that, if a cycle exists in any of the wait-for graphs, then the
system is deadlocked.
754 Chapter 18
18.3 Your company is building a comp1.1ter network, and you are asked to
develop a scheme for dealing with the deadlock problem.
a. Would you use a deadlock-detection scheme or a deadlockprevention
scheme?
b. If you used a deadlock-prevention scheme, which one would you
use? Explain your choice.
c. If you used a deadlock-detection scheme, which one would you
use? Explain your choice.
18.4 Derive an election algorithm for bidirectional rings that is more efficient
than the one presented in this chapter. How many messages are needed
for n processes?
18.5 Your company is building a computer network, and you are asked to
write an algorithm for achieving distributed mutual exclusion. Which
scheme will you use? Explain your choice.
18.6 Consider the following failure model for faulty processors. Processors
follow the prescribed protocol but may fail at unexpected points in
time. When processors fail, they simply stop functioning and do not
continue to participate in the distributed system. Given such a failure
model, design an algorithm for reaching agreement among a set of
processors. Discuss the conditions under which agreement could be
reached.
18.7 Under what circumstances does the wait-die scheme perform better
than the wound-wait scheme for granting resources to concurrently
executing transactions?
18.8 Consider a failure that occurs during 2PC for a transaction. For each
possible failure, explain how 2PC ensures transaction atomicity despite
the failure.
18.9 The logical clock timestamp scheme presented in this chapter provides
the following guarantee: if event A happens before event B, then the
timestamp of A is smaller than the timestamp of B. Note, however, that
we cam1.0t order two events based only on their timestamps. The fact
that an event C has a timestamp that is smaller than the timestamp
of event D does not necessarily mean that event C happened before
event D; C and D could be concurrent events in the system. Discuss
ways in which the logical clock timestamp scheme could be extended
to distinguish concurrent events from events that can be ordered by the
happened-before relation.