Operating SystemsDekker's Algorithm

Dekker's Algorithm

LevelIntermediate

Duration55 mins

TopicDekker's Algorithm

4 / 5

Comparison with Peterson

From Dekker to Peterson: The Evolution of Elegance

In 1981, sixteen years after Dekker's Algorithm was published, Gary L. Peterson introduced a simpler solution to the two-process mutual exclusion problem. Peterson's Algorithm achieves the same three guarantees—mutual exclusion, progress, and bounded waiting—with significantly less complexity.

This development raises important questions:

What makes Peterson's Algorithm simpler?
How do the two algorithms differ structurally?
Why did it take 16 years to find a simpler solution?
When might Dekker's approach still be preferred?

This page provides a comprehensive comparison of the two algorithms, examining their structures side-by-side, analyzing their differences, and understanding the trade-offs between them. By understanding both, you'll gain deeper insight into synchronization algorithm design.

What You Will Learn

By the end of this page, you will understand the structural differences between Dekker's and Peterson's algorithms, why Peterson's version is simpler without sacrificing correctness, the historical significance of the simplification, and the design principles that make simpler synchronization algorithms easier to verify.

Side-by-Side Algorithm Comparison

Let's examine both algorithms side-by-side to see their structural similarities and differences.

Dekker's Algorithm:

dekkers_algorithm.c
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
// DEKKER'S ALGORITHM (1965)
// First correct software solution for 2-process mutual exclusion
 
// Shared variables
boolean flag[2] = {FALSE, FALSE};  // Intent flags
int turn = 0;                       // Priority indicator
 
void dekker_process(int i) {
    int j = 1 - i;  // Other process
    
    while (TRUE) {
        // ===== ENTRY PROTOCOL =====
        
        flag[i] = TRUE;  // Express intent
        
        while (flag[j] == TRUE) {            // Contention check
            if (turn != i) {                  // Not my turn?
                flag[i] = FALSE;              // Back off
                while (turn != i) {           // Wait for turn
                    // Busy wait
                }
                flag[i] = TRUE;               // Re-assert intent
            }
            // Else: my turn, stay in loop waiting for flag[j] = FALSE
        }
        
        // ===== CRITICAL SECTION =====
        critical_section();
        
        // ===== EXIT PROTOCOL =====
        turn = j;         // Give turn to other
        flag[i] = FALSE;  // Clear intent
        
        // ===== REMAINDER SECTION =====
        remainder_section();
    }
}

Peterson's Algorithm:

petersons_algorithm.c
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
// PETERSON'S ALGORITHM (1981)
// Simplified solution for 2-process mutual exclusion
 
// Shared variables
boolean flag[2] = {FALSE, FALSE};  // Intent flags
int turn;                           // Priority indicator
 
void peterson_process(int i) {
    int j = 1 - i;  // Other process
    
    while (TRUE) {
        // ===== ENTRY PROTOCOL =====
        
        flag[i] = TRUE;  // Express intent
        turn = j;        // Give turn to other (be polite!)
        
        while (flag[j] == TRUE && turn == j) {
            // Busy wait
        }
        
        // ===== CRITICAL SECTION =====
        critical_section();
        
        // ===== EXIT PROTOCOL =====
        flag[i] = FALSE;  // Clear intent
        
        // ===== REMAINDER SECTION =====
        remainder_section();
    }
}

Immediate Observation

Peterson's entry protocol is 4 lines; Dekker's is 10+ lines. Peterson has no nested loops; Dekker has a loop inside a loop with conditionals. Peterson's exit protocol is 1 line; Dekker's is 2. This dramatic simplification is the core contribution of Peterson's work.

Structural Differences

The two algorithms share the same shared variables (two flags and a turn indicator) but use them quite differently:

Difference 1: Turn Assignment Timing

In Dekker's Algorithm:

Turn is assigned in the exit protocol after leaving the critical section
turn = j gives priority to the other process for the next contention

In Peterson's Algorithm:

