# Leader Election Algorithms - ADR Implementations

This repository contains implementations of two distributed leader election algorithms for ring topologies:

## Algorithms

### 1. LCR (Le Lann, Chang, and Roberts) Algorithm
Located in `LCR Algorithm/` folder.

**Algorithm Overview:**
- Unidirectional ring topology
- Each node sends its ID clockwise
- Only forwards IDs larger than its own
- When a node sees its own ID return, it declares itself leader
- Leader broadcasts termination token (-1) to notify all nodes

**Key Components:**
- `Node.java`: Implements node behavior with ReentrantLock for message synchronization
- `Main.java`: Sets up 5 nodes in a unidirectional ring
- Uses `BlockingQueue<Message>` with Condition variables for reliable message delivery

**How to Run:**
```powershell
cd "LCR Algorithm"
javac Main.java
java Main
```

**Expected Output:**
- One "Node X becomes LEADER" message (where X is the highest ID)
- Final states showing all nodes with `termination=true` and `leader` set to highest ID

---

### 2. HS (Hirschberg-Sinclair) Algorithm
Located in `HS Algorithm/` folder.

**Algorithm Overview:**
- Bidirectional ring topology
- Nodes send messages in both directions with increasing range (2^phase)
- Messages travel outward up to their hop limit (alcance), then bounce back
- If a node's ID returns from both directions, it advances to the next phase
- First node whose message travels the entire ring becomes leader

**Key Components:**
- `Message.java`: Message object with:
  - `id`: The node ID being propagated
  - `alcance`: Hop count (decrements as message travels)
  - `isIn`: Boolean flag (false = outbound, true = inbound/reply)
  
- `Node.java`: Implements bidirectional node behavior
  - Uses `BlockingQueue<Message>` for inbox
  - Sends initial messages with alcance = 2^0 = 1
  - Processes incoming messages:
    - If `msg.id > my_id` and `alcance > 0`: forward with `alcance - 1`
    - If `alcance == 0`: send back as reply (`isIn = true`)
    - If `msg.id < my_id`: discard and reply with own ID
    - If `msg.id == my_id`: declare leadership!
    
- `Main.java`: Sets up 5 nodes in a bidirectional ring

**How to Run:**
```powershell
cd "HS Algorithm"
javac Message.java Node.java Main.java
java Main
```

**Expected Output:**
- "Node X becomes LEADER" (where X is the highest ID: 9 in the default setup)
- Final states showing `isLeader=true` for the leader node

---

## Implementation Details

### Message Synchronization (Both Algorithms)
- **LCR**: Uses `ReentrantLock` with `Condition` variables to ensure messages aren't overwritten
  - `await()` blocks until a new message arrives
  - `signal()` wakes the waiting thread
  
- **HS**: Uses `BlockingQueue<Message>` for reliable message delivery
  - `take()` blocks until a message is available
  - `offer()` enqueues messages safely

### Termination
Both algorithms use a termination token:
- **LCR**: Sends `-1` when leader is elected
- **HS**: Sends `Message(-1, 0, true)` when leader is elected
- All nodes forward the token and terminate upon receiving it

---

## Architecture Notes

### Why use locks/queues in a unidirectional ring?
Even with one sender per node, **timing issues** can cause problems:
1. Sender writes `next.in_message = value1`
2. Sender quickly writes `next.in_message = value2` (overwrites!)
3. Receiver only sees `value2` (message loss)

The lock/queue prevents overwrites and guarantees delivery order.

### HS Algorithm Phase Advancement
The current implementation is simplified and processes messages sequentially. A full implementation would:
- Track replies from both directions separately
- Advance to phase `k+1` only when replies from both directions confirm the node's ID is maximal within distance 2^k
- This ensures O(n log n) message complexity

---

## Testing

Default node configurations:
- **LCR**: Nodes with IDs 0, 1, 2, 3, 4 → Leader: 4
- **HS**: Nodes with IDs 5, 2, 7, 3, 9 → Leader: 9

To test with different IDs, modify the `Main.java` in each folder.

---

## Requirements

- Java Development Kit (JDK) 8 or higher
- PowerShell or Command Prompt (Windows)

## Author

Implementation of classic distributed algorithms for academic purposes.