distributed-algorithms.md

class Node {
  constructor(id, nodes = []) {
    this.id = id;
    this.nodes = nodes;
    this.leaderId = null;
    this.isLeader = false;
    this.electionInProgress = false;
    this.timeout = null;
  }

  // Start an election
  startElection() {
    console.log(`Node ${this.id} starting election`);
    this.electionInProgress = true;

    // Get nodes with higher IDs
    const higherNodes = this.nodes.filter((node) => node.id > this.id);

    if (higherNodes.length === 0) {
      // No higher nodes, become leader
      this.becomeLeader();
    } else {
      // Send election messages to higher nodes
      higherNodes.forEach((node) => {
        this.sendElectionMessage(node);
      });

      // Set timeout for responses
      this.timeout = setTimeout(() => {
        if (this.electionInProgress) {
          this.becomeLeader();
        }
      }, 1000);
    }
  }

  // Send election message to another node
  sendElectionMessage(node) {
    console.log(`Node ${this.id} sending ELECTION to ${node.id}`);
    // In a real system, this would be a network call
    node.receiveElectionMessage(this);
  }

  // Receive election message from another node
  receiveElectionMessage(sender) {
    console.log(`Node ${this.id} received ELECTION from ${sender.id}`);

    // Send OK response
    this.sendOkMessage(sender);

    // Start own election if not already in progress
    if (!this.electionInProgress) {
      this.startElection();
    }
  }

  // Send OK message in response to election
  sendOkMessage(node) {
    console.log(`Node ${this.id} sending OK to ${node.id}`);
    // In a real system, this would be a network call
    node.receiveOkMessage(this);
  }

  // Receive OK message
  receiveOkMessage(sender) {
    console.log(`Node ${this.id} received OK from ${sender.id}`);
    // Cancel leadership claim
    if (this.timeout) {
      clearTimeout(this.timeout);
      this.timeout = null;
    }
    this.electionInProgress = false;
  }

  // Become the leader
  becomeLeader() {
    console.log(`Node ${this.id} becoming leader`);
    this.isLeader = true;
    this.leaderId = this.id;
    this.electionInProgress = false;

    // Announce leadership to all nodes
    this.nodes.forEach((node) => {
      if (node.id !== this.id) {
        this.sendLeaderMessage(node);
      }
    });
  }

  // Send leader announcement
  sendLeaderMessage(node) {
    console.log(`Node ${this.id} announcing leadership to ${node.id}`);
    // In a real system, this would be a network call
    node.receiveLeaderMessage(this);
  }

  // Receive leader announcement
  receiveLeaderMessage(leader) {
    console.log(`Node ${this.id} accepting ${leader.id} as leader`);
    this.isLeader = false;
    this.leaderId = leader.id;
    this.electionInProgress = false;
  }

  // Detect leader failure
  detectLeaderFailure() {
    console.log(`Node ${this.id} detected leader failure`);
    this.leaderId = null;
    this.startElection();
  }
}

Vector clocks are essential for tracking causality in distributed systems. This implementation demonstrates how to maintain and compare logical timestamps across distributed nodes:

class VectorClock {
  constructor(nodeId, totalNodes) {
    this.nodeId = nodeId;
    // Initialize vector with zeros for all nodes
    this.vector = new Array(totalNodes).fill(0);
  }

  // Increment local counter for an event
  increment() {
    this.vector[this.nodeId]++;
    return this.clone();
  }

  // Update vector when receiving a message
  update(otherClock) {
    // Take the maximum of each position
    for (let i = 0; i < this.vector.length; i++) {
      this.vector[i] = Math.max(this.vector[i], otherClock.vector[i]);
    }
    // Increment local counter
    this.vector[this.nodeId]++;
    return this.clone();
  }