Turn is assigned in the entry protocol before waiting
turn = j says "I'm willing to let you go first if we both want in"

This is the key innovation. Peterson moved the turn assignment to the entry section and inverted its meaning.

Turn Variable Usage Comparison
Aspect	Dekker's Algorithm	Peterson's Algorithm
When set	Exit protocol (after CS)	Entry protocol (before waiting)
Who sets to j	Process i after exiting	Process i upon entering protocol
Semantic meaning	"It's your turn next"	"After you, if we both want in"
Initial value	Matters (0 or 1)	Doesn't matter (gets set before use)
Used how	Determines who backs off	Part of compound wait condition

Difference 2: The Wait Condition

In Dekker's Algorithm:

while (flag[j] == TRUE) {
    // Complex inner logic with backoff
}

The wait condition only checks the flag. The turn logic is handled inside the loop.

In Peterson's Algorithm:

while (flag[j] == TRUE && turn == j) {
    // Simple busy wait
}

The wait condition checks both flag and turn. There's no inner logic—just spin.

This compound condition is Peterson's second key innovation. By checking both conditions together, there's no need for the complex back-off protocol.

wait_condition_analysis.c
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
// PETERSON'S WAIT CONDITION ANALYSIS
// while (flag[j] && turn == j)
 
// Exit condition: flag[j] == FALSE OR turn != j
 
// Case 1: flag[j] == FALSE
//   Meaning: Other process doesn't want critical section
//   Action: Enter immediately (no contention)
//   Same as Dekker
 
// Case 2: flag[j] == TRUE but turn != j (i.e., turn == i)
//   Meaning: Other wants CS, but WE have priority
//   Action: Enter immediately (we win contention)
//   Difference: In Dekker, we'd spin on flag[j] with priority
 
// Case 3: flag[j] == TRUE and turn == j
//   Meaning: Other wants CS and THEY have priority
//   Action: Wait (they should enter)
//   Difference: No backoff needed! Just keep checking.
 
// WHY NO BACKOFF NEEDED:
// - We set turn = j BEFORE waiting
// - If other also enters entry protocol, they set turn = i
// - The LAST write to turn wins
// - Exactly one of us has turn, the other enters
// - No possibility of both waiting forever!

The Last Writer Wins

Peterson's insight was that if both processes set turn before waiting, the last writer determines the value. One process will see turn = i, the other will see turn = j. They cannot both see turn values that keep them waiting. This eliminates the deadlock that forces Dekker's backoff protocol.

Why Peterson's Algorithm Is Simpler

Peterson's Algorithm is objectively simpler by several metrics:

1. Lines of Code

Component	Dekker	Peterson
Entry protocol	~12	4
Exit protocol	2	1
Nested loops	Yes	No
Conditionals in loop	2	0 (compound condition)

2. Cognitive Complexity

Dekker's Algorithm requires understanding:

The back-off behavior (why clear flag?)
The retry behavior (why re-set flag?)
The priority wait (why spin on turn?)
The turn transfer (why give turn after exit?)

Peterson's Algorithm requires understanding:

The compound wait condition (both parts must be true to wait)
The "polite" turn assignment (give priority to other)

3. Formal Verification Difficulty

Proving Dekker correct requires reasoning about:

Multiple interleaved states
The backoff/retry sequences
Turn transfer semantics

Proving Peterson correct is more direct:

Fewer states to consider
No backoff states
Simpler invariants

Peterson's Simplification Benefits

•Eliminates backoff — No need to clear and re-set flags during contention
•Eliminates nested loops — Single loop with compound condition
•Simplifies exit — No turn manipulation needed; just clear flag
•Easier to verify — Fewer states, cleaner invariants, shorter proofs
•Less error-prone — Fewer places to make implementation mistakes

The Elegance of Peterson's Insight:

By setting turn = j in the entry protocol, Peterson creates a situation where:

