Book Errata - The Spin Model Checker::
69 bottom line: "exclusive read and exclusive write" -> "exclusive .. Algorithms for mutual exclusion. North Oxford Academic Publishers Ltd., 1986.
http://spinroot.com/spin/Doc/Book_extras/Errata.htmlHOME |
Example algorithms you can write on (or any others):
1) K Raymond. A tree-based algorithm for distributed mutual exclusion.
ACM Transactions on Computer Systems Volume 7 , Issue 1 (February
1989)
2) Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion
algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4,
p.344-349, Nov. 1985
3) S. Banerjee and P. K. Chrysanthis. A New Token Passing Distributed
Mutual Exclusion Algorithm (1996) In Proceedings of the Intl. Conf. on
Distributed Computing Systems. pp. 717--724
4) M. L. Neilsen and M. Mizuno. A DAG-based algorithm for distributed
mutual exclusion. In Proc. of the 11th Int. Conf. on Distributed
Computing Sys., pp. 354-360, 1991.
Convince the reader on your understanding of the following:
1) Underlying principles or the basis for the algorithm.
2) Functional details of the algorithm.
3) Instances where it does better/worse than the (or any) competition.
4) Include the reference section and a copy of the paper you are reporting on
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 Verifications with Proof Scores in CafeOBJ::
File Format: PDF/Adobe Acrobat - View as HTMLof distributed systems such as distributed mutual exclusion algorithms[12] and security. protocols[13]. We named this method the OTS/CafeOBJ method.
http://www.cs.ucsd.edu/~goguen/pps/kfwadt04.pdfHOME |
Algorithms for Scalable Synchronization on Shared-Memory ::
File Format: Adobe PostScript - View as HTMLThe information structure of distributed mutual exclusion algorithms. Algorithms for distributing hot-spot addressing. CSRD report
http://cs-www.cs.yale.edu/homes/arvind/cs424/readings/synch.psHOME |
[4] Neilsen, M. L. and Mizuno, M. A DAG-based algorithm for distributed
mutual exclusion. In Proc. of the 11th Int. Conf. on Distributed Computing
Sys., 1991, pp. 354-360.
http://plg.uwaterloo.ca/~mlaszlo/answers/neilsen_mizuno.dag-based_algorithm_for_distributed_mutual_exclusion.ps
I enjoyed working on this interesting question of yours. If you feel that
any part of my answer requires amplification or elaboration, please let
me know through a Clarification Request so that I have a chance to fully
meet your needs before you assign a rating.
Regards,
leapinglizard
I need the following clarification:
Is your algorithm closer to any of the following 3 algorithms? Which one?
1) Leslie Lamport: Times, clocks and ordering of events in a Distributed system
2) Ashok K Agarwal: An optimal Algorithm for Mutual Exclusion in Computer Network
3) Mamoru Maekawa: A N Algorithm for Mutual Exclusion in Decentralized systems
Would you please provide me with the following querry. I am in urgent need of it.
Your new request falls outside the scope of the original question.
I'll look into it when I have time, but not immediately.
leapinglizard
Hi,
ur previous work was very good. :-) Can u plz choose another
algorithm frm the list or any other distributed mutual exclusion and
do the same?
Please take a look at the following questions again ( also question
no:5//comparison of the algorithm)
I can offer u another $50 for this.
I also need this report within another 3-4days(similar as ur prev
work..with adding the comparison). Please let me know ur response
ASAP.
Example algorithms you can write on (or any others):
1) K Raymond. A tree-based algorithm for distributed mutual exclusion.
ACM Transactions on Computer Systems Volume 7 , Issue 1 (February
1989)
2) S. Banerjee and P. K. Chrysanthis. A New Token Passing Distributed
Mutual Exclusion Algorithm (1996) In Proceedings of the Intl. Conf. on
Distributed Computing Systems. pp. 717--724
3) M. L. Neilsen and M. Mizuno. A DAG-based algorithm for distributed
mutual exclusion. In Proc. of the 11th Int. Conf. on Distributed
Computing Sys., pp. 354-360, 1991.
Convince the reader on your understanding of the following:
1) Underlying principles or the basis for the algorithm.
2) Functional details of the algorithm.
3) Instances where it does better/worse than the (or any) competition.
4) Include the reference section and a copy of the paper you are reporting on
5) Is your algorithm closer to any of the following 3 algorithms? Which one?
a) Leslie Lamport: Times, clocks and ordering of events in a Distributed system
b) Ashok K Agarwal: An optimal Algorithm for Mutual Exclusion in Computer Network
c) Mamoru Maekawa: A N Algorithm for Mutual Exclusion in Decentralized systems Analysis of the Suzuki-Kasami Algorithm with the Maude Model Checker::
File Format: PDF/Adobe Acrobat - View as HTMLIn this paper, we report on the case study in which the. Maude model checker has been used Suzuki&Kasami distributed mutual exclusion algorithm. In
http://www.jaist.ac.jp/~ogata/mypapers/apsec05.pdfHOME |
As a courtesy, I shall address your additional question about the
Suzuki-Kasami algorithm later today. If you want to see an entirely
new answer, however, you should list a separate question with this
answering service. In general, a Researcher's answer is limited to the
scope of the original question.
I also wish to direct your attention to the house policy on homework assistance.
FAQ: homework questions
http://answers.google.com/answers/faq.html#homework
leapinglizard
Hi
I was wondering if you could provide me the solution of additional
question about the Suzuki-Kasami algorithm. I would be really greatful
if you could send me the solution by Tuesday... Computer and Information Sciences at IU South Bend::
Fundamental concepts of computer programming, algorithm development, . client -server models, distributed mutual exclusion and concurrency control,
http://www.cs.iusb.edu/CS_courses.htmlHOME |
Comprehensive Self-Stabilization Bibliography::
Self-stabilization of dynamic systems assuming only read/write atomicity. A quorum-based self-stabilizing distributed mutual exclusion algorithm.
http://www.cs.uiowa.edu/ftp/selfstab/bibliography/stabib.htmlHOME |
You're right, I did promise to do so much earlier, and I apologize for
the delay. I shall look into it soon. Thanks for your understanding
and patience.
leapinglizard
Is your algorithm close to any of the following 3 algorithms? Which one?
Lamport, Leslie: Time, clocks, and the ordering of events in a distributed
system
Ricart, G. and Agrawala, A. K: An optimal algorithm for mutual
exclusion in computer networks.
Maekawa, Mamoru: A sq(n) algorithm for mutual exclusion in decentralized
systems.
The Suzuki-Kasami algorithm does not resemble those described in the
three papers above. It is not compatible with the requirements of the
first and offers a significant conceptual improvement over the latter
two.
The Lamport algorithms [4] address the problem of synchronization,
which requires that requests be granted in the order they are issued.
In distributed mutual exclusion, there is no such assumption.
Suzuki-Kasami is designed precisely for an asynchronous environment in
which there are no clocks and no guarantee of message ordering.
Ricart and Agrawala [2] propose a linear-time algorithm in which a
node desiring a lock on a critical code segment must broadcast its
request to every other node and must then wait for responses from all
of them. Suzuki-Kasami is a linear-time algorithm with a smaller
constant factor that does away with the requirement to wait for a
response from every other node in the network. The solution is to
introduce the notion of a transferable execution privilege. This
feature sets Suzuki-Kasami apart from earlier distributed-mutex
algorithms and leads to the state-of-the-art algorithms of our day
which also transfer privilege from node to node.
Nor is Suzuki-Kasami comparable to the Maekawa algorithm [5], in which
nodes vote on whether a lock request should be granted. Although
Maekawa takes sublinear time, it still lacks the crucial feature of
requiring but a single response to transfer the execution privilege
from one node to another. It is this idea, and not that of voting,
which distinguishes Suzuki-Kasami and makes the later advances
possible.
If we must choose, we would say that Suzuki-Kasami most resembles the
Ricart-Agrawala algorithm, this latter being its immediate forebear
though not its progenitor. This is still rather a weak resemblance. It
is most useful to observe that Suzuki-Kasami is a revolutionary step
in the development of efficient distributed-mutex algorithms.
References:
[4] Lamport, Leslie. Time, clocks, and the ordering of events in a
distributed system. Communications of the ACM, Vol. 21, No. 7, Jul.
1978, pp. 558-565.
http://plg.uwaterloo.ca/~mlaszlo/answers/lamport.time_clocks_and_the_ordering_of_events_in_a_distributed_system.pdf
[5] Maekawa, Mamoru. A sq(n) algorithm for mutual exclusion in
decentralized systems. ACM Transactions on Computer Systems, Vol. 3,
No. 2, May 1985, pp. 145-159.
http://plg.uwaterloo.ca/~mlaszlo/answers/maekawa.a_sq(n)_algorithm_for_mutual_exclusion_in_decentralized_systems.pdf
leapinglizard
 Red Hat's Rough Recovery From CFO Exit
 Windows Live Finds a New, Pre-installed Home
|
Write a report on a distributed mutual exclusion algorithm