distributed-framework
A collection of algorithms for Distributed Systems course (winter semesters 2020/21, 2021/22, 2022/23, 2023/24) at Jagiellonian University, Theoretical Computer Science Department.
Algorithms
Leader election
Synchronized directed ring
- Chang-Roberts algorithm
- Peterson (Dolev-Klawe-Rodeh A) algorithm
- Improved Peterson algorithm
- Dolev-Klawe-Rodeh algorithm B
- Simplified Itai-Rodeh algorithm
- Itai-Rodeh algorithm
- Higham-Przytycka algorithm
Synchronized undirected ring
- Franklin algorithm
- Hirschberg-Sinclair algorithm
- ProbAsFar (Korach-Rotem-Santoro) algorithm
- Higham-Przytycka algorithm
Synchronized undirected mesh
- Peterson algorithm
Synchronized oriented hypercube
- Hyperelect algorithm
Synchronized torus
- Mans orientation algorithm (prelude to Peterson leader election)
Synchronized oriented clique
- Humblet algorithm
Synchronized undirected graph
- Yo-Yo algorithm
- Casteigts-Métivier-Robson-Zemmari algorithm
Asynchronous directed ring
- Chang-Roberts algorithm
- Peterson (Dolev-Klawe-Rodeh A) algorithm
- Improved Peterson algorithm
- Dolev-Klawe-Rodeh algorithm B
- Itai-Rodeh algorithm
- Higham-Przytycka algorithm
Asynchronous undirected ring
- Franklin algorithm
- Hirschberg-Sinclair algorithm
- Stages with feedback (Korach-Rotem-Santoro) algorithm
- Probabilistic Franklin algorithm
- Itai-Rodeh algorithm
Asynchronous clique
- Korach-Moran-Zaks algorithm
- Afek-Gafni B algorithm
Asynchronous oriented clique
- Loui-Matsushita-West algorithm
Graph orientation
Asynchronous ring
- Syrotiuk-Pachl algorithm
Order estimation
Asynchronous undirected ring
- Itai-Rodeh algorithm
Consensus
Byzantine problem
Synchronized network
- Single Bit (Garay-Berman) algorithm
- Phase King (Garay-Berman-Perry) algorithm
- Ben-Or randomized algorithm
- Chor-Coan algorithm
Graph algorithms
Synchronized minimum spanning tree
- Gallager-Humblet-Spira algorithm
Synchronized maximal independent set
- Luby algorithm
- Métivier-Robson-Saheb-Djahromi-Zemmari algorithm (C)
Synchronized dominating set
- Local Randomized Greedy (Jia-Rajaraman-Suel) algorithm
- Kuhn-Wattenhoffer algorithm
Running
Run example:
go run src/example/synchronized.go 5