🧠 File 07: Software-Only Algorithms — Peterson's, Bakery, Set-and-Test

When the interviewer says: "No mutex, no atomics, no __sync_*, no synchronized. You only have standard memory reads and writes."

📖 Why Do These Exist?

These algorithms were invented in the 1960s-1980s when CPUs didn't have atomic instructions like CMPXCHG or XCHG. They prove that mutual exclusion is possible using ONLY plain memory reads and writes — no special hardware support needed.

Interview context: Juspay interviewers ask this to test your depth of CS fundamentals. They want to see if you understand synchronization from first principles.

🔧 Algorithm 1: Peterson's Algorithm (For Exactly 2 Threads)

The Concept (Politeness Protocol):

Imagine two people approaching a narrow doorway:

Each person raises their hand: "I want to go through!" (flag[i] = true)
Each person says: "No, after you!" (turn = other)
If the other person also has their hand up AND it's the other person's turn → wait
Otherwise → go through!

Why It Works:

Both set flag = true (both want to enter)
Both set turn = other (both are polite)
But turn can only be ONE value (0 or 1)
The LAST thread to write turn gets stuck waiting
The FIRST thread to write turn proceeds (because turn was overwritten by the other)

Implementation:

class PetersonLock {
private:
    volatile bool flag[2];  // flag[i] = true means thread i wants to enter
    volatile int turn;      // whose "turn" to wait
    
public:
    PetersonLock() {
        flag[0] = false;
        flag[1] = false;
        turn = 0;
    }
    
    void lock(int threadId) {
        int other = 1 - threadId;
        
        flag[threadId] = true;  // Step 1: "I want to enter"
        turn = other;           // Step 2: "But you go first" (politeness)
        
        // Step 3: Wait ONLY IF:
        // - the other thread ALSO wants to enter, AND
        // - it's the other thread's turn
        while (flag[other] && turn == other) {
            // spin-wait
        }
        
        // We're in! The other thread either:
        // - doesn't want to enter (flag[other] = false), OR
        // - it IS our turn (turn == threadId, meaning other wrote turn last)
    }
    
    void unlock(int threadId) {
        flag[threadId] = false;  // "I'm done, not interested anymore"
    }
};

Proof of Correctness (The Three Properties):

1. Mutual Exclusion (only one in critical section):

For both to be in CS: both flag[0] and flag[1] are true
Both set turn = other
If Thread 0 set turn = 1 LAST: Thread 0 waits (turn == 1 and flag[1] == true)
If Thread 1 set turn = 0 LAST: Thread 1 waits
Only one can be "last" → only one waits → mutual exclusion ✅

2. Progress (someone always enters if anyone wants to):

If only Thread 0 wants to enter: flag[1] == false → while loop exits immediately ✅
If both want: the one who wrote turn first proceeds ✅

3. Bounded Waiting (no starvation):

A thread waits at most one "turn" — the other thread sets turn = me on its next entry ✅

Using Peterson's for Tree of Space:

// Each NODE in the tree gets a PetersonLock
// Supports up to 2 threads per node
vector<PetersonLock> nodePetersons;

bool lockWithPeterson(int node, int uid, int threadId) {
    // threadId is 0 or 1 (which of the two threads)
    
    vector<int> path;
    int cur = node;
    while (cur != -1) {
        path.push_back(cur);
        cur = parent[cur];
    }
    
    // Acquire Peterson locks from leaf to root
    for (int p : path) {
        nodePetersons[p].lock(threadId);
    }
    
    // Critical section (same checks as before)
    bool success = true;
    if (locked[node] != -1) success = false;
    if (success && descCount[node] > 0) success = false;
    if (success) {
        for (int i = 1; i < (int)path.size(); i++) {
            if (locked[path[i]] != -1) { success = false; break; }
        }
    }
    if (success) {
        locked[node] = uid;
        for (int i = 1; i < (int)path.size(); i++) {
            descCount[path[i]]++;
        }
    }
    
    // Release in reverse
    for (auto it = path.rbegin(); it != path.rend(); ++it) {
        nodePetersons[*it].unlock(threadId);
    }
    
    return success;
}

Limitations:

Only 2 threads! For N threads, use Bakery Algorithm.
On modern CPUs, requires memory barriers (CPUs reorder writes!)
volatile in C++ only prevents compiler optimization, NOT CPU reordering