  // Compare with another vector clock
  compare(otherClock) {
    let isGreater = false;
    let isLess = false;

    for (let i = 0; i < this.vector.length; i++) {
      if (this.vector[i] > otherClock.vector[i]) {
        isGreater = true;
      } else if (this.vector[i] < otherClock.vector[i]) {
        isLess = true;
      }
    }

    if (isGreater && !isLess) return 1;      // Happened after
    if (!isGreater && isLess) return -1;     // Happened before
    if (!isGreater && !isLess) return 0;     // Same time
    return null;                             // Concurrent events
  }

  // Create a copy of this clock
  clone() {
    const copy = new VectorClock(this.nodeId, this.vector.length);
    copy.vector = [...this.vector];
    return copy;
  }

  toString() {
    return `[${this.vector.join(', ')}]`;
  }
}

// Example usage
function demonstrateVectorClocks() {
  console.log("Vector Clock Demonstration");

  // Create three nodes with their vector clocks
  const clockA = new VectorClock(0, 3);
  const clockB = new VectorClock(1, 3);
  const clockC = new VectorClock(2, 3);

  console.log("Initial state:");
  console.log(`Node A: ${clockA}`);
  console.log(`Node B: ${clockB}`);
  console.log(`Node C: ${clockC}`);

  // Node A performs an event
  clockA.increment();
  console.log("\nNode A performs an event:");
  console.log(`Node A: ${clockA}`);

  // Node A sends a message to Node B
  const messageClockAB = clockA.clone();
  console.log("\nNode A sends a message to Node B");

  // Node B receives the message and updates its clock
  clockB.update(messageClockAB);
  console.log("Node B receives the message:");
  console.log(`Node A: ${clockA}`);
  console.log(`Node B: ${clockB}`);

  // Node B performs an event
  clockB.increment();
  console.log("\nNode B performs an event:");
  console.log(`Node B: ${clockB}`);

  // Node C performs two events
  clockC.increment();
  clockC.increment();
  console.log("\nNode C performs two events:");
  console.log(`Node C: ${clockC}`);

  // Node C sends a message to Node A
  const messageClockCA = clockC.clone();
  console.log("\nNode C sends a message to Node A");

  // Node A receives the message and updates its clock
  clockA.update(messageClockCA);
  console.log("Node A receives the message:");
  console.log(`Node A: ${clockA}`);
  console.log(`Node C: ${clockC}`);

  // Compare events
  console.log("\nCausality relationships:");
  const comparisonAB = clockA.compare(clockB);
  const comparisonAC = clockA.compare(clockC);
  const comparisonBC = clockB.compare(clockC);

  console.log(`A compared to B: ${interpretComparison(comparisonAB)}`);
  console.log(`A compared to C: ${interpretComparison(comparisonAC)}`);
  console.log(`B compared to C: ${interpretComparison(comparisonBC)}`);
}

function interpretComparison(result) {
  if (result === 1) return "happened after";
  if (result === -1) return "happened before";
  if (result === 0) return "same time";
  return "concurrent with";
}

demonstrateVectorClocks();

class ConsistentHashing {
  constructor(numberOfReplicas = 3) {
    this.numberOfReplicas = numberOfReplicas;
    this.ring = {};  // Hash ring
    this.sortedKeys = [];  // Sorted keys for binary search
    this.nodes = new Set();  // Track active nodes
  }

  // Add a node to the hash ring
  addNode(node) {
    if (this.nodes.has(node)) return;

    this.nodes.add(node);

    // Add virtual nodes (replicas) to the ring
    for (let i = 0; i < this.numberOfReplicas; i++) {
      const key = this.hash(`${node}:${i}`);
      this.ring[key] = node;
    }

    // Update sorted keys
    this.sortedKeys = Object.keys(this.ring).map(Number).sort((a, b) => a - b);

    console.log(`Added node ${node} with ${this.numberOfReplicas} replicas`);
  }

