Lock Requirements: Mutual Exclusion, Deadlock Freedom, and Liveness

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Safety Property: Mutual Exclusion
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Let H(t) = {P₁, P₂, ..., Pₙ} be the set of processes holding the lock at time t
 
Invariant: ∀t: |H(t)| ≤ 1
 
In words: For all points in time t, the cardinality of the holder set is at most 1.
 
Violation: If at any time t, we have |H(t)| > 1, mutual exclusion is violated.
 
Example violation:
  t₁: H(t₁) = {A}      ✓ Valid - A holds lock
  t₂: H(t₂) = {}       ✓ Valid - No one holds lock
  t₃: H(t₃) = {A, B}   ✗ VIOLATION - Two holders

1
2
3
4
5
6
7
8
9
10
11
12
13

Scenario: Three lock servers (L1, L2, L3), process A and process B
 
Time    A's view           L1, L2 (majority)    L3 (partitioned)   B's view
----    --------           -----------------    ----------------   --------
t1      Request lock       Receive A's request  (partitioned)      (idle)
t2      (waiting)          Grant to A           (partitioned)      Request lock
t3      "I have lock"      A is holder          Receive B's req    (waiting)
t4      (in critical       A is holder          Grant to B         "I have lock"
        section)                                (thinks A dead)    
t5      BOTH IN CRITICAL SECTION — MUTUAL EXCLUSION VIOLATED
 
The partition between L3 and {L1, L2} caused L3 to believe A was dead,
leading to granting the lock to B while A still held it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Classic Deadlock (Multiple Locks):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
Process A                Process B
---------                ---------
Acquire(Lock1) ✓         Acquire(Lock2) ✓
Acquire(Lock2) ⏳         Acquire(Lock1) ⏳
  waiting for B            waiting for A
       ↓                        ↓
    DEADLOCK: Neither can proceed, neither will release
 
Single Lock Deadlock:
━━━━━━━━━━━━━━━━━━━━
 
Process A acquires lock
Process A crashes without releasing
No timeout configured
Lock is held forever
All other processes wait forever
       ↓
    DEADLOCK: System frozen
 
Livelock (Variant):
━━━━━━━━━━━━━━━━━━━
 
Process A tries to acquire, fails, retries immediately
Process B tries to acquire, fails, retries immediately
Both constantly retry at the exact same moment
Neither ever succeeds
       ↓
    LIVELOCK: Progress is attempted but never made

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

import asyncio
from typing import Optional
 
class DistributedLock:
    def __init__(self, lock_service, resource_id: str, ttl_seconds: int = 30):
        self.lock_service = lock_service
        self.resource_id = resource_id
        self.ttl = ttl_seconds
        self.renewal_interval = ttl_seconds // 3  # Renew at 1/3 of TTL
        self.lock_token: Optional[str] = None
        self.renewal_task: Optional[asyncio.Task] = None
    
    async def acquire(self, wait_timeout: float = 10.0) -> bool:
        """Attempt to acquire lock with timeout."""
        deadline = time.time() + wait_timeout
        
        while time.time() < deadline:
            result = await self.lock_service.try_lock(
                self.resource_id, 
                ttl=self.ttl
            )
            if result.acquired:
                self.lock_token = result.token
                self._start_renewal_loop()
                return True
            
            # Exponential backoff with jitter
            await asyncio.sleep(random.uniform(0.1, 0.5))
        
        return False  # Timeout without acquiring
    
    def _start_renewal_loop(self):
        """Background task to keep lock alive."""
        async def renew_loop():
            while True:
                await asyncio.sleep(self.renewal_interval)
                try:
                    renewed = await self.lock_service.renew(
                        self.resource_id, 
                        self.lock_token,
                        ttl=self.ttl
                    )
                    if not renewed:
                        # Lost the lock (token mismatch or expired)
                        raise LockLostException("Lock renewal failed")
                except Exception as e:
                    # Notify application that lock is no longer held
                    self._handle_lock_loss(e)
                    return
        
        self.renewal_task = asyncio.create_task(renew_loop())
    
    async def release(self):
        """Explicitly release the lock."""
        if self.renewal_task:
            self.renewal_task.cancel()
        if self.lock_token:
            await self.lock_service.unlock(self.resource_id, self.lock_token)
            self.lock_token = None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Deadlock Freedom (weaker):
━━━━━━━━━━━━━━━━━━━━━━━━━━
 
"If there are waiters, someone will get the lock."
 
Allows: A request that waits forever while others continuously 
       acquire and release the lock.
 
Example: Process A requests lock. Processes B, C, D also request.
         B gets lock, releases, C gets lock, releases, B gets lock again...
         A never gets the lock, but the system isn't deadlocked.
 
 
Starvation Freedom (stronger):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
"If you request the lock, you WILL get it eventually."
 
Forbids: Any scenario where a request waits forever.
 
Guarantee: There is a bounded number of times a request can be 
           "skipped" before it must be granted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Fair Lock with Queue:
━━━━━━━━━━━━━━━━━━━━━
 
Lock State:
  - holder: Current lock holder (or null)
  - queue: [P3, P5, P7, P2]  # Waiting processes in FIFO order
 
Operation: acquire(Pi)
  if holder is null:
    holder = Pi
    return SUCCESS
  else:
    queue.append(Pi)
    wait_until_notified(Pi)
    return SUCCESS
 
Operation: release(Pcurrent)
  assert holder == Pcurrent
  if queue is not empty:
    next = queue.pop(0)  # First in queue
    holder = next
    notify(next)
  else:
    holder = null
 
Guarantee: If P requests at time T, P will be granted the lock after
           at most |queue_at_T| other grants. No starvation possible.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Bounded Wait with B = 3:
━━━━━━━━━━━━━━━━━━━━━━━━
 
If process P requests at position 5 in queue:
  - Maximum others served first: 4 (positions 1-4)
  - P's position when it acquires: ≤ 5
  - Bound satisfied: 4 ≤ B would require B ≥ 4
 
For FIFO queue: B = N-1 where N is queue length when P joined
  This is optimal—P must wait for everyone ahead of it.
 
For priority queue: B depends on arrival rate of higher priorities
  In worst case (infinite high-priority arrivals): B = ∞ (no bound)
 
Example of bounded wait violation:
  P joins queue at position 3
  Before P reaches front, 100 new high-priority requests arrive
  100 more high-priority requests arrive
  ... P may never be served (B = ∞)
  
  Solution: Aging—requests increase priority over time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Scenario: Network partition separates lock service from some clients
 
Option A: Prioritize Safety
━━━━━━━━━━━━━━━━━━━━━━━━━━━
- Lock service refuses to grant new locks if it can't contact enough nodes
- Existing locks may be held indefinitely by unreachable holders
- Clients in minority partition cannot acquire locks
- Result: System stops making progress, but never violates mutual exclusion
 
Option B: Prioritize Liveness
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
- Lock service continues operating in each partition independently
- New locks granted on both sides of partition
- If same resource is locked on both sides: MUTUAL EXCLUSION VIOLATED
- Result: System continues operating, but safety may be compromised
 
No Third Option:
━━━━━━━━━━━━━━━━
Given: Lock holder in Partition A, new request in Partition B
We cannot determine if A has released without communicating with A
If we grant to B: Safety violation possible
If we wait for A: Liveness violation (may wait forever)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

SAFETY PROPERTIES (Bad things never happen):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
1. Mutual Exclusion
   ─────────────────
   Guarantee: At most one holder at any time
   Violation: Two processes in critical section simultaneously
   Severity: CRITICAL—data corruption possible
   Required for: ALL legitimate lock implementations
 
 
LIVENESS PROPERTIES (Good things eventually happen):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
 
2. Deadlock Freedom (weakest liveness)
   ────────────────────────────────────
   Guarantee: If waiters exist and holder releases, someone gets lock
   Violation: System frozen permanently with no holder and no progress
   Severity: HIGH—system completely unavailable
   Achieved by: Lock timeouts, crash detection
 
         ↓ (stronger)
 
3. Starvation Freedom (lockout freedom)
   ─────────────────────────────────────
   Guarantee: Every requester eventually gets the lock
   Violation: Some requests wait forever while others succeed
   Severity: MEDIUM—certain clients/requests starved
   Achieved by: Fair queuing (FIFO order)
 
         ↓ (strongest)
 
4. Bounded Wait (bounded bypass)
   ──────────────────────────────
   Guarantee: At most B others can "cut in line" before any request
   Violation: Unbounded number of others served before some request
   Severity: LOW—system works but wait times unpredictable
   Achieved by: Strict queue ordering, priority aging
 
 
RELATIONSHIP:
  Bounded Wait ⟹ Starvation Freedom ⟹ Deadlock Freedom
  (Each property implies the weaker ones above it)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

interface ProductionDistributedLock {
    // Core Operations
    acquire(timeout?: Duration): Promise<LockToken>;
    tryAcquire(): Promise<LockToken | null>;
    release(token: LockToken): Promise<void>;
    
    // Reentrancy Support
    acquireReentrant(timeout?: Duration): Promise<LockToken>;
    releaseReentrant(token: LockToken): Promise<boolean>; // true if fully released
    
    // Lock Extension
    extend(token: LockToken, duration: Duration): Promise<LockToken>;
    
    // Observability
    getHolder(): Promise<LockHolderInfo | null>;
    getQueueLength(): Promise<number>;
    getQueuePosition(requestId: string): Promise<number | null>;
    
    // Conditional Operations
    acquireIfVersion(expectedVersion: number, timeout?: Duration): Promise<LockToken>;
    
    // Events
    onLockLost(callback: (reason: LockLostReason) => void): void;
    onAcquired(callback: (token: LockToken) => void): void;
}
 
interface LockHolderInfo {
    holderId: string;
    acquiredAt: Date;
    expiresAt: Date;
    renewalCount: number;
    metadata: Record<string, string>;
}