No single machine
knows everything.

// One node, two roles: a TCP listener (the "server")
// and a TCP dialer (the "client"). Every node in a real
// distributed system runs both at once.
use std::io::{Read, Write};
use std::net::{TcpListener, TcpStream};

fn run_server(addr: &str) -> std::io::Result<()> {
    let listener = TcpListener::bind(addr)?;
    for incoming in listener.incoming() {
        let mut sock = incoming?;
        let mut buf = [0u8; 1024];
        let n = sock.read(&mut buf)?;
        // Echo back; in a real node we'd parse a protocol message
        // (ping, gossip-tx, request-block, etc.) and dispatch.
        sock.write_all(&buf[..n])?;
    }
    Ok(())
}

fn dial(peer: &str, payload: &[u8]) -> std::io::Result<Vec<u8>> {
    let mut sock = TcpStream::connect(peer)?;
    sock.write_all(payload)?;
    let mut reply = Vec::new();
    sock.read_to_end(&mut reply)?;
    Ok(reply)
}

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

// Listening side of a node.
int run_server(uint16_t port) {
    int s = socket(AF_INET, SOCK_STREAM, 0);
    struct sockaddr_in addr = { 0 };
    addr.sin_family = AF_INET;
    addr.sin_port = htons(port);
    addr.sin_addr.s_addr = INADDR_ANY;
    bind(s, (struct sockaddr*)&addr, sizeof addr);
    listen(s, 32);

    for (;;) {
        int c = accept(s, NULL, NULL);
        char buf[1024];
        ssize_t n = recv(c, buf, sizeof buf, 0);
        send(c, buf, n, 0);             // echo for the demo
        close(c);
    }
}

// Dialing side. Open a connection to a peer, send bytes, read a reply.
int dial(const char *ip, uint16_t port, const char *payload) {
    int s = socket(AF_INET, SOCK_STREAM, 0);
    struct sockaddr_in addr = { 0 };
    addr.sin_family = AF_INET;
    addr.sin_port = htons(port);
    inet_pton(AF_INET, ip, &addr.sin_addr);
    connect(s, (struct sockaddr*)&addr, sizeof addr);

    send(s, payload, strlen(payload), 0);
    char buf[1024];
    ssize_t n = recv(s, buf, sizeof buf, 0);
    close(s);
    return (int)n;
}

// Consistent hashing: a fixed ring of slots from 0 to 2^32 - 1.
// Each node is placed at hash(node_id) on the ring; each key is placed
// at hash(key); a key belongs to the first node clockwise from its
// position. Adding or removing a node only relocates 1/N of keys.
use sha2::{Sha256, Digest};

fn hash_to_u32(s: &str) -> u32 {
    let mut h = Sha256::new();
    h.update(s.as_bytes());
    let digest = h.finalize();
    u32::from_be_bytes([digest[0], digest[1], digest[2], digest[3]])
}

struct HashRing {
    nodes: Vec<(u32, String)>,   // (position_on_ring, node_id)
}

impl HashRing {
    fn add(&mut self, node: &str) {
        self.nodes.push((hash_to_u32(node), node.to_string()));
        self.nodes.sort_by_key(|&(pos, _)| pos);
    }

    fn owner(&self, key: &str) -> &str {
        let kpos = hash_to_u32(key);
        // First node whose position >= key position; wrap to first if none.
        self.nodes
            .iter()
            .find(|&&(pos, _)| pos >= kpos)
            .map(|(_, id)| id.as_str())
            .unwrap_or(&self.nodes[0].1)
    }
}

// In Cassandra, DynamoDB, memcached clusters: this is how you find the
// node that owns a given key. Add a node and only ~1/N of keys move.

// Consistent hashing: a fixed ring of slots from 0 to 2^32 - 1.
// Each node is placed at hash(node_id) on the ring; each key is placed
// at hash(key); a key belongs to the first node clockwise from its
// position. Adding or removing a node only relocates 1/N of keys.
use sha2::{Sha256, Digest};

fn hash_to_u32(s: &str) -> u32 {
    let mut h = Sha256::new();
    h.update(s.as_bytes());
    let digest = h.finalize();
    u32::from_be_bytes([digest[0], digest[1], digest[2], digest[3]])
}

struct HashRing {
    nodes: Vec<(u32, String)>,   // (position_on_ring, node_id)
}

impl HashRing {
    fn add(&mut self, node: &str) {
        self.nodes.push((hash_to_u32(node), node.to_string()));
        self.nodes.sort_by_key(|&(pos, _)| pos);
    }

