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

1. Chang-Roberts algorithm
2. Peterson (Dolev-Klawe-Rodeh A) algorithm
3. Improved Peterson algorithm
4. Dolev-Klawe-Rodeh algorithm B
5. Simplified Itai-Rodeh algorithm
6. Itai-Rodeh algorithm
7. Higham-Przytycka algorithm

Synchronized undirected ring

1. Franklin algorithm
2. Hirschberg-Sinclair algorithm
3. ProbAsFar (Korach-Rotem-Santoro) algorithm

Synchronized undirected mesh

1. Peterson algorithm

Synchronized oriented hypercube

1. Hyperelect algorithm

Synchronized oriented clique

1. Humblet algorithm

Synchronized undirected graph

1. Yo-Yo algorithm
2. Casteigts-Métivier-Robson-Zemmari algorithm

Asynchronous directed ring

1. Chang-Roberts algorithm
2. Peterson (Dolev-Klawe-Rodeh A) algorithm
3. Improved Peterson algorithm
4. Dolev-Klawe-Rodeh algorithm B
5. Itai-Rodeh algorithm
6. Higham-Przytycka algorithm

Asynchronous undirected ring

1. Franklin algorithm
2. Hirschberg-Sinclair algorithm
3. Stages with feedback (Korach-Rotem-Santoro) algorithm
4. Probabilistic Franklin algorithm
5. Itai-Rodeh algorithm

Asynchronous clique

1. Korach-Moran-Zaks algorithm

Asynchronous oriented clique

1. Loui-Matsushita-West algorithm

Graph orientation

Asynchronous ring

1. Syrotiuk-Pachl algorithm

Order estimation

Asynchronous undirected ring

1. Itai-Rodeh algorithm

Consensus

Synchronized network

1. Single Bit (Garay-Berman) algorithm
2. Phase King (Garay-Berman-Perry) algorithm
3. Ben-Or randomized algorithm

Graph algorithms

Synchronized minimum spanning tree

1. Gallager-Humblet-Spira algorithm

Synchronized maximal independent set

1. Luby algorithm

Synchronized dominating set

1. Local Randomized Greedy (Jia-Rajaraman-Suel) algorithm
2. Kuhn-Wattenhoffer algorithm

Running

Run example:

  go run src/example/synchronized.go 5