Specifying Token Ring for Mutual Exclusion

Mutual exclusion is a common term appearing frequently in computer sciences. In essence, it’s a mechanism of concurrency control allowing exclusive access to some resource (or “critical region”). Token passing is an algorithm for distributed mutual exclusion (DME) and will be our focus in this post.

DME specifications usually make the following assumptions:

• Network delivers message in order, e.g. TCP (sometimes)
• Every message is eventually delivered (usually)
• Messages are never duplicated. Duplication may result granting resources to multiple clients, which is not what mutual exclusion demands (usually)

Thing we might want to guarantee for DME specifications are:

• Mutual exclusion, at most one client is in a critical section (always)
• Non-starvation. A requesting client enters critical section eventually (usually)
• Non-overtaking. A client cannot enter critical section more than once while another client waits (usually)

In addition, we need to analyze DME algorithms’ performance metrics, which usually includes:

• Message complexity, e.g. number of messages sent between clients being served
• response time, or time between request and entering CS
• Throughput, or rate of processing CS requests

Let’s take a token ring as an example. In a token ring, a client holds a token and then sends it to the next one after exiting...