🔧 Algorithm 2: Lamport's Bakery Algorithm (For N Threads)

The Concept:

Like a bakery where customers take numbered tickets:

When you arrive, look at everyone's ticket numbers
Take a number = max(all tickets) + 1
Wait until your number is the smallest
If two people have the same number, the one with the smaller thread ID goes first

Implementation:

class BakeryLock {
private:
    int N;                          // number of threads
    volatile bool choosing[];       // choosing[i] = true while thread i picks a number
    volatile int number[];          // number[i] = thread i's ticket number
    
public:
    BakeryLock(int numThreads) : N(numThreads) {
        choosing = new volatile bool[N];
        number = new volatile int[N];
        for (int i = 0; i < N; i++) {
            choosing[i] = false;
            number[i] = 0;
        }
    }
    
    void lock(int threadId) {
        // Step 1: Start choosing a number
        choosing[threadId] = true;
        
        // Step 2: Pick ticket = max of all tickets + 1
        int maxNum = 0;
        for (int i = 0; i < N; i++) {
            if (number[i] > maxNum) maxNum = number[i];
        }
        number[threadId] = maxNum + 1;
        
        choosing[threadId] = false;  // Done choosing
        
        // Step 3: Wait for our turn
        for (int j = 0; j < N; j++) {
            if (j == threadId) continue;
            
            // Wait while thread j is still choosing
            while (choosing[j]) { /* spin */ }
            
            // Wait while thread j has a smaller ticket
            // (or same ticket but smaller ID)
            while (number[j] != 0 && 
                   (number[j] < number[threadId] || 
                    (number[j] == number[threadId] && j < threadId))) {
                // spin
            }
        }
        // We're in!
    }
    
    void unlock(int threadId) {
        number[threadId] = 0;  // Drop our ticket
    }
};

Properties:

Works for any number of threads ✅
No hardware atomics needed ✅
Uses only reads and writes ✅
Ticket numbers can grow unboundedly (but in practice, wrap around is fine)

🔧 Algorithm 3: Set-and-Test (The Juspay Optimistic Pattern)

The Concept:

Instead of "check THEN set" (which has a TOCTOU gap), we "set THEN check" (claim first, verify after).

Traditional (Test-and-Set):              Optimistic (Set-and-Test):
1. Read: is it free?                     1. Write: claim it (increment counter)
   ⚡ context switch here ⚡              2. Read: did anyone else claim it too?
2. Write: mark as mine                      if count > 1 → collision → undo
→ TOCTOU bug!                            → collision detected after the fact

Implementation for Tree of Space:

vector<int> lockedCount(N, 0);    // 0 = free, >0 = claimed
vector<int> locked(N, -1);        // uid
// Note: lockedCount++ is STILL not atomic in C++!
// This pattern works ONLY if:
//   1. Single-word reads/writes are atomic (x86 guarantees this for aligned ints)
//   2. We accept that lost updates on lockedCount++ are DETECTED by the >1 check

bool lockSetAndTest(int node, int uid) {
    // EARLY BAIL-OUT (optional optimization)
    if (lockedCount[node] > 0 || descCount[node] > 0) return false;
    
    // ════════════════════════════════════
    // SET FIRST: Optimistically claim the node
    // ════════════════════════════════════
    lockedCount[node]++;
    
    // ════════════════════════════════════
    // TEST AFTER: Did another thread also claim it?
    // ════════════════════════════════════
    if (lockedCount[node] > 1) {
        // Collision! Another thread incremented too.
        lockedCount[node]--;
        return false;
    }
    
    // ════════════════════════════════════
    // ANCESTOR WALK (with bottom-up set-and-test)
    // ════════════════════════════════════
    int cur = parent[node];
    while (cur != -1) {
        // SET: insert into ancestor's tracking (inform them)
        lockedDescendants[cur].insert(node);
        
        // TEST: is ancestor locked? or does ancestor have conflicting lockedCount?
        if (locked[cur] != -1 || lockedCount[cur] > 0) {
            // Conflict! ROLLBACK everything we've done.
            lockedCount[node]--;
            int rollback = parent[node];
            while (rollback != cur) {
                lockedDescendants[rollback].erase(node);
                rollback = parent[rollback];
            }
            lockedDescendants[cur].erase(node);
            return false;
        }
        
        cur = parent[cur];
    }
    
    // All checks passed
    locked[node] = uid;
    return true;
}