Each process politely offers priority to the other
The last offer "sticks" (last write wins)
Exactly one process is offered priority
That process can enter (even if both want in)
The other process waits briefly, then enters after the first exits

This is conceptually simpler: each process says "after you" and the last one to say it actually yields. In Dekker, the yielding is more complex: check priority, back off, wait for turn, retry.

Teaching Preference

Peterson's Algorithm is the standard choice for teaching mutual exclusion because students can understand it in 15 minutes. Dekker's typically requires an hour. For pedagogical purposes, Peterson achieves the same learning objectives (proving mutual exclusion, understanding atomic operations, etc.) with less confusion.

Correctness Comparison

Both algorithms satisfy the three requirements for mutual exclusion solutions. Let's compare how they achieve each:

Mutual Exclusion:

Dekker's Approach

•Both flags set → contention
•Check turn to determine priority
•Non-priority process backs off (clears flag)
•Priority process sees flag cleared, enters
•At most one flag set when entering CS

Peterson's Approach

•Both flags set → potentially wait
•But turn can only favor one
•Last to set turn = j waits
•Other sees turn != j, enters
•Turn variable breaks tie; no backoff needed

Progress:

progress_comparison.txt
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
PROGRESS PROPERTY
 
Goal: If no process is in CS and some want to enter, one will enter.
 
DEKKER:
  - If only one process wants in: flag[j] = FALSE, enter immediately
  - If both want in: turn determines priority
    - Priority process spins on flag[j]
    - Non-priority process backs off, clears flag[j]
    - Priority process sees flag[j] = FALSE, enters
  - Progress achieved via backoff creating asymmetry
 
PETERSON:
  - If only one process wants in: 
    - flag[j] = FALSE makes condition FALSE, enter immediately
  - If both want in:
    - Both set turn to each other
    - Last write wins (say turn = i survives)
    - Process i sees turn != j(= i), condition FALSE, enters
    - Process j sees turn == j AND flag[i] = TRUE, waits
  - Progress achieved via turn breaking tie
 
Key insight: Peterson's progress relies on last-write semantics
Dekker's progress relies on explicit backoff
 
Both work, but Peterson's is more direct.

Bounded Waiting:

bounded_waiting_comparison.txt
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
BOUNDED WAITING PROPERTY
 
Goal: After a process wants to enter, at most N-1 entries 
      by other processes before this process enters.
      (For 2 processes: at most 1 entry by the other)
 
DEKKER:
  - Process i wants to enter, backs off (turn = j)
  - Process j enters, exits, sets turn = i
  - Process i now has turn, will win next contention
  - Bound: 1 entry by other process
 
PETERSON:
  - Process i wants to enter, sets turn = j
  - If j in CS, i waits (turn = j, flag[j] = TRUE)
  - When j exits, j sets flag[j] = FALSE
  - i sees flag[j] = FALSE, enters
  - Even if j immediately reenters:
    - j sets flag[j] = TRUE, turn = i
    - i sees turn == i (not j), enters
  - Bound: 0 or 1 entry by other process
 
Key insight: Peterson achieves bounded waiting through
the turn assignment in entry protocol. The waiter is
always favored after the first exit.
 
Both algorithms provide the same bound (1),
achieved through different mechanisms.

Property Comparison Summary
Property	Dekker Mechanism	Peterson Mechanism	Same Guarantee?
Mutual Exclusion	Backoff + flag clear	Compound wait condition	Yes
Progress	Backoff creates asymmetry	Last-write turn semantics	Yes
Bounded Waiting	Turn transfer on exit	Turn assignment on entry	Yes (bound = 1)

Historical Perspective

A natural question arises: if Peterson's solution is simpler, why did it take 16 years to discover (1965 → 1981)?

The State of the Art in 1965:

When Dekker designed his algorithm:

No established theory: There was no framework for reasoning about concurrent programs. Dekker had to invent his reasoning approach alongside the algorithm.
First solution pressure: Dekker wasn't trying to find the simplest solution—he was trying to find any correct solution. Once a working algorithm exists, simplification is a different (often easier) problem.
Exit-focused thinking: Dekker's approach of transferring turn on exit is intuitive: "I'm done, you can go now." The entry-focused approach of Peterson is less intuitive: "I'll let you go first... and actually mean it only if you also want in."
No alternative examples: Without seeing multiple solutions, it's hard to identify unnecessary complexity. Only after Dekker's algorithm was studied for years did its complexity become apparent.

The Gap Wasn't Wasted

Between 1965 and 1981, the field wasn't idle. Dijkstra developed semaphores (1965), Hansen and Hoare developed monitors (1970s), Lamport developed the Bakery Algorithm (1974), and formal verification techniques matured. Peterson's simplification benefited from 16 years of accumulated understanding about what mattered in synchronization.

Why Peterson's Insight Was Non-Obvious:

Peterson's key insight—setting turn in the entry protocol to yield to the other—seems backwards at first:

"Wait, I want to enter, so why am I giving turn to the other process?"

The answer is subtle: by both processes offering priority to each other, the last offer stands. If I offer after you offer, you have priority. If you offer after I offer, I have priority. This converts a potential deadlock (both claiming priority) into orderly sequencing (exactly one has priority).

This is an example of a counterintuitive correct solution: doing the opposite of what seems right (yielding when you want to acquire) achieves the desired result (actually acquiring).

Peterson's Contribution:

Peterson's 1981 paper, "Myths About the Mutual Exclusion Problem," not only presented the simpler algorithm but also debunked common misconceptions:

Myth: Mutual exclusion requires complex back-off protocols
Reality: A simple compound wait condition suffices
Myth: Turn must be managed carefully to avoid starvation
Reality: Setting turn on entry (yielding) automatically provides fairness
Myth: Simpler algorithms sacrifice correctness properties
Reality: Peterson's algorithm achieves all three properties with less code

Lessons from the Dekker-Peterson Evolution

•First ≠ Best: The first correct solution is rarely the simplest
•Simplification takes time: Deep understanding precedes elegant simplification
•Invert assumptions: Sometimes the non-obvious approach (yield to acquire) works better
•Study success, then reduce: Analyze what makes a solution work, then remove what doesn't contribute
•Both have value: Dekker's for historical understanding, Peterson's for practical teaching

When Might Each Algorithm Be Preferred?

In practice, neither algorithm is used in production systems—hardware primitives (compare-and-swap, test-and-set) provide better performance. However, for academic and specific constrained contexts, different situations might favor one over the other:

Prefer Peterson When:

Teaching: Simpler to understand and verify
Formal verification exercises: Fewer states to analyze
Prototyping: Less code to write and debug
Minimal complexity required: Standard CS curriculum choice

Prefer Dekker When:

Historical study: Understanding the evolution of synchronization
Exam contexts: When asked specifically about Dekker's algorithm
Teaching backoff concepts: Dekker's explicit backoff illustrates the technique
Understanding complexity: Showing why simpler solutions are better

Practical Comparison
Consideration	Dekker	Peterson
Code complexity	Higher	Lower
Proof complexity	Higher	Lower
Teaching value	Historical context	Standard example
Memory operations	More (backoff writes)	Fewer
Scalability to n processes	Neither scales directly	Neither scales directly
Modern hardware	Neither is used	Neither is used

Both Are Obsolete in Practice

For actual systems programming, use hardware-supported primitives (mutexes, spinlocks with CAS, etc.). Both Dekker's and Peterson's algorithms require sequential consistency which modern processors don't guarantee without explicit memory barriers. They are teaching tools, not production solutions.

The Real Takeaway:

The comparison between Dekker and Peterson isn't about choosing one for implementation—it's about:

Understanding algorithm evolution: How correct solutions get simplified over time
Recognizing complexity sources: What parts of Dekker are necessary vs. artificial
Appreciation for elegance: Why Peterson's formulation is considered elegant
Design pattern recognition: The "yield to acquire" pattern in Peterson appears in other contexts
Verification skills: Proving either algorithm correct builds concurrent reasoning skills