  // Remove a node from the hash ring
  removeNode(node) {
    if (!this.nodes.has(node)) return;

    this.nodes.delete(node);

    // Remove virtual nodes from the ring
    for (let i = 0; i < this.numberOfReplicas; i++) {
      const key = this.hash(`${node}:${i}`);
      delete this.ring[key];
    }

    // Update sorted keys
    this.sortedKeys = Object.keys(this.ring).map(Number).sort((a, b) => a - b);

    console.log(`Removed node ${node}`);
  }

  // Get the node responsible for a key
  getNode(key) {
    if (this.sortedKeys.length === 0) return null;

    const hash = this.hash(key);

    // Find the first point in the ring with a hash >= the key's hash
    let idx = this.findClosestNodeIdx(hash);

    // Return the node at that position
    return this.ring[this.sortedKeys[idx]];
  }

  // Find the index of the closest node in the ring
  findClosestNodeIdx(hash) {
    // Binary search to find the closest node
    let left = 0;
    let right = this.sortedKeys.length - 1;

    if (hash > this.sortedKeys[right]) {
      // Wrap around to the first node if hash is greater than all nodes
      return 0;
    }

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      if (this.sortedKeys[mid] === hash) {
        return mid;
      }

      if (this.sortedKeys[mid] > hash) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }

    // If we didn't find an exact match, left is the insertion point
    // which is the index of the first element greater than hash
    return left % this.sortedKeys.length;
  }

  // Simple hash function (for demonstration purposes)
  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash * 31 + key.charCodeAt(i)) % 1000;
    }
    return hash;
  }

  // Get distribution statistics
  getDistribution(keys) {
    const distribution = {};

    // Initialize counters for each node
    for (const node of this.nodes) {
      distribution[node] = 0;
    }

    // Count keys per node
    for (const key of keys) {
      const node = this.getNode(key);
      if (node) {
        distribution[node]++;
      }
    }

    return distribution;
  }
}

// Example usage
function demonstrateConsistentHashing() {
  console.log("Consistent Hashing Demonstration");

  const ch = new ConsistentHashing(3);

  // Add initial nodes
  ch.addNode("node1");
  ch.addNode("node2");
  ch.addNode("node3");

  // Generate some keys
  const keys = Array.from({ length: 100 }, (_, i) => `key${i}`);

  // Show initial distribution
  console.log("\nInitial distribution:");
  console.log(ch.getDistribution(keys));

  // Add a new node
  console.log("\nAdding node4:");
  ch.addNode("node4");

  // Show new distribution
  console.log("\nNew distribution:");
  console.log(ch.getDistribution(keys));

  // Remove a node
  console.log("\nRemoving node2:");
  ch.removeNode("node2");

  // Show final distribution
  console.log("\nFinal distribution:");
  console.log(ch.getDistribution(keys));

  // Show some key assignments
  console.log("\nSample key assignments:");
  for (let i = 0; i < 5; i++) {
    const key = `key${i}`;
    console.log(`${key} -> ${ch.getNode(key)}`);
  }
}

demonstrateConsistentHashing();

class Node {
  constructor(id, network) {
    this.id = id;
    this.network = network;
    this.data = new Map();  // Local key-value store
    this.version = new Map();  // Version numbers for each key
    this.gossipInterval = null;
  }

  // Start gossiping
  startGossiping(intervalMs = 1000) {
    this.gossipInterval = setInterval(() => this.gossip(), intervalMs);
    console.log(`Node ${this.id} started gossiping`);
  }

  // Stop gossiping
  stopGossiping() {
    if (this.gossipInterval) {
      clearInterval(this.gossipInterval);
      this.gossipInterval = null;
      console.log(`Node ${this.id} stopped gossiping`);
    }
  }

  // Perform a single round of gossip
  gossip() {
    // Select a random peer
    const peers = this.network.getNodes().filter(node => node.id !== this.id);
    if (peers.length === 0) return;

    const randomPeer = peers[Math.floor(Math.random() * peers.length)];

    // Send our data to the peer
    console.log(`Node ${this.id} gossiping with Node ${randomPeer.id}`);
    randomPeer.receiveGossip(this.getSummary());
  }

