Dear rdvish,
I would choose to write a report on the Suzuki-Kasami approach to
distributed mutual exclusion. Bear in mind that you must use my work for
reference purposes only. You should not attempt to pass it off as your
own work. If you are to write such a report for a class, I urge you to
choose one of the other algorithms in the list, relying on my report
only as a model for your own. Since Banerjee and Chrysanthis' paper is
not readily available, I recommend the one by Neilsen and Mizuno. Note
that the references at the end of the report include a link to a local
copy of each paper.
On Suzuki and Kasami's O(N) algorithm for Distributed Mutual Exclusion
======================================================================
Underlying Principles
---------------------
Suzuki and Kasami's 1985 paper [1] is in large part a response to
Ricart and Agrawala's 1981 paper [2] in which the latter claimed to
have found an optimal algorithm for the so-called symmetrical approach
to distributed mutual exclusion. Although the later authors point out
that the earlier ones fail to define exactly what is meant by symmetry,
it is certainly the case that neither algorithm attempts to solve the
problem of distributed mutual exclusion by centralized control, where one
master node has greater privileges than the remaining nodes in a network.
There is indeed the notion of privilege in the Suzuki-Kasami algorithm,
but this is a transferable privilege that can be passed around the network
and used equally by every node. Associated with each critical section
of code is a privilege object that contains information common to all
nodes in the network. If a node wishes to enter a critical section and
it does not possess the privilege object, it broadcasts a request to
all other nodes in the network. Once all nodes with earlier priority
have finished using the privilege object, the last of these transfers
it to the requesting node, which in turn uses it, updates the common
information, and passes it on as necessary.
In the Ricart-Agrawala algorithm, it is also the case that a node wishing
to enter a critical section must broadcast a request to all other nodes
in the network, but it can only proceed once all other nodes have replied
in the affirmative. The advantage of Suzuki-Kasami lies in the fact that
a request is fulfilled by a single reply, as opposed to the N-1 replies
necessitated in a network of N nodes by Ricart-Agrawala.
Both algorithms resolve contention between simultaneous requests by means
of monotonically increasing sequence numbers. Whereas the Ricart-Agrawala
approach allows these numbers to fall in a range no greater than 2N, since
a node may not enter the critical section before all earlier requests by
other nodes have been fulfilled, the basic Suzuki-Kasami algorithm offers
no such guarantee. However, Suzuki and Kasami propose a modification
to their algorithm that does impose such a constraint, at the cost of
a small linear increase in the number of message exchanges per request.
Functional Details
------------------
The privilege object that gets passed around among nodes in the basic
Suzuki-Kasami algorithm is a pair (Q, LN) such that: Q is a queue of
identifiers for those nodes whose requests have gone unfulfilled thus far,
in order of their arrival in the queue; and LN is an array containing, for
each node, the sequence number of its most recently fulfilled request. To
make sense of this information, each node maintains an array RN that
contains, for every node in the network, the greatest sequence number
among the requests it has received so far from that node.
When a node wishes to enter a critical section, it makes a request
containing its own identifier as well as a sequence number n such that
n-1 is the previous sequence number it issued, or 1 if this is its first
request. The request is broadcast to all other nodes in the network,
while the node updates its own RN array to reflect the sequence number
it has just issued. Upon receiving a request, a node compares its RN
element for the requesting node to the sequence number issued by the
requesting node, and sets the RN element to the greater of the two. If
a node currently possesses the privilege object and is executing the
critical section, it must carry out all such RN updates after completing
execution and before looking at the privilege object.
The key moment in the algorithm is precisely when a node has left
the critical section and updated its RN array to reflect all requests
received since entering the critical section. The next task for this
node is to update its own element in the LN array to reflect the sequence
number of the request it has just fulfilled. Now it scans its RN array,
comparing each element to the corresponding one in the privilege object's
LN array. For each node whose RN element is one greater than its LN
element, meaning that the request bearing this sequence number should be
fulfilled next for the node in question, it appends the node identifier
to Q, the privilege object's task queue, unless Q already contains this
node identifier. Finally, if Q is not empty, the privileged node pops the
node identifier from the head of the queue and transfers the privilege
object to the corresponding node, which is then permitted to enter the
critical section.
In the modified version of Suzuki-Kasami, which imposes a finite range
on the monotonically increasing sequence numbers, each node contains
a supplementary array in which it records, for every other node in the
network, the number of requests it has received from it. Once a node i
sees that the number of requests from some other node j has reached a
constant L, it sends a reply to node j and resets the count. Conversely,
if a node i has already sent L requests, it may only send an L+1th request
once it has received a reply from every other node in the network. Once
it has done so, it resets its request count to 1 and proceeds to send
the request. This mechanism ensures that no more than L sequence numbers
from a given node are circulating in the network at any one time. Thus,
the range of sequence numbers, while monotonically and indefinitely
increasingly, may be restricted to the range [1, L] without affecting
the correct operation of mutual exclusion.
Advantages and Drawbacks
------------------------
The basic Suzuki-Kasami algorithm assures that the number of messages
exchanged per request is N for a network of N nodes. With sequence
numbers increasing without bound, however, there is no guarantee that
in a long-running distributed session, a sequence number won't overflow
the largest possible integer, causing either a crash or an erroneous
result in the algorithm. The modified Suzuki-Kasami algorithm, which
can restrict sequence numbers to the range [1, L] while guaranteeing
correct operation, requires N + (N-1)/L message exchanges per request,
or negligibly more than N for large L. This bound is an improvement over
the Ricart-Agrawala algorithm, which requires 2*(N-1) message exchanges
per node, or about twice as many.
However, the size of the messages exchanged is smaller in Ricart-Agrawala,
since the two kinds of message, request and reply, each contain nothing
more a node identifier and a sequence number. In Suzuki-Kasami, although
requests similarly comprise a node identifier and a sequence number,
the privilege object carries considerably more information. A privilege
object for a network of N nodes must store an array of N integers as
well as an integer queue with a maximum size of N, for a total of 2N
integer-sized records. It can be argued, on the other hand, that the cost
of transmitting a message of size 2N is in practice negligible compared
with the latency in a network of size N. A similar argument applies
in defense of the greater complexity of storing and maintaining the RN
arrays of Suzuki-Kasami. Since the bottleneck is in all probability in
the network latency, rather than in the processing at each node, the
Suzuki-Kasami algorithm is expected to be faster by a constant factor
than Ricart-Agrawala.
Although Suzuki-Kasami was a significant advance in its day, it has
since been rendered obsolete by algorithms that offer much better average
performance, especially under heavy network load. A prominent example is
Raymond's 1989 algorithm [3], which imposes a tree on the network by using
a minimum spanning tree of the network graph. Each node now communicates
only with its neighbors in the tree, which can dramatically cut down the
number of message exchanges and the length of the path traveled by each
message, depending on the topology of the tree. Processing costs at each
node are also reduced because each node only records information about
transactions with its immediate neighbors while remaining oblivious to
the remainder of the network. In the worst case, Raymond's algorithm
still takes O(N) message exchanges per request, but in the average
case, O(log N) messages are exchanged per request under light network
load. Under heavy network load, where each message does more work,
the average number of message exchanges per request is about four.
The Neilsen-Mizuno algorithm [4], which imposes a directed acyclic graph
(DAG) on the network graph, also takes O(N) messages exchanges per request
in the worst case, but only about three messages in the average case and
merely one under heavy network load. That is even better than the two
messages per request required by a centralized scheme for distributed
mutual exclusion. Nonetheless, the Suzuki-Kasami algorithm remains
historically important as a stepping stone from linear-expected-time to
logarithmic- and constant-expected-time approaches, since its authors
pioneered the crucial idea of transferable execution privilege.
References
----------
[1] Suzuki I. and Kasami, T. A distributed mutual exclusion algorithm,
ACM Transactions on Computer Systems (TOCS), Vol. 3, No.4, Nov. 1985,
pp.344-349.
http://plg.uwaterloo.ca/~mlaszlo/answers/suzuki_kasami.distributed_mutual_exclusion_algorithm.pdf
[2] Ricart, G. and Agrawala, A. K. An optimal algorithm for mutual
exclusion in computer networks. Communications of the ACM, Vol. 24,
No. 1, Jan. 1981, pp. 9-17.
http://plg.uwaterloo.ca/~mlaszlo/answers/ricart_agrawala.optimal_algorithm_for_mutual_exclusion_in_computer_networks.pdf
[3] Raymond, K. A tree-based algorithm for distributed mutual exclusion.
ACM Transactions on Computer Systems, Vol. 7, No. 1, Feb. 1989, pp. 61-77.
http://plg.uwaterloo.ca/~mlaszlo/answers/raymond.tree_based_algorithm_for_distributed_mutual_exclusion.pdf |
,
0 Comments
)