Summary: Dekker vs. Peterson

We've comprehensively compared Dekker's and Peterson's algorithms. Let's consolidate the key insights:

Key Takeaways

•Same shared variables: Both use flag[2] and turn
•Different turn timing: Dekker sets turn on exit; Peterson sets turn on entry
•Different wait condition: Dekker checks only flag with inner turn logic; Peterson uses compound condition
•Peterson eliminates backoff: By setting turn in entry, no explicit backoff/retry needed
•Same correctness guarantees: Both achieve mutual exclusion, progress, and bounded waiting
•Peterson is simpler: Fewer lines, less cognitive load, easier to verify
•16-year gap: Simplification required accumulated understanding of synchronization
•Neither is practical: Modern systems use hardware primitives instead

What's Next:

Our final page examines the limitations of Dekker's Algorithm (which also apply to Peterson's). We'll explore why these algorithms fail on modern hardware without memory barriers, why they don't scale to more than two processes without modification, and how these limitations led to the development of hardware synchronization primitives.

Page Complete

You now understand the key differences between Dekker's and Peterson's algorithms, why Peterson's version is simpler without sacrificing correctness, and the historical context of this evolution. This comparison illuminates fundamental principles of synchronization algorithm design. Next, we'll explore the limitations that make these algorithms unsuitable for modern systems.

4 / 5

Loading learning content...

Operating SystemsDekker's Algorithm

Dekker's Algorithm

LevelIntermediate

Duration55 mins

TopicDekker's Algorithm

4 / 5

Comparison with Peterson

From Dekker to Peterson: The Evolution of Elegance

This development raises important questions:

What makes Peterson's Algorithm simpler?
How do the two algorithms differ structurally?
Why did it take 16 years to find a simpler solution?
When might Dekker's approach still be preferred?

What You Will Learn

Side-by-Side Algorithm Comparison

Let's examine both algorithms side-by-side to see their structural similarities and differences.

Dekker's Algorithm:

dekkers_algorithm.c
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
// DEKKER'S ALGORITHM (1965)
// First correct software solution for 2-process mutual exclusion
 
// Shared variables
boolean flag[2] = {FALSE, FALSE};  // Intent flags
int turn = 0;                       // Priority indicator
 
void dekker_process(int i) {
    int j = 1 - i;  // Other process
    
    while (TRUE) {
        // ===== ENTRY PROTOCOL =====
        
        flag[i] = TRUE;  // Express intent
        
        while (flag[j] == TRUE) {            // Contention check
            if (turn != i) {                  // Not my turn?
                flag[i] = FALSE;              // Back off
                while (turn != i) {           // Wait for turn
                    // Busy wait
                }
                flag[i] = TRUE;               // Re-assert intent
            }
            // Else: my turn, stay in loop waiting for flag[j] = FALSE
        }
        
        // ===== CRITICAL SECTION =====
        critical_section();
        
        // ===== EXIT PROTOCOL =====
        turn = j;         // Give turn to other
        flag[i] = FALSE;  // Clear intent
        
        // ===== REMAINDER SECTION =====
        remainder_section();
    }
}

Peterson's Algorithm:

petersons_algorithm.c
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
// PETERSON'S ALGORITHM (1981)
// Simplified solution for 2-process mutual exclusion
 
// Shared variables
boolean flag[2] = {FALSE, FALSE};  // Intent flags
int turn;                           // Priority indicator
 
void peterson_process(int i) {
    int j = 1 - i;  // Other process
    
    while (TRUE) {
        // ===== ENTRY PROTOCOL =====
        
        flag[i] = TRUE;  // Express intent
        turn = j;        // Give turn to other (be polite!)
        
        while (flag[j] == TRUE && turn == j) {
            // Busy wait
        }
        
        // ===== CRITICAL SECTION =====
        critical_section();
        
        // ===== EXIT PROTOCOL =====
        flag[i] = FALSE;  // Clear intent
        
        // ===== REMAINDER SECTION =====
        remainder_section();
    }
}

