🇬🇷 Ελληνική έκδοση: README_GR.md

Distributed Systems – Algorithm Simulations (C)

This repository contains C implementations and simulations of distributed algorithms from the Distributed Systems CEID's course assignments.

The focus is on algorithmic correctness and distributed behavior rather than real network programming. All implementations simulate message passing, synchronous or asynchronous execution, and reliable FIFO channels, exactly as described in the problem statements.

---

Contents

Set 1

Exercise 1 – Synchronous Ring Algorithm

• Model: Synchronous distributed system
• Topology: Ring
• Channels: Reliable, FIFO
• Description:
  • Tick-based simulation of the given pseudocode
  • Each process communicates only with its neighbors
  • Demonstrates synchronous distributed computation on a ring

---

Exercise 2 – Counting the Number of Edges in a Graph

• Model: Distributed system
• Topology: Arbitrary connected graph
• Channels: Reliable, FIFO
• Approach:
  • Construction of a BFS tree rooted at a designated process u0
  • Convergecast of local node degrees from leaves to the root
  • The root computes the number of edges as:

    m = (sum of all degrees) / 2
    

• Implementation highlights:
  • Parent–child relationships
  • Subtree aggregation
  • Distributed-style message passing simulation

---

Set 2

Exercise 1 – Leader Election in a Complete Graph

• Model: Asynchronous distributed system

• Topology: Fully connected network

• Channels: Reliable and FIFO

• Assumptions:

  • Each process has a unique identifier (UID)
  • The number of processes n is known

• Algorithm: FloodSet Leader Election

  • Each process maintains a set S of known UIDs
  • Initially: S = { own UID }
  • Processes exchange sets with all others
  • Upon receiving a new set, they compute the union
  • If the set changes, it is flooded again
  • When |S| = n, the leader is selected as:

    leader = max(S)
    

• Simulation characteristics:

  • Event-driven asynchronous message passing
  • Random delivery delays
  • FIFO ordering enforced per communication channel
  • Guaranteed termination and agreement

---

Set 2 – Additional Exercises (Theory)

Exercises 2 and 3 of Set 2 are purely theoretical and focus on:

• Probabilistic analysis of a randomized consensus algorithm under message loss
• Reasoning about consistent cuts and global histories in distributed systems

As these exercises do not specify executable algorithms or pseudocode, they are intentionally not implemented in code.

---

Input Format

Input files are simple text files and vary per exercise. They may include:

• Number of processes
• Process UIDs
• Graph edges (for graph-based exercises)

---

Compilation & Execution

All programs are written in standard C and can be compiled using GCC or executed through IDEs such as Code::Blocks.

Example:

gcc main.c -o distributed
./distributed input.in

---

🔐 License

This repository contains personal academic laboratory work. It is shared for educational and reference purposes only.

Please do not submit this material as your own coursework.

All Rights Reserved.