Concurrent Minimum Spanning Tree

System Architecture & Performance

Engineered a highly concurrent variation of Borůvka’s algorithm to process large-scale graph structures in parallel. The implementation focused on minimizing thread contention and optimizing memory access patterns.

• Parallel Processing: Designed the algorithm to distribute edge-weight evaluations across multiple worker threads, significantly reducing processing bottlenecks on dense clusters.
• Synchronization: Utilized atomic variables and thread-safe concurrent priority queues to manage state without introducing heavy locking mechanisms or deadlocks.
• Performance Metrics: Benchmarked against standard sequential implementations, achieving a 59.7% faster execution time when processing randomly generated sparse graphs (100,000+ nodes) on an 8-core machine.