Immediate Observation

Structural Differences

The two algorithms share the same shared variables (two flags and a turn indicator) but use them quite differently:

Difference 1: Turn Assignment Timing

In Dekker's Algorithm:

Turn is assigned in the exit protocol after leaving the critical section
turn = j gives priority to the other process for the next contention

In Peterson's Algorithm:

Turn is assigned in the entry protocol before waiting
turn = j says "I'm willing to let you go first if we both want in"

This is the key innovation. Peterson moved the turn assignment to the entry section and inverted its meaning.

Turn Variable Usage Comparison
Aspect	Dekker's Algorithm	Peterson's Algorithm
When set	Exit protocol (after CS)	Entry protocol (before waiting)
Who sets to j	Process i after exiting	Process i upon entering protocol
Semantic meaning	"It's your turn next"	"After you, if we both want in"
Initial value	Matters (0 or 1)	Doesn't matter (gets set before use)
Used how	Determines who backs off	Part of compound wait condition

Difference 2: The Wait Condition

In Dekker's Algorithm:

while (flag[j] == TRUE) {
    // Complex inner logic with backoff
}

The wait condition only checks the flag. The turn logic is handled inside the loop.

In Peterson's Algorithm:

while (flag[j] == TRUE && turn == j) {
    // Simple busy wait
}

The wait condition checks both flag and turn. There's no inner logic—just spin.

This compound condition is Peterson's second key innovation. By checking both conditions together, there's no need for the complex back-off protocol.

wait_condition_analysis.c
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
// PETERSON'S WAIT CONDITION ANALYSIS
// while (flag[j] && turn == j)
 
// Exit condition: flag[j] == FALSE OR turn != j
 
// Case 1: flag[j] == FALSE
//   Meaning: Other process doesn't want critical section
//   Action: Enter immediately (no contention)
//   Same as Dekker
 
// Case 2: flag[j] == TRUE but turn != j (i.e., turn == i)
//   Meaning: Other wants CS, but WE have priority
//   Action: Enter immediately (we win contention)
//   Difference: In Dekker, we'd spin on flag[j] with priority
 
// Case 3: flag[j] == TRUE and turn == j
//   Meaning: Other wants CS and THEY have priority
//   Action: Wait (they should enter)
//   Difference: No backoff needed! Just keep checking.
 
// WHY NO BACKOFF NEEDED:
// - We set turn = j BEFORE waiting
// - If other also enters entry protocol, they set turn = i
// - The LAST write to turn wins
// - Exactly one of us has turn, the other enters
// - No possibility of both waiting forever!

The Last Writer Wins

Why Peterson's Algorithm Is Simpler

Peterson's Algorithm is objectively simpler by several metrics:

1. Lines of Code

Component	Dekker	Peterson
Entry protocol	~12	4
Exit protocol	2	1
Nested loops	Yes	No
Conditionals in loop	2	0 (compound condition)

2. Cognitive Complexity

Dekker's Algorithm requires understanding:

The back-off behavior (why clear flag?)
The retry behavior (why re-set flag?)
The priority wait (why spin on turn?)
The turn transfer (why give turn after exit?)

Peterson's Algorithm requires understanding:

The compound wait condition (both parts must be true to wait)
The "polite" turn assignment (give priority to other)

3. Formal Verification Difficulty

Proving Dekker correct requires reasoning about:

Multiple interleaved states
The backoff/retry sequences
Turn transfer semantics

Proving Peterson correct is more direct:

Fewer states to consider
No backoff states
Simpler invariants

Peterson's Simplification Benefits

•Eliminates backoff — No need to clear and re-set flags during contention
•Eliminates nested loops — Single loop with compound condition
•Simplifies exit — No turn manipulation needed; just clear flag
•Easier to verify — Fewer states, cleaner invariants, shorter proofs
•Less error-prone — Fewer places to make implementation mistakes

