Distributed mutual exclusion

This page is an example of a CSE 452-style design doc for a distributed protocol. The protocol ensures mutual exclusion—when a node acquires the global lock, it is guaranteed that nobody else holds the lock. (For example, this might be useful if the node needs to perform some actions with the guarantee that no other nodes are performing similar actions at the same time.)

Preface

• Goals:
  • Clients are assigned ownership of a global lock with the guarantee that no other client currently holds the lock. When they are done with the lock, they release it so that other clients may acquire it.
  • Clients that do not hold the lock are always requesting it.
  • Clients are not guaranteed to eventually acquire the lock if they ask for it - as we don't maintain a queue at the server. Instead, a single client can repeatedly re-acquire the lock even though others are also waiting.
• Desired fault model:
  • Asynchronous unreliable message delivery with message reordering. Assumes clients and the server obey the protocol, and that neither clients nor the server crash.
• Challenges:
  • An asynchronous, reordering, and duplicating network means that it can be difficult for nodes to tell whether a message is current, or a copy of an old already handled message.

Protocol

• Kinds of node:
  • One unique server node that manages the lock state.
  • Any number of client nodes trying to acquire the lock.
• State at each kind of node:
  • At the server:
    • current holder: client who currently holds the lock or None if nobody holds the lock
      • init: None
    • numGranted: The number of times the lock has been acquired
      • init: 0
  • At the client:
    • sequenceNum
      • sequenceNum: 0
      • 0 if the lock was never held by this client. If the lock is currently held by this client, the number of times the the lock has been granted to anyone. Otherwise the client's sequenceNum at the last point in time when the lock was held by this client.
    • mode: {None, Held, Releasing, Released}
      • init: None
      • None means this client does not hold the lock.
      • Held means that this client currently holds the lock.
      • Releasing means that this client had the lock and has released it, but the the server may or may not know.
      • Released means that this client no longer holds the sequenceNum version of the lock (and the server also knows); the server in the meantime might have re-granted the lock.
      • The client does not know whether other clients hold the lock or not, except in state Held - in that case, it knows it is the only node with the lock.

Messages:

A figure sketching the relationship of the messages to one another is at this link.

• Request
  • Source: Client
  • Destination: Server
  • Contents: client ID
  • Sent on startup and whenever the client takes a timeout and the lock is not held. In other words, the client always requests the lock.
  • What happens at the destination when it is received?
    • The server checks whether the lock is currently held by the requester.
    • If yes, it replies with the current numGranted.
    • If the lock is held by some other client, the server ignores the request. (The client will retry.)
    • If the lock is not held, it increments numGranted, sets the current holder to the sender of the request and sends a Grant message with the new value of numGranted back to the sender.
• Grant
  • Source: Server
  • Destination: Client that sent Request
  • Contents: current value of numGranted
  • Sent whenever a Request arrives and either the lock is not held or the the lock is currently held by the client making the request.
  • What happens at the destination when it is received?
    • The client compares the client sequenceNum against numGranted in the message. If numGranted is higher, the lock is acquired, the client goes into Held and updates the client sequenceNum. Note that the client cannot already be in Held in this case. Otherwise the message is ignored.
    • The client can now perform whatever critical section it needs to do. If there is no need for the lock, or when the client is done with its critical section, it sends Release and sets mode to Releasing.
• Release
  • Source: client
  • Destination: server
  • Contents: sequenceNum - set to the current sequenceNum at the client
  • When is it sent? When the critical section finishes, or when the client timer expires and the client mode is Releasing (the client doesn't know if the previous Release made it to the server).
  • What happens at the destination when it is received? The server checks the message sequenceNum against the current numGranted. If they match, this is a valid Release, and the holder is set to None. If the sequenceNum is smaller than numGranted, this is a duplicate. (The sequenceNum can never be larger than numGranted.) Either way, the server replies with a ReleaseAck to ensure that the client knows that the lock has been released (possibly some time ago).
• ReleaseAck
  • Source: server
  • Destination: client that sent Release
  • Contents: current value of numGranted
  • When is it sent? In reply to a Release message
  • What happens at the destination when it is received? If the current value of the sequenceNum at the client is larger than numGranted, this is a replay to an older Release and we can safely ignore it (we've moved on and re-acquired the lock). Otherwise, if the state is Releasing, changed to Released. (The state could already be Released if this is a duplicate Ack.) We do not update the sequenceNum until we re-acquire the lock, and we don't immediately issue another Request but instead wait for a timeout to do that.

Timers:

• ClientRetransmit: On expiration, if the client is in state None or Released, it issues a Request message. If the client is in state Releasing (the server may not have received the lock release), we send a Release message. If the client is in Held, do nothing.
• The server does not have a timer.

Correctness/Liveness

• A table sketching the error handling for each message type is at this link link.
• The table summarizes how message drops, duplicates, reorders, and delays are handled. Unless the lock is currently held by the client, the client will always retry, and so either the lock will be released (if the release was lost) or the lock will be acquired (if the lock is currently free).
• The system retries forever if delays are arbitrarily long.
• The system does not handle node failures. Server failures, or client failures while holding the lock will cause the system to deadlock.
• The system does not handle partitions. These can cause the system to deadlock.

Conclusion

• Goals achieved: Mutual exclusion. Only one client at a time will hold the lock, and it will never think it holds the lock when another client holds the lock.
• Limitations: Does not handle failures or partitions.
• What goals are only achieved sometimes? Clients waiting for a lock may only sometimes get the lock, if they are unlucky as to when their requests arrive at the server.