Kessels Algorithm
Three-process mutual exclusion algorithm implementation in C++. Ensures that only one process can access a critical section at a time, preventing race conditions in concurrent systems. Uses shared variables and message passing to coordinate between three processes without deadlock or starvation.
Language
C++
Processes
3
Guarantees
Deadlock-free
Tech Stack
Technologies Used
C++
Linux
CMake
Git
GitHub
BashC++LinuxCMakeGitGitHubBashC++LinuxCMakeGitGitHubBashC++LinuxCMakeGitGitHubBashCore Implementation
Key Features
Mutual Exclusion
Only one layer winner proceeds to the second layer, ensuring exclusive critical section access at all times.
Deadlock Freedom
Timeouts and tie-breakers force progress - if both contend, one flips the tie bit ensuring forward movement.
Starvation Freedom
Each contender eventually becomes the winner due to alternating tie-breakers guaranteeing fair access.
Deep Dive
Project Case Study
Technical details and challenges
The Challenge
Distributed systems face the dining philosophers problem when multiple processes compete for shared resources. Traditional mutex implementations can lead to deadlock or starvation. The challenge was implementing Kessels' algorithm in Go, ensuring correctness, proving starvation freedom mathematically, and demonstrating practical performance under concurrent load.
The Solution
Implemented Kessels' efficient mutex algorithm using Go's concurrency primitives. The solution uses alternating tie-breakers and priority mechanisms to ensure fairness. Built comprehensive test suite to verify correctness under various scenarios. Provided formal proof of starvation freedom using mathematical induction. Created performance benchmarks comparing against standard mutex implementations.
Technical Deep Dive
Go's goroutines and channels provide lightweight concurrency for testing. Atomic operations ensure memory consistency across threads. The algorithm uses two-tier priority system with alternating tie-breakers. Each contender eventually becomes winner through fair rotation. Benchmarks measure throughput, latency, and fairness under high contention. Implementation demonstrates practical application of theoretical distributed systems concepts.
Results & Impact
Successfully implemented and formally proved correctness of Kessels' algorithm. The implementation passed all correctness tests including race conditions and edge cases. Performance benchmarks showed competitive throughput with standard mutexes while guaranteeing starvation freedom. The project received high marks for combining theoretical computer science with practical implementation in Go.