  // Get a summary of our data
  getSummary() {
    const summary = new Map();
    for (const [key, version] of this.version.entries()) {
      summary.set(key, {
        version,
        value: this.data.get(key)
      });
    }
    return summary;
  }

  // Receive gossip from another node
  receiveGossip(summary) {
    let updates = 0;

    // Process each key in the received summary
    for (const [key, { version, value }] of summary.entries()) {
      // If we don't have this key or our version is older
      if (!this.version.has(key) || this.version.get(key) < version) {
        this.data.set(key, value);
        this.version.set(key, version);
        updates++;
      }
    }

    if (updates > 0) {
      console.log(`Node ${this.id} updated ${updates} keys from gossip`);
    }
  }

  // Update a value locally
  setValue(key, value) {
    // Increment version or start at 1
    const newVersion = (this.version.get(key) || 0) + 1;

    this.data.set(key, value);
    this.version.set(key, newVersion);

    console.log(`Node ${this.id} set ${key}=${value} (version ${newVersion})`);
  }

  // Get a value
  getValue(key) {
    return this.data.get(key);
  }

  // Get all data
  getAllData() {
    const result = {};
    for (const [key, value] of this.data.entries()) {
      result[key] = {
        value,
        version: this.version.get(key)
      };
    }
    return result;
  }
}

class Network {
  constructor() {
    this.nodes = [];
  }

  // Add a node to the network
  addNode(nodeId) {
    const node = new Node(nodeId, this);
    this.nodes.push(node);
    return node;
  }

  // Get all nodes
  getNodes() {
    return this.nodes;
  }
}

// Example usage
function demonstrateGossipProtocol() {
  console.log("Gossip Protocol Demonstration");

  // Create a network with 5 nodes
  const network = new Network();
  const nodes = [];

  for (let i = 0; i < 5; i++) {
    nodes.push(network.addNode(i));
  }

  // Start gossiping on all nodes
  nodes.forEach(node => node.startGossiping(1000));

  // Set some initial values on different nodes
  nodes[0].setValue("color", "red");
  nodes[2].setValue("size", "large");
  nodes[4].setValue("shape", "circle");

  // After some time, check the propagation
  setTimeout(() => {
    console.log("\nData after 3 seconds of gossiping:");
    nodes.forEach(node => {
      console.log(`Node ${node.id} data:`, node.getAllData());
    });

    // Update a value
    console.log("\nUpdating a value on Node 1");
    nodes[1].setValue("color", "blue");

    // Check again after more gossiping
    setTimeout(() => {
      console.log("\nData after 3 more seconds of gossiping:");
      nodes.forEach(node => {
        console.log(`Node ${node.id} data:`, node.getAllData());
      });

      // Stop all nodes
      nodes.forEach(node => node.stopGossiping());
    }, 3000);
  }, 3000);
}

demonstrateGossipProtocol();

1. Review the following implementation of a distributed counter:

class DistributedCounter {
  constructor(nodeId) {
    this.nodeId = nodeId;
    this.localCount = 0;
    this.lastSeen = {}; // Track last seen count from each node
  }

  // Increment local counter
  increment() {
    this.localCount++;
    console.log(
      `Node ${this.nodeId}: Incremented counter to ${this.localCount}`
    );
    return this.localCount;
  }

  // Receive update from another node
  receiveUpdate(nodeId, count) {
    console.log(
      `Node ${this.nodeId}: Received count ${count} from Node ${nodeId}`
    );

    // Update last seen value for this node
    this.lastSeen[nodeId] = count;

    // Log current state
    console.log(`Node ${this.nodeId}: Current state:`, {
      localCount: this.localCount,
      lastSeen: this.lastSeen
    });
  }