    fn owner(&self, key: &str) -> &str {
        let kpos = hash_to_u32(key);
        // First node whose position >= key position; wrap to first if none.
        self.nodes
            .iter()
            .find(|&&(pos, _)| pos >= kpos)
            .map(|(_, id)| id.as_str())
            .unwrap_or(&self.nodes[0].1)
    }
}

// In Cassandra, DynamoDB, memcached clusters: this is how you find the
// node that owns a given key. Add a node and only ~1/N of keys move.

// A toy gossip loop. Each tick: pick a random peer, send our current
// view. Over enough ticks, every node converges to the same state.
use std::collections::HashSet;

struct Node {
    id: u32,
    peers: Vec<u32>,
    seen: HashSet<u32>,   // ids of messages we've already received
}

impl Node {
    fn receive(&mut self, msg_id: u32) -> bool {
        // Return true if this is a new message (worth forwarding).
        self.seen.insert(msg_id)
    }

    fn gossip(&self, msg_id: u32, network: &mut [Node]) {
        // Forward to a small random subset of peers.
        for &peer_id in self.peers.iter().take(3) {
            let peer = &mut network[peer_id as usize];
            if peer.receive(msg_id) {
                // peer also gossips on next tick; epidemic spread.
            }
        }
    }
}

// Real implementations:
//  - Bitcoin: send "inv" announcement, peer requests with "getdata"
//  - Ethereum devp2p: same pattern, richer message types
//  - SWIM (HashiCorp memberlist, Cassandra): ping + indirect ping
//  - HyParView + Plumtree (Erlang): structured gossip overlays

// A toy gossip loop. Each tick: pick a random peer, send our current
// view. Over enough ticks, every node converges to the same state.
use std::collections::HashSet;

struct Node {
    id: u32,
    peers: Vec<u32>,
    seen: HashSet<u32>,   // ids of messages we've already received
}

impl Node {
    fn receive(&mut self, msg_id: u32) -> bool {
        // Return true if this is a new message (worth forwarding).
        self.seen.insert(msg_id)
    }

    fn gossip(&self, msg_id: u32, network: &mut [Node]) {
        // Forward to a small random subset of peers.
        for &peer_id in self.peers.iter().take(3) {
            let peer = &mut network[peer_id as usize];
            if peer.receive(msg_id) {
                // peer also gossips on next tick; epidemic spread.
            }
        }
    }
}

// Real implementations:
//  - Bitcoin: send "inv" announcement, peer requests with "getdata"
//  - Ethereum devp2p: same pattern, richer message types
//  - SWIM (HashiCorp memberlist, Cassandra): ping + indirect ping
//  - HyParView + Plumtree (Erlang): structured gossip overlays

// Byzantine fault tolerance: with f faulty nodes you need at least
// 3f + 1 total to guarantee agreement.
//
//   f = 0  ->  n = 1   (trivial, single trusted node)
//   f = 1  ->  n = 4   (3 honest, 1 byzantine)
//   f = 2  ->  n = 7   (5 honest, 2 byzantine)
//   f = 3  ->  n = 10  (PBFT can guarantee safety + liveness)
//
// The intuition: each "phase" needs 2f+1 acknowledgements to be sure
// the agreement isn't being faked, and the network must still progress
// even with f silent nodes. 2f+1 (for safety) + f (to outvote bad
// quorum) = 3f+1 minimum.
//
// PBFT (Castro & Liskov, 1999) made this practical. Tendermint,
// HotStuff, Diem BFT, and many modern proof-of-stake chains
// are descendants of PBFT.

#include <stdbool.h>
#include <stdint.h>

bool can_agree(int total_nodes, int faulty) {
    return total_nodes >= 3 * faulty + 1;
}

// Byzantine fault tolerance: with f faulty nodes you need at least
// 3f + 1 total to guarantee agreement.
//
//   f = 0  ->  n = 1   (trivial, single trusted node)
//   f = 1  ->  n = 4   (3 honest, 1 byzantine)
//   f = 2  ->  n = 7   (5 honest, 2 byzantine)
//   f = 3  ->  n = 10  (PBFT can guarantee safety + liveness)
//
// The intuition: each "phase" needs 2f+1 acknowledgements to be sure
// the agreement isn't being faked, and the network must still progress
// even with f silent nodes. 2f+1 (for safety) + f (to outvote bad
// quorum) = 3f+1 minimum.
//
// PBFT (Castro & Liskov, 1999) made this practical. Tendermint,
// HotStuff, Diem BFT, and many modern proof-of-stake chains
// are descendants of PBFT.

#include <stdbool.h>
#include <stdint.h>

bool can_agree(int total_nodes, int faulty) {
    return total_nodes >= 3 * faulty + 1;
}