NetGameSim to Akka Distributed Algorithms Simulator

This repository implements an end-to-end pipeline that converts randomly generated graphs into a running message-passing distributed system. Graph nodes become Akka actors, graph edges become communication channels, and distributed algorithms execute on top of this infrastructure.

Demo video

Project walkthrough and run demo: https://youtu.be/Lu_LjnTUHlU

Features

NetGameSim Integration: Uses NetGameSim for large-scale random graph generation (all topology types)
Graph Overlays: Tree (DFS spanning tree) and ring (BFS-order) overlays extracted from NetGameSim graphs
Edge Labels: Message type constraints per edge for traffic control
Node PDFs: Probability distributions for message generation (weighted, uniform, Zipf)
Timer & Input Nodes: Two initiation mechanisms for computations
Distributed Algorithms:
- Tree Leader Election (saturation algorithm, O(n) messages)
- Hirschberg-Sinclair (ring leader election, O(n log n) messages)
Built-in Metrics: MetricsActor collects message counts, timing, and milestones
Interactive Mode: Runtime message injection for testing

Prerequisites

Java 17+ (OpenJDK or Oracle JDK)
SBT 1.9.x (Scala Build Tool)
Scala 3.3.x (handled by SBT)
Git (for submodule management)

Getting Started

1. Clone the Repository

git clone <repository-url>
cd CS553_Project
git submodule update --init --recursive

2. Build the Project

sbt clean compile

3. Run Tests

sbt test

4. Run a Simulation

There are two ways to run experiments:

Option A — Interactive Experiment Runner (recommended)

run-experiment.ps1 is a PowerShell script that asks for a node count, automatically selects all NGSim parameters, runs both algorithms back-to-back, and prints a formatted comparison table.

powershell -ExecutionPolicy Bypass -File .\run-experiment.ps1

Or pass the node count directly:

powershell -ExecutionPolicy Bypass -File .\run-experiment.ps1 -NodeCount 500

The script will:

Ask for node count (or use -NodeCount)
Auto-select edgeProbability, reachability, connectedness based on size
Run Tree Leader Election → capture results
Run Hirschberg-Sinclair → capture results
Print a side-by-side comparison:

+--------------------------------+-----------------+---------------+
|  Metric                        |  Tree LE        |  H-S          |
+================================+=================+===============+
|  Leader Elected                |  Node 499       |  Node 499     |
+--------------------------------+-----------------+---------------+
|  Runtime                       |  845ms          |  1203ms       |
+--------------------------------+-----------------+---------------+
|  Messages Sent                 |  4,992          |  28,341       |
+--------------------------------+-----------------+---------------+
|  Algorithm Milestones          |  998            |  5,241        |
+--------------------------------+-----------------+---------------+
|  Unique Edges Used             |  998            |  1,000        |
+================================+=================+===============+

  Complexity note:
    Tree Leader Election : O(n)       messages  [saturation]
    Hirschberg-Sinclair  : O(n log n) messages  [phase-based ring]

Recommended node counts: 16 (quick demo), 500, 1500, 5000, 10000

Option B — Manual config edit + sbt command

Edit three lines in conf/sim-run.conf and run a single sbt command.

Step 1 — open conf/sim-run.conf and change these lines:

sim {
  graph {
    type      = "tree"                  # ← CHANGE: "tree" | "ring" | "random"
    nodeCount = 1500                    # ← CHANGE: any number of nodes you want
    seed      = 42
  }
  algorithm = "tree-leader-election"    # ← CHANGE: see table below
}

NGSimulator {
  NetModel {
    statesTotal = 1499   # ← CHANGE: always nodeCount - 1
    ...
  }
}

You want	Set `graph.type`	Set `algorithm`
Tree Leader Election	`tree`	`tree-leader-election`
Hirschberg-Sinclair Ring Election	`ring`	`hirschberg-sinclair`
Background traffic only	`random`	`noop`

Important: statesTotal must always equal nodeCount - 1. For example: 500 nodes → statesTotal = 499, 1500 nodes → statesTotal = 1499.

Also adjust edgeProbability in NGSimulator.NetModel based on node count:

nodeCount	edgeProbability	desiredReachabilityCoverage
≤ 100	0.15	0.90
101 – 1,000	0.05	0.80
1,001 – 5,000	0.03	0.70
5,001 – 20,000	0.001	0.60
> 20,000	0.0005	0.50

Step 2 — run it:

sbt -batch "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-run.conf --out outputs/my-run"

The simulator will:

Call NetGameSim to generate a random base graph of the requested size
Extract the requested topology overlay (DFS spanning tree or BFS ring)
Spawn one Akka actor per node and one channel per edge
Start the chosen algorithm and print results

Step 3 — reading the results

Results appear in three places simultaneously:

A) Console / sbt output — watch it live

The most important lines to look for while the run is happening:

# Algorithm result
[Node 708] I AM THE LEADER! Saturation complete across 87 neighbours   ← Tree election winner
[Node 499] I AM THE LEADER! My probe traversed the entire ring          ← HS ring election winner

# Metrics summary printed automatically when the simulation ends
============================================================
SIMULATION METRICS SUMMARY
============================================================
Total runtime:       433ms        ← how long the algorithm took
Total messages sent: 2999         ← total message count across all actors

Messages by type:
  Control             : 2,999     ← breakdown by message type

Unique edges used:    2998        ← how many channels carried traffic
Algorithm milestones: 4500        ← election_sent / forwarded / leader_elected events
============================================================

B) Log file — full history of every event

Every line printed to the console is also saved to:

sim-cli/logs/simulation.log

Useful commands to extract specific results after the run:

# Who became the leader?
Select-String -Path sim-cli\logs\simulation.log -Pattern "I AM THE LEADER"

# All algorithm milestones (phase starts, elections, forwarding)
Select-String -Path sim-cli\logs\simulation.log -Pattern "leader_elected|election_sent|election_forwarded|phase_started|phase_complete"

# The final metrics summary only
Select-String -Path sim-cli\logs\simulation.log -Pattern "SIMULATION METRICS|Total runtime|Total messages|Messages by type|Unique edges|Algorithm milestones"

C) Graph JSON file — saved topology for inspection or re-use

The enriched graph (nodes, edges, labels, PDFs) is saved to:

outputs/my-run/graph.json

You can reload this exact graph on a future run without regenerating it:

sbt "sim-cli/runMain edu.uic.cs553.cli.SimMain --graph outputs/my-run/graph.json --run 60s"

Quick-demo configs (fixed sizes, no editing needed)

If you just want to see it working immediately with pre-set parameters:

# Tree Leader Election on a 15-node tree
sbt "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-tree.conf --out outputs/tree-run"

# Hirschberg-Sinclair on a 16-node ring
sbt "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-ring.conf --out outputs/ring-run"

# Background traffic on a 50-node random graph (no algorithm)
sbt "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-random.conf --out outputs/random-run"

5. Interactive Mode

sbt "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-tree.conf --interactive"

Commands in interactive mode:

<nodeId> <msgType> <payload> — Inject a message to a node (e.g. 0 Work task1)
status — Show simulation status
quit — Exit interactive mode

Project Structure

CS553_Project/
├── build.sbt                    # Multi-module SBT build
├── run-experiment.ps1           # Interactive experiment runner (both algorithms)
├── project/
│   ├── build.properties         # SBT version
│   └── plugins.sbt              # sbt-assembly (Cinnamon commented out)
├── netgamesim/                  # NetGameSim source (git submodule)
├── sim-core/                    # Graph model, config, serialization
├── sim-runtime-akka/            # Akka actors, metrics, run loop
├── sim-algorithms/              # Distributed algorithm implementations
├── sim-cli/                     # Command line entry points
├── conf/                        # Configuration files
│   ├── sim-tree.conf            # Tree leader election (15 nodes, quick demo)
│   ├── sim-ring.conf            # Hirschberg-Sinclair (16 nodes, quick demo)
│   ├── sim-random.conf          # Random graph traffic (50 nodes, quick demo)
│   ├── sim-run.conf             # Primary editable config for any size run
│   └── inject-example.txt       # Example file-driven injection commands
├── docs/
│   └── report.md                # Design decisions and results
└── README.md

NetGameSim Integration

The simulator integrates with NetGameSim for scalable random graph generation. All three graph types (tree, ring, random) start by generating a random base graph via NetGameSim. The topology overlay is then applied:

random — uses the NetGameSim graph as-is
tree — extracts a DFS spanning tree from the NetGameSim graph
ring — builds a BFS-order bidirectional ring from the NetGameSim graph

This means NetGameSim configuration (under NGSimulator) controls the size and density of the base graph for all topology types.

NetGameSim Configuration

NGSimulator {
  NetModel {
    statesTotal = 14              # Approx. nodeCount - 1
    edgeProbability = 0.3         # Edge density of the base random graph
    desiredReachabilityCoverage = 0.95
    maxBranchingFactor = 4
  }
  Graph { directionality = "directed" }
}

The NetGameSimAdapter converts NetGameSim's NetGraph to our EnrichedGraph format, then GraphOverlay.spanningTree or GraphOverlay.ring reshapes it for the chosen algorithm.

Configuration

Simulations are controlled via HOCON configuration files. Key sections:

Graph Configuration

sim.graph {
  type = "tree"    # tree, ring, or random
  nodeCount = 15
  seed = 42
  edgeProbability = 0.3  # For random graphs only
}

Edge Labeling

sim.edgeLabeling {
  default = ["Control", "Ping"]  # Default allowed message types on every edge
  overrides = [
    { from = 0, to = 1, allow = ["Control", "Work", "Ack"] }
  ]
}

Node PDFs

sim.traffic {
  tickIntervalMs = 100
  pdfFamily = "weighted"   # weighted | uniform | zipf
  defaultPdf = [
    { msg = "Ping", p = 0.6 }
    { msg = "Work", p = 0.4 }
  ]
  perNodePdf = [
    { node = 5, pdf = [{ msg = "Gossip", p = 1.0 }] }
  ]
}

PDF families supported:

weighted — explicit probabilities (must sum to 1.0)
uniform — equal probability for every type listed
zipf — rank-based Zipf distribution; set zipfExponent to control skew

Initiators

sim.initiators {
  timers = [
    { node = 0, tickEveryMs = 100, mode = "pdf" }
    { node = 5, tickEveryMs = 200, mode = "fixed", fixedMsg = "Ping" }
  ]
  inputs = [
    { node = 1 }
    { node = 2 }
  ]
}

File Injection Format

When using --inject <file>, each line has the format:

<delayMs> node=<id> type=<MsgType> payload=<text>

Example (conf/inject-example.txt):

500  node=1  type=Ping    payload=hello-from-driver
1000 node=2  type=Work    payload=task-alpha
1500 node=0  type=Gossip  payload=rumour-1

Reproducible Experiments

Quickest way — experiment runner (runs both algorithms automatically)

# Small demo (fast, ~1-3 min total)
powershell -ExecutionPolicy Bypass -File .\run-experiment.ps1 -NodeCount 500

# Medium run (~5-10 min total)
powershell -ExecutionPolicy Bypass -File .\run-experiment.ps1 -NodeCount 1500

# Large run (~20-30 min total)
powershell -ExecutionPolicy Bypass -File .\run-experiment.ps1 -NodeCount 10000

Individual runs — reproduce specific results from `docs/report.md`

# 1. Tree Leader Election — 15-node spanning tree (quick demo)
sbt -batch "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-tree.conf --out outputs/tree-run"
# Expected: node 14 elected leader; O(n) Control messages

# 2. Hirschberg-Sinclair — 16-node ring (quick demo)
sbt -batch "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-ring.conf --out outputs/ring-run"
# Expected: node 15 elected leader (highest ID); O(n log n) Control messages

# 3. Random traffic with edge constraints — 50-node random graph
sbt -batch "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-random.conf --out outputs/random-run"
# Expected: PDF-driven traffic; Work messages only traverse edges where Work is in the label

# 4. Configurable large run — edit sim-run.conf to set nodeCount and algorithm
sbt -batch "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-run.conf --out outputs/my-run"

# 5. File-driven injection
sbt -batch "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-random.conf --inject conf/inject-example.txt"

# 6. Interactive injection
sbt -batch "sim-cli/runMain edu.uic.cs553.cli.SimMain --config conf/sim-random.conf --interactive"
# Type: 0 Work task1    (inject Work message to node 0)
# Type: status          (show running status)
# Type: quit            (exit)

Finding the leader after a run

# Who was elected leader?
Select-String -Path sim-cli\logs\simulation.log -Pattern "I AM THE LEADER" | Select-Object -Last 2

# Full metrics summary
Select-String -Path sim-cli\logs\simulation.log -Pattern "Total runtime|Total messages|Unique edges|Algorithm milestones" | Select-Object -Last 10

Algorithms

Tree Leader Election

Topology: Tree (DFS spanning tree extracted from NetGameSim graph)
Complexity: O(n) messages, O(diameter) time
Process: Leaves initiate by sending Election messages toward the center. An internal node waits until it has heard from all-but-one neighbor, then forwards the best candidate ID to the remaining neighbor. The node that receives from all neighbors becomes the leader and broadcasts LeaderAck back down the tree.
Two-center handling: When two adjacent nodes both saturate simultaneously, the higher-ID node wins.

Hirschberg-Sinclair

Topology: Bidirectional ring (BFS-order overlay from NetGameSim graph)
Complexity: O(n log n) messages, O(n) time
Process: Phase-based probing with exponentially increasing distances (2^k per phase). Active nodes send Probe messages in both directions; a probe survives only past nodes with smaller IDs. When a probe travels 2^k hops it becomes a Reply. A node advances to the next phase only after receiving both replies. The node whose probe circles the entire ring becomes the leader.

Testing

The project includes 5 ScalaTest specifications:

GraphModelSpec — Edge labels, PDFs (uniform/weighted/Zipf), graph generation
NodeActorSpec — Actor initialization, message routing, edge label enforcement, timer ticks
TreeLeaderElectionSpec — Algorithm correctness on trees, two-center tie-breaking, determinism
HirschbergSinclairSpec — Probe/reply handling, phase advancement, leader election on ring
SimulationIntegrationSpec — End-to-end simulation, SimulationManager, algorithm factory

Run all tests:

sbt test

Run specific test suites:

sbt "sim-core/testOnly *GraphModelSpec"
sbt "sim-runtime-akka/testOnly *NodeActorSpec"
sbt "sim-algorithms/testOnly *TreeLeaderElectionSpec"
sbt "sim-algorithms/testOnly *HirschbergSinclairSpec"
sbt "sim-algorithms/testOnly *SimulationIntegrationSpec"

Instrumentation

Built-in Metrics (MetricsActor)

The project includes a built-in MetricsActor that collects:

Message counts by type
Message counts by edge (from, to)
Algorithm milestones (phase start/complete, leader elected, etc.)
Timing information

Metrics are logged at simulation end via postStop.

Cinnamon (Optional — Requires Commercial License)

For advanced Akka actor instrumentation, the project supports Lightbend Cinnamon. Cinnamon requires a commercial license and access to the Lightbend repository.

To enable Cinnamon (if you have a license):

Set val useCinnamon = true in build.sbt
Uncomment the plugin line in project/plugins.sbt
Add Lightbend credentials and resolver (see comment block in build.sbt)
Uncomment the cinnamon { ... } block in sim-runtime-akka/src/main/resources/application.conf
For IDE runs, add -javaagent:/path/to/cinnamon-agent.jar to VM options

See the detailed comment block at the bottom of build.sbt for the exact wiring template.

Troubleshooting

Build Errors

If you see missing dependency errors:

sbt clean update compile

Submodule Issues

If NetGameSim is missing or empty:

git submodule update --init --recursive

NetGameSim Graph Generation Hangs

If the simulation hangs during graph generation, the edgeProbability is too high for the node count — the resulting graph has too many edges for NetGameSim's reachability walk to finish. Fix: lower edgeProbability and desiredReachabilityCoverage using the table in conf/sim-run.conf. The experiment runner (run-experiment.ps1) selects these values automatically.

Cinnamon Agent Not Loading

When running from IDE, add to VM options:

-javaagent:/path/to/cinnamon-agent.jar

License

This project is for educational purposes as part of CS553 coursework.

Name		Name	Last commit message	Last commit date
Latest commit History 5 Commits
conf		conf
docs		docs
netgamesim @ c56478c		netgamesim @ c56478c
project		project
sim-algorithms/src		sim-algorithms/src
sim-cli/src/main		sim-cli/src/main
sim-core/src		sim-core/src
sim-runtime-akka/src		sim-runtime-akka/src
.gitignore		.gitignore
.gitmodules		.gitmodules
README.md		README.md
build.sbt		build.sbt
run-experiment.ps1		run-experiment.ps1

Folders and files

Latest commit

History

Repository files navigation

NetGameSim to Akka Distributed Algorithms Simulator

Demo video

Features

Prerequisites

Getting Started

1. Clone the Repository

2. Build the Project

3. Run Tests

4. Run a Simulation

Option A — Interactive Experiment Runner (recommended)

Option B — Manual config edit + sbt command

Step 3 — reading the results

Quick-demo configs (fixed sizes, no editing needed)

5. Interactive Mode

Project Structure

NetGameSim Integration

NetGameSim Configuration

Configuration

Graph Configuration

Edge Labeling

Node PDFs

Initiators

File Injection Format

Reproducible Experiments

Quickest way — experiment runner (runs both algorithms automatically)

Individual runs — reproduce specific results from docs/report.md

Finding the leader after a run

Algorithms

Tree Leader Election

Hirschberg-Sinclair

Testing

Instrumentation

Built-in Metrics (MetricsActor)

Cinnamon (Optional — Requires Commercial License)

Troubleshooting

Build Errors

Submodule Issues

NetGameSim Graph Generation Hangs

Cinnamon Agent Not Loading

License

References

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Contributors

Uh oh!

Languages

Individual runs — reproduce specific results from `docs/report.md`

Packages