⚠️ CRITICAL LIMITATIONS OF SET-AND-TEST:

Bug 1: Both Threads Rejected (Livelock)

Thread 1: lock(India, 5)
Thread 2: lock(India, 7)

Step 1: T1: lockedCount[India]++ → 1
Step 2: T2: lockedCount[India]++ → 2
Step 3: T1: lockedCount > 1? YES (2 > 1) → rollback, return false
Step 4: T2: lockedCount > 1? YES (still 2 or 1) → rollback, return false
Result: BOTH return false. Nobody locked India! BUG!

Bug 2: Ancestor-Descendant Both Succeed

Thread 1: lock(World)
Thread 2: lock(Asia)

If T1 hasn't incremented lockedCount[World] yet when T2 checks it → T2 proceeds
Then T1 also proceeds → BOTH succeed → invariant violated!

Why Set-and-Test Isn't Perfect:

"Set-and-test is an optimistic concurrency control pattern. It works well when collisions are rare, but when two threads compete directly, BOTH can fail (no progress). It's a stepping stone in the interview discussion — the interviewer expects you to identify these bugs and either accept them or layer additional coordination on top (like retry loops or software mutual exclusion)."

The Corrected Version (From Your Interview):

Based on your interview transcript, the interviewer guided you to this pattern:

bool lockCorrected(int node, int uid) {
    // SET FIRST (claim before checking)
    lockedCount[node]++;
    
    if (lockedCount[node] > 1 || descCount[node] > 0) {
        lockedCount[node]--;
        return false;
    }
    
    // Walk ancestors: set bottom FIRST, then test
    int cur = parent[node];
    while (cur != -1) {
        // SET: register with ancestor
        lockedDescendants[cur].insert(node);
        
        // TEST: is ancestor independently locked?
        if (locked[cur] != -1 || lockedCount[cur] > 0) {
            // ROLLBACK
            lockedCount[node]--;
            int par = parent[node];
            while (par != parent[cur]) {
                lockedDescendants[par].erase(node);
                par = parent[par];
            }
            return false;
        }
        
        cur = parent[cur];
    }
    
    locked[node] = uid;
    return true;
}

📝 What to Say to the Interviewer

"When hardware atomics are strictly banned, there are two proven software approaches:

Peterson's Algorithm (2 threads): Uses two shared variables — a flag array and a turn variable. Each thread announces intent and politely yields turn. The last thread to set turn waits. Guarantees mutual exclusion, progress, and bounded waiting using only memory reads and writes.

Lamport's Bakery Algorithm (N threads): Like a bakery ticket system. Each thread takes a number = max(all numbers) + 1. The smallest number goes first. Ties broken by thread ID.

Set-and-Test (Optimistic): Instead of check-then-set (which has TOCTOU), we set-then-check. Claim the resource by incrementing a counter, then verify no collision. The key insight from our discussion: in the ancestor walk, we INSERT into the ancestor's tracking BEFORE checking if the ancestor is locked. This way, even if another thread is concurrently locking the ancestor, our presence is already registered. However, this pattern has known bugs (both threads can reject each other) and requires careful handling."

07_software_algorithms.md

🧠 File 07: Software-Only Algorithms — Peterson's, Bakery, Set-and-Test

📖 Why Do These Exist?

🔧 Algorithm 1: Peterson's Algorithm (For Exactly 2 Threads)

The Concept (Politeness Protocol):

Why It Works:

Implementation:

Proof of Correctness (The Three Properties):

Using Peterson's for Tree of Space:

Limitations:

🔧 Algorithm 2: Lamport's Bakery Algorithm (For N Threads)

The Concept:

Implementation:

Properties:

🔧 Algorithm 3: Set-and-Test (The Juspay Optimistic Pattern)

The Concept:

Implementation for Tree of Space:

⚠️ CRITICAL LIMITATIONS OF SET-AND-TEST:

Why Set-and-Test Isn't Perfect:

The Corrected Version (From Your Interview):

📝 What to Say to the Interviewer