The Elegance of Peterson's Insight:

By setting turn = j in the entry protocol, Peterson creates a situation where:

Each process politely offers priority to the other
The last offer "sticks" (last write wins)
Exactly one process is offered priority
That process can enter (even if both want in)
The other process waits briefly, then enters after the first exits

This is conceptually simpler: each process says "after you" and the last one to say it actually yields. In Dekker, the yielding is more complex: check priority, back off, wait for turn, retry.

Teaching Preference

Correctness Comparison

Both algorithms satisfy the three requirements for mutual exclusion solutions. Let's compare how they achieve each:

Mutual Exclusion:

Dekker's Approach

•Both flags set → contention
•Check turn to determine priority
•Non-priority process backs off (clears flag)
•Priority process sees flag cleared, enters
•At most one flag set when entering CS

Peterson's Approach

•Both flags set → potentially wait
•But turn can only favor one
•Last to set turn = j waits
•Other sees turn != j, enters
•Turn variable breaks tie; no backoff needed

Progress:

progress_comparison.txt
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
PROGRESS PROPERTY
 
Goal: If no process is in CS and some want to enter, one will enter.
 
DEKKER:
  - If only one process wants in: flag[j] = FALSE, enter immediately
  - If both want in: turn determines priority
    - Priority process spins on flag[j]
    - Non-priority process backs off, clears flag[j]
    - Priority process sees flag[j] = FALSE, enters
  - Progress achieved via backoff creating asymmetry
 
PETERSON:
  - If only one process wants in: 
    - flag[j] = FALSE makes condition FALSE, enter immediately
  - If both want in:
    - Both set turn to each other
    - Last write wins (say turn = i survives)
    - Process i sees turn != j(= i), condition FALSE, enters
    - Process j sees turn == j AND flag[i] = TRUE, waits
  - Progress achieved via turn breaking tie
 
Key insight: Peterson's progress relies on last-write semantics
Dekker's progress relies on explicit backoff
 
Both work, but Peterson's is more direct.

Bounded Waiting:

bounded_waiting_comparison.txt
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
BOUNDED WAITING PROPERTY
 
Goal: After a process wants to enter, at most N-1 entries 
      by other processes before this process enters.
      (For 2 processes: at most 1 entry by the other)
 
DEKKER:
  - Process i wants to enter, backs off (turn = j)
  - Process j enters, exits, sets turn = i
  - Process i now has turn, will win next contention
  - Bound: 1 entry by other process
 
PETERSON:
  - Process i wants to enter, sets turn = j
  - If j in CS, i waits (turn = j, flag[j] = TRUE)
  - When j exits, j sets flag[j] = FALSE
  - i sees flag[j] = FALSE, enters
  - Even if j immediately reenters:
    - j sets flag[j] = TRUE, turn = i
    - i sees turn == i (not j), enters
  - Bound: 0 or 1 entry by other process
 
Key insight: Peterson achieves bounded waiting through
the turn assignment in entry protocol. The waiter is
always favored after the first exit.
 
Both algorithms provide the same bound (1),
achieved through different mechanisms.

Property Comparison Summary
Property	Dekker Mechanism	Peterson Mechanism	Same Guarantee?
Mutual Exclusion	Backoff + flag clear	Compound wait condition	Yes
Progress	Backoff creates asymmetry	Last-write turn semantics	Yes
Bounded Waiting	Turn transfer on exit	Turn assignment on entry	Yes (bound = 1)

Historical Perspective

A natural question arises: if Peterson's solution is simpler, why did it take 16 years to discover (1965 → 1981)?

The State of the Art in 1965:

When Dekker designed his algorithm:

No established theory: There was no framework for reasoning about concurrent programs. Dekker had to invent his reasoning approach alongside the algorithm.
First solution pressure: Dekker wasn't trying to find the simplest solution—he was trying to find any correct solution. Once a working algorithm exists, simplification is a different (often easier) problem.
Exit-focused thinking: Dekker's approach of transferring turn on exit is intuitive: "I'm done, you can go now." The entry-focused approach of Peterson is less intuitive: "I'll let you go first... and actually mean it only if you also want in."
No alternative examples: Without seeing multiple solutions, it's hard to identify unnecessary complexity. Only after Dekker's algorithm was studied for years did its complexity become apparent.

The Gap Wasn't Wasted

Why Peterson's Insight Was Non-Obvious:

Peterson's key insight—setting turn in the entry protocol to yield to the other—seems backwards at first:

"Wait, I want to enter, so why am I giving turn to the other process?"

This is an example of a counterintuitive correct solution: doing the opposite of what seems right (yielding when you want to acquire) achieves the desired result (actually acquiring).

Peterson's Contribution:

Peterson's 1981 paper, "Myths About the Mutual Exclusion Problem," not only presented the simpler algorithm but also debunked common misconceptions:

Myth: Mutual exclusion requires complex back-off protocols
Reality: A simple compound wait condition suffices
Myth: Turn must be managed carefully to avoid starvation
Reality: Setting turn on entry (yielding) automatically provides fairness
Myth: Simpler algorithms sacrifice correctness properties
Reality: Peterson's algorithm achieves all three properties with less code

Lessons from the Dekker-Peterson Evolution

•First ≠ Best: The first correct solution is rarely the simplest
•Simplification takes time: Deep understanding precedes elegant simplification
•Invert assumptions: Sometimes the non-obvious approach (yield to acquire) works better
•Study success, then reduce: Analyze what makes a solution work, then remove what doesn't contribute
•Both have value: Dekker's for historical understanding, Peterson's for practical teaching

When Might Each Algorithm Be Preferred?

Prefer Peterson When:

Teaching: Simpler to understand and verify
Formal verification exercises: Fewer states to analyze
Prototyping: Less code to write and debug
Minimal complexity required: Standard CS curriculum choice

Prefer Dekker When:

Historical study: Understanding the evolution of synchronization
Exam contexts: When asked specifically about Dekker's algorithm
Teaching backoff concepts: Dekker's explicit backoff illustrates the technique
Understanding complexity: Showing why simpler solutions are better

Practical Comparison
Consideration	Dekker	Peterson
Code complexity	Higher	Lower
Proof complexity	Higher	Lower
Teaching value	Historical context	Standard example
Memory operations	More (backoff writes)	Fewer
Scalability to n processes	Neither scales directly	Neither scales directly
Modern hardware	Neither is used	Neither is used

Both Are Obsolete in Practice

The Real Takeaway:

The comparison between Dekker and Peterson isn't about choosing one for implementation—it's about:

Understanding algorithm evolution: How correct solutions get simplified over time
Recognizing complexity sources: What parts of Dekker are necessary vs. artificial
Appreciation for elegance: Why Peterson's formulation is considered elegant
Design pattern recognition: The "yield to acquire" pattern in Peterson appears in other contexts
Verification skills: Proving either algorithm correct builds concurrent reasoning skills

Summary: Dekker vs. Peterson

We've comprehensively compared Dekker's and Peterson's algorithms. Let's consolidate the key insights:

Key Takeaways

•Same shared variables: Both use flag[2] and turn
•Different turn timing: Dekker sets turn on exit; Peterson sets turn on entry
•Different wait condition: Dekker checks only flag with inner turn logic; Peterson uses compound condition
•Peterson eliminates backoff: By setting turn in entry, no explicit backoff/retry needed
•Same correctness guarantees: Both achieve mutual exclusion, progress, and bounded waiting
•Peterson is simpler: Fewer lines, less cognitive load, easier to verify
•16-year gap: Simplification required accumulated understanding of synchronization
•Neither is practical: Modern systems use hardware primitives instead

What's Next:

Page Complete

4 / 5