  // Get the total count across all nodes we know about
  getTotalCount() {
    // Sum our count and all last seen counts
    const total =
      this.localCount +
      Object.values(this.lastSeen).reduce((sum, count) => sum + count, 0);

    console.log(`Node ${this.nodeId}: Total count is ${total}`);
    return total;
  }
}

// Example usage
function demonstrateDistributedCounter() {
  console.log('Distributed Counter Example');

  // Create three nodes
  const node1 = new DistributedCounter(1);
  const node2 = new DistributedCounter(2);
  const node3 = new DistributedCounter(3);

  // Each node increments its counter
  node1.increment();
  node2.increment();
  node2.increment();
  node3.increment();

  // Nodes share their counts (simulating network messages)
  node1.receiveUpdate(2, node2.localCount);
  node1.receiveUpdate(3, node3.localCount);

  node2.receiveUpdate(1, node1.localCount);
  node2.receiveUpdate(3, node3.localCount);

  node3.receiveUpdate(1, node1.localCount);
  node3.receiveUpdate(2, node2.localCount);

  // Get total counts from each node's perspective
  node1.getTotalCount();
  node2.getTotalCount();
  node3.getTotalCount();
}

demonstrateDistributedCounter();

1. Review the following implementation of a distributed key-value store:

class DistributedStore {
  constructor(nodeId) {
    this.nodeId = nodeId;
    this.data = {};
    this.peers = [];
  }

  // Add a peer node
  addPeer(node) {
    this.peers.push(node);
    console.log(`Node ${this.nodeId}: Added peer Node ${node.nodeId}`);
  }

  // Set a value and replicate to peers
  set(key, value) {
    console.log(`Node ${this.nodeId}: Setting ${key}=${value}`);

    // Update local data
    this.data[key] = value;

    // Replicate to peers
    this.peers.forEach((peer) => {
      console.log(
        `Node ${this.nodeId}: Replicating ${key}=${value} to Node ${peer.nodeId}`
      );
      peer.replicate(key, value, this.nodeId);
    });
  }

  // Receive replicated data from a peer
  replicate(key, value, fromNodeId) {
    console.log(
      `Node ${this.nodeId}: Received replication of ${key}=${value} from Node ${fromNodeId}`
    );
    this.data[key] = value;
  }

  // Get a value
  get(key) {
    const value = this.data[key];
    console.log(`Node ${this.nodeId}: Getting ${key}=${value}`);
    return value;
  }

  // Show all data
  showData() {
    console.log(`Node ${this.nodeId}: Current data:`, this.data);
  }
}

// Example usage
function demonstrateDistributedStore() {
  console.log('Distributed Key-Value Store Example');

  // Create three nodes
  const node1 = new DistributedStore(1);
  const node2 = new DistributedStore(2);
  const node3 = new DistributedStore(3);

  // Connect the nodes
  node1.addPeer(node2);
  node1.addPeer(node3);
  node2.addPeer(node1);
  node2.addPeer(node3);
  node3.addPeer(node1);
  node3.addPeer(node2);

  // Set some values on different nodes
  node1.set('color', 'red');
  node2.set('size', 'large');
  node3.set('shape', 'circle');

  // Check that values have replicated
  console.log('\nFinal state of all nodes:');
  node1.showData();
  node2.showData();
  node3.showData();

  // Demonstrate reading values
  console.log('\nReading values from Node 1:');
  node1.get('color');
  node1.get('size');
  node1.get('shape');
}

demonstrateDistributedStore();

1. Review the following implementation of a heartbeat failure detector:

class HeartbeatDetector {
  constructor(nodeId, timeoutMs = 3000) {
    this.nodeId = nodeId;
    this.timeoutMs = timeoutMs;
    this.lastHeartbeat = {};
    this.peers = [];
    this.alive = {};
    this.heartbeatInterval = null;
    this.checkInterval = null;
  }

  // Add a peer node
  addPeer(node) {
    this.peers.push(node);
    this.alive[node.nodeId] = true; // Assume alive initially
    console.log(`Node ${this.nodeId}: Added peer Node ${node.nodeId}`);
  }

  // Start sending heartbeats and checking for failures
  start() {
    // Send heartbeats every 1 second
    this.heartbeatInterval = setInterval(() => {
      this.sendHeartbeats();
    }, 1000);

    // Check for failures every 2 seconds
    this.checkInterval = setInterval(() => {
      this.checkFailures();
    }, 2000);

    console.log(`Node ${this.nodeId}: Started heartbeat detector`);
  }

  // Stop the detector
  stop() {
    clearInterval(this.heartbeatInterval);
    clearInterval(this.checkInterval);
    console.log(`Node ${this.nodeId}: Stopped heartbeat detector`);
  }

  // Send heartbeats to all peers
  sendHeartbeats() {
    console.log(`Node ${this.nodeId}: Sending heartbeats to peers`);
    this.peers.forEach((peer) => {
      peer.receiveHeartbeat(this.nodeId);
    });
  }

  // Receive a heartbeat from another node
  receiveHeartbeat(fromNodeId) {
    this.lastHeartbeat[fromNodeId] = Date.now();

    // If node was previously marked as failed, mark it as recovered
    if (!this.alive[fromNodeId]) {
      this.alive[fromNodeId] = true;
      console.log(`Node ${this.nodeId}: Node ${fromNodeId} has recovered`);
    }
  }

  // Check for failed nodes
  checkFailures() {
    const now = Date.now();

    Object.keys(this.lastHeartbeat).forEach((nodeId) => {
      const timeSinceLastHeartbeat = now - this.lastHeartbeat[nodeId];

      // If we haven't received a heartbeat within the timeout period
      if (timeSinceLastHeartbeat > this.timeoutMs) {
        if (this.alive[nodeId]) {
          this.alive[nodeId] = false;
          console.log(
            `Node ${this.nodeId}: Detected failure of Node ${nodeId}`
          );
        }
      }
    });

    console.log(`Node ${this.nodeId}: Current status:`, this.alive);
  }

  // Simulate this node failing (stops sending heartbeats)
  simulateFailure() {
    clearInterval(this.heartbeatInterval);
    console.log(
      `Node ${this.nodeId}: Simulating failure (stopped sending heartbeats)`
    );
  }

  // Simulate this node recovering
  simulateRecovery() {
    this.heartbeatInterval = setInterval(() => {
      this.sendHeartbeats();
    }, 1000);
    console.log(
      `Node ${this.nodeId}: Simulating recovery (resumed sending heartbeats)`
    );
  }
}

// Example usage
function demonstrateHeartbeatDetector() {
  console.log('Heartbeat Failure Detector Example');

  // Create three nodes
  const node1 = new HeartbeatDetector(1);
  const node2 = new HeartbeatDetector(2);
  const node3 = new HeartbeatDetector(3);

  // Connect the nodes
  node1.addPeer(node2);
  node1.addPeer(node3);
  node2.addPeer(node1);
  node2.addPeer(node3);
  node3.addPeer(node1);
  node3.addPeer(node2);

  // Start all detectors
  node1.start();
  node2.start();
  node3.start();

  // After 5 seconds, simulate node 2 failing
  setTimeout(() => {
    console.log('\nSimulating failure of Node 2');
    node2.simulateFailure();
  }, 5000);

  // After 10 seconds, simulate node 2 recovering
  setTimeout(() => {
    console.log('\nSimulating recovery of Node 2');
    node2.simulateRecovery();
  }, 10000);

  // After 15 seconds, stop all detectors
  setTimeout(() => {
    console.log('\nStopping all detectors');
    node1.stop();
    node2.stop();
    node3.stop();
  }, 15000);
}

demonstrateHeartbeatDetector();

1. Review the following implementation of the Bully Algorithm for leader election:

class Node {
  constructor(id) {
    this.id = id;
    this.leaderId = null;
    this.nodes = [];
  }

  // Add other nodes that this node can communicate with
  addNodes(nodes) {
    this.nodes = nodes.filter((node) => node.id !== this.id);
    console.log(`Node ${this.id}: Added ${this.nodes.length} peers`);
  }

  // Start an election
  startElection() {
    console.log(`Node ${this.id}: Starting election`);

    // Find nodes with higher IDs
    const higherNodes = this.nodes.filter((node) => node.id > this.id);

    if (higherNodes.length === 0) {
      // No higher nodes, become leader
      this.becomeLeader();
    } else {
      // Send election messages to higher nodes
      console.log(`Node ${this.id}: Sending election message to higher nodes`);
      let receivedResponse = false;

      higherNodes.forEach((node) => {
        // In a real system, this would be asynchronous
        const response = node.receiveElection(this.id);
        if (response) receivedResponse = true;
      });

      // If no response from higher nodes, become leader
      if (!receivedResponse) {
        this.becomeLeader();
      }
    }
  }

  // Receive election message from another node
  receiveElection(senderId) {
    console.log(
      `Node ${this.id}: Received election message from Node ${senderId}`
    );

    // Reply to sender
    console.log(`Node ${this.id}: Sending OK to Node ${senderId}`);

    // Start our own election
    setTimeout(() => this.startElection(), 100);

    return true; // Acknowledge receipt
  }

  // Become the leader
  becomeLeader() {
    console.log(`Node ${this.id}: Becoming leader`);
    this.leaderId = this.id;

    // Announce leadership to all nodes
    this.nodes.forEach((node) => {
      node.receiveLeaderAnnouncement(this.id);
    });
  }

  // Receive leader announcement
  receiveLeaderAnnouncement(leaderId) {
    console.log(
      `Node ${this.id}: Received announcement that Node ${leaderId} is the leader`
    );
    this.leaderId = leaderId;
  }
}

// Example usage
function demonstrateLeaderElection() {
  console.log('Leader Election Example');

  // Create nodes with IDs 1-5
  const nodes = [];
  for (let i = 1; i <= 5; i++) {
    nodes.push(new Node(i));
  }

  // Connect nodes to each other
  nodes.forEach((node) => {
    node.addNodes(nodes);
  });

  // Start an election from node 2
  console.log('\nStarting election from Node 2:');
  nodes[1].startElection();

  // After the election completes, check the results
  setTimeout(() => {
    console.log('\nElection results:');
    nodes.forEach((node) => {
      console.log(`Node ${node.id}: Leader is Node ${node.leaderId}`);
    });
  }, 1000);
}

demonstrateLeaderElection();

1. Review the following implementation that demonstrates CAP theorem trade-offs:

class CAPNode {
  constructor(id, preferConsistency = true) {
    this.id = id;
    this.preferConsistency = preferConsistency; // CP vs AP mode
    this.data = {};
    this.version = {};
    this.peers = [];
    this.partitioned = false; // Network partition simulation
  }

  // Add a peer node
  addPeer(node) {
    this.peers.push(node);
    console.log(`Node ${this.id}: Added peer Node ${node.id}`);
  }

  // Set a value locally and replicate to peers
  set(key, value) {
    console.log(`Node ${this.id}: Setting ${key}=${value}`);

    // Update local version
    this.version[key] = (this.version[key] || 0) + 1;

    // Update local data
    this.data[key] = value;

    // Try to replicate to peers
    let replicatedCount = 0;
    this.peers.forEach((peer) => {
      if (!this.partitioned && !peer.partitioned) {
        peer.replicate(key, value, this.version[key], this.id);
        replicatedCount++;
      }
    });

    // In CP mode, if we couldn't replicate to majority, revert
    if (this.preferConsistency && replicatedCount < this.peers.length / 2) {
      console.log(
        `Node ${this.id}: CONSISTENCY VIOLATION - couldn't replicate to majority, reverting`
      );
      delete this.data[key];
      return false;
    }

    return true;
  }

  // Receive replicated data from a peer
  replicate(key, value, version, fromNodeId) {
    // If we're partitioned, we can't receive replications
    if (this.partitioned) return false;

    console.log(
      `Node ${this.id}: Received replication of ${key}=${value} (v${version}) from Node ${fromNodeId}`
    );

    // Check if our version is older
    if (!this.version[key] || this.version[key] < version) {
      this.data[key] = value;
      this.version[key] = version;
      return true;
    } else {
      console.log(`Node ${this.id}: Ignoring replication, have newer version`);
      return false;
    }
  }

  // Get a value
  get(key) {
    // In CP mode, if partitioned, refuse reads for consistency
    if (this.preferConsistency && this.partitioned) {
      console.log(`Node ${this.id}: REFUSING READ in CP mode during partition`);
      return null;
    }

    const value = this.data[key];
    console.log(`Node ${this.id}: Getting ${key}=${value}`);
    return value;
  }

  // Simulate a network partition
  simulatePartition() {
    this.partitioned = true;
    console.log(
      `Node ${this.id}: NETWORK PARTITION - disconnected from cluster`
    );
  }

  // Heal a network partition
  healPartition() {
    this.partitioned = false;
    console.log(`Node ${this.id}: PARTITION HEALED - reconnected to cluster`);
  }

  // Show current state
  showState() {
    console.log(`Node ${this.id}: Current state:`, {
      mode: this.preferConsistency ? 'CP' : 'AP',
      partitioned: this.partitioned,
      data: this.data,
      versions: this.version
    });
  }
}

// Example usage
function demonstrateCAP() {
  console.log('CAP Theorem Demonstration');

  // Create CP and AP nodes
  const cpNode1 = new CAPNode(1, true); // Consistency preferred
  const cpNode2 = new CAPNode(2, true); // Consistency preferred
  const apNode3 = new CAPNode(3, false); // Availability preferred
  const apNode4 = new CAPNode(4, false); // Availability preferred

  // Connect the nodes
  const allNodes = [cpNode1, cpNode2, apNode3, apNode4];
  allNodes.forEach((node) => {
    allNodes
      .filter((n) => n !== node)
      .forEach((peer) => {
        node.addPeer(peer);
      });
  });

  // Initial writes
  console.log('\nInitial writes to all nodes:');
  cpNode1.set('color', 'red');

  // Check initial state
  console.log('\nInitial state:');
  allNodes.forEach((node) => node.showState());

  // Simulate network partition
  console.log('\nSimulating network partition for Node 1 and Node 3:');
  cpNode1.simulatePartition();
  apNode3.simulatePartition();

  // Try writes during partition
  console.log('\nAttempting writes during partition:');
  const cpWriteResult = cpNode1.set('size', 'large');
  const apWriteResult = apNode3.set('shape', 'circle');

  console.log(
    `CP node write during partition: ${cpWriteResult ? 'SUCCEEDED' : 'FAILED'}`
  );
  console.log(
    `AP node write during partition: ${apWriteResult ? 'SUCCEEDED' : 'FAILED'}`
  );

  // Try reads during partition
  console.log('\nAttempting reads during partition:');
  const cpReadResult = cpNode1.get('color');
  const apReadResult = apNode3.get('color');

  console.log(
    `CP node read during partition: ${
      cpReadResult !== null ? 'SUCCEEDED' : 'FAILED'
    }`
  );
  console.log(
    `AP node read during partition: ${
      apReadResult !== null ? 'SUCCEEDED' : 'FAILED'
    }`
  );

  // Heal the partition
  console.log('\nHealing the network partition:');
  cpNode1.healPartition();
  apNode3.healPartition();

  // Check final state
  console.log('\nFinal state after partition healed:');
  allNodes.forEach((node) => node.showState());
}

demonstrateCAP();