Endoreversible thermodynamics

2013-02-18T13:28:21Z

18.111.105.211: more punctuation

{{Multiple issues|cleanup=May 2009|notability=May 2009|unreferenced =May 2009|
{{Expert-subject|Computer science|date=May 2009}}
}}

The '''Suzuki-Kasami algorithm'''<ref>Ichiro Suzuki, Tadao Kasami, ''A distributed mutual exclusion algorithm'', ACM Transactions on Computer Systems, Volume 3 Issue 4, Nov. 1985 (pages 344 - 349)</ref> is a [[access token|token]]-based [[algorithm]] for achieving mutual exclusion in [[distributed systems]]. The process holding the token is the only process able to enter its critical section.

If a process wants to enter its critical section and it does not have the token, it broadcasts a request message to all other processes in the system. The process that has the token, if it is not currently in a critical section, will then send the token to the requesting process. The algorithm makes use of increasing Request Numbers to allow messages to arrive out-of-order.

== Algorithm description ==

Let <math>n</math> be the number of processes. Each process is identified by an integer in <math>1, ..., n</math>.

=== Data structures ===

Each process <math>i</math> maintains one data structure:

* an array <math>RN_i[n]</math> (for Request Number), where <math>RN_i[j]</math> stores the last Request Number received from <math>j</math>

The token contains two data structures:

* an array <math>LN[n]</math> (for Last request Number), where <math>LN[j]</math> stores the most recent Request Number of process <math>j</math> for which the token was successfully granted
* a queue Q, storing the ID of processes waiting for the token

=== Algorithm ===

==== Requesting the critical section (CS) ====

When process <math>i</math> wants to enter the CS, if it does not have the token, it:

* increments its sequence number <math>RN_i[i]</math>
* sends a request message containing new sequence number to all processes in the system

==== Releasing the CS ====

When process <math>i</math> leaves the CS, it:

* sets <math>LN[i]</math> of the token equal to <math>RN_i[i]</math>. This indicates that its request <math>RN_i[i]</math> has been executed
* for every process <math>k</math> not in the token queue <math>Q</math>, it appends <math>k</math> to <math>Q</math> if <math>RN_i[k] = LN[k] + 1</math>. This indicates that process <math>k</math> has an outstanding request
* if the token queue <math>Q</math> is nonempty after this update, it pops a process ID <math>j</math> from <math>Q</math> and sends the token to <math>j</math>
* otherwise, it keeps the token

==== Receiving a request ====

When process <math>i</math> receives a request from <math>j</math> with sequence number <math>s</math>, it:

* sets <math>RN_i[j]</math> to <math>max(RN_i[j], s)</math> (if <math>s < RN_i[j]</math>, the message is outdated)
* if process <math>i</math> has the token and is not in CS, and if <math>RN_i[j] == LN[j] + 1</math> (indicating an outstanding request), it sends the token to process <math>j</math>

==== Executing the CS ====

A process enters the CS when it has acquired the token.

== Notes on the algorithm ==

* Only the site currently holding the token can access the CS
:* All processes involved in the assignment of the CS
* [[Hypertext Transfer Protocol|Request]] messages sent to all [[Node (networking)|nodes]]
:* Not based on [[Lamport timestamps|Lamport’s logical clock]]
:* The algorithm uses sequence numbers instead
* Used to keep track of outdated requests
* They advance independently on each site

The main design issues of the algorithm:
* Telling outdated requests from current ones
* Determining which site is going to get the token next

Data structures used to deal with these two aspects:
* Each site Si has an array RNi[1..N] to store the sequence
* Number of the latest requests received from other sites

The token contains two data structures:
* The token array LN[1..N] keeps track of the request executed most recently on each site
* The token queue Q is a queue of requesting sites

=== Requesting the CS ===
* If the site does not have the token, then it increases its sequence number RNi[i] and sends a request(i, sn) message to all other sites (sn= RNi[i])
* When a site Sj receives this message, it sets RNj[i] to max(RNj[i], sn). If Sj has the idle token, them it sends the token to Si if RNj[i] = LN[i]+1

=== Executing the CS ===
* Site Si executes the CS when it has received the token

=== Releasing the CS ===
* When done with the CS, site Si sets LN[i] = RNi[i]
* For every site Sj whose ID is not in the token queue, it appends its ID to the token queue if RNi[j] =LN[j]+1
* If the queue is not empty, it extracts the ID at the head of the queue and sends the token to that site

=== Performance ===
* either 0 or n messages for CS invocation (no messages if process holds the token; otherwise <math>N - 1</math> requests and <math>1</math> reply)
* Synchronization delay is 0 or N

==References==
{{Reflist}}

[[Category:Distributed algorithms]]

formulasearchengine - User contributions [en]

Endoreversible thermodynamics