Distributed Algorithm Theory

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <numeric>
5
#include <queue>
6
using namespace std;
7
8
// Simulate synchronous rounds in a connected undirected graph.
9
// FloodMax: each node starts with its UID; in each round it sends its current
10
// maximum UID to neighbors and updates to the maximum received.
11
// After D rounds (graph diameter), all nodes know the global maximum UID (the leader).
12
13
int main() {
14
    ios::sync_with_stdio(false);
15
    cin.tie(nullptr);
16
17
    // Example graph (undirected): 0-1-2-3 and 1-4; diameter D = 3
18
    //      0
19
    //      |
20
    //      1 -- 2 -- 3
21
    //      |
22
    //      4
23
    int n = 5;
24
    vector<vector<int>> adj(n);
25
    auto add_edge = [&](int u, int v){ adj[u].push_back(v); adj[v].push_back(u); };
26
    add_edge(0,1); add_edge(1,2); add_edge(2,3); add_edge(1,4);
27
28
    // Unique IDs per node (could be any distinct integers)
29
    vector<int> uid = {7, 2, 9, 1, 5};
30
31
    // Current known maximum at each node
32
    vector<int> curMax = uid;
33
34
    // Upper bound on rounds: using n as a safe bound if D is unknown
35
    int rounds = n; 
36
37
    for (int r = 0; r < rounds; ++r) {
38
        // In a synchronous round, everyone sends then everyone receives
39
        vector<vector<int>> inbox(n);
40
        for (int u = 0; u < n; ++u) {
41
            for (int v : adj[u]) {
42
                inbox[v].push_back(curMax[u]);
43
            }
44
        }
45
        bool changed = false;
46
        for (int u = 0; u < n; ++u) {
47
            int before = curMax[u];
48
            for (int x : inbox[u]) curMax[u] = max(curMax[u], x);
49
            if (curMax[u] != before) changed = true;
50
        }
51
        // Early stop if stable (no changes); in practice, termination detection can be more involved
52
        if (!changed) break;
53
    }
54
55
    // Determine leader as node holding the maximum UID
56
    int globalMax = *max_element(uid.begin(), uid.end());
57
    int leader = max_element(uid.begin(), uid.end()) - uid.begin();
58
59
    cout << "Global max UID (leader's UID): " << globalMax << "\n";
60
    cout << "All nodes' final view: ";
61
    for (int u = 0; u < n; ++u) cout << curMax[u] << (u+1==n?'\n':' ');
62
    cout << "Elected leader node index: " << leader << " (UID=" << uid[leader] << ")\n";
63
64
    return 0;
65
}
66

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// This is a minimal, single-instance Paxos simulation (happy path, no failures).
5
// Roles: Proposer, Acceptors, Learner. Majority quorums ensure safety.
6
// Messages are delivered synchronously by function calls for simplicity.
7
8
struct Promise {
9
    int promised_n;     // proposal number promised (echo of proposer n)
10
    bool ok;            // whether acceptor promises not to accept < n
11
    int accepted_n;     // last accepted proposal number (if any)
12
    optional<int> accepted_v; // last accepted value (if any)
13
};
14
15
struct Accepted {
16
    int n; // proposal number
17
    int v; // value
18
};
19
20
struct Acceptor {
21
    int id;
22
    int promised_n = -1;        // highest prepare seen
23
    int accepted_n = -1;        // highest accepted proposal number
24
    optional<int> accepted_v;   // value of highest accepted
25
26
    Promise on_prepare(int n) {
27
        Promise p; p.promised_n = n; p.accepted_n = accepted_n; p.accepted_v = accepted_v;
28
        if (n > promised_n) { promised_n = n; p.ok = true; }
29
        else { p.ok = false; }
30
        return p;
31
    }
32
33
    bool on_accept(int n, int v) {
34
        if (n >= promised_n) {
35
            promised_n = n; accepted_n = n; accepted_v = v; return true;
36
        }
37
        return false;
38
    }
39
};
40
41
struct Learner {
42
    int n_acceptors;
43
    int quorum;
44
    map<pair<int,int>, int> votes; // ((n,v) -> count)
45
46
    Learner(int n): n_acceptors(n), quorum(n/2 + 1) {}
47
48
    optional<int> on_accepted(const Accepted &a) {
49
        auto key = make_pair(a.n, a.v);
50
        int c = ++votes[key];
51
        if (c >= quorum) return a.v; // decided
52
        return nullopt;
53
    }
54
};
55
56
struct Proposer {
57
    int my_n; // proposal number (must be unique and increasing across proposers in real systems)
58
    int my_v; // proposed value
59
60
    Proposer(int n, int v): my_n(n), my_v(v) {}
61
62
    // Phase 1: send prepare, collect promises
63
    // Phase 2: choose value (highest accepted if any), send accept
64
    optional<int> run(vector<Acceptor> &accs, Learner &learner) {
65
        // Phase 1: Prepare
66
        vector<Promise> promises;
67
        int ok_count = 0;
68
        for (auto &a : accs) {
69
            Promise p = a.on_prepare(my_n);
70
            if (p.ok) ++ok_count;
71
            promises.push_back(p);
72
        }
73
        int quorum = (int)accs.size()/2 + 1;
74
        if (ok_count < quorum) {
75
            cerr << "No quorum in Phase 1; try higher proposal number.\n";
76
            return nullopt;
77
        }
78
        // Adopt value with highest accepted_n if any
79
        int best_n = -1; optional<int> adopt_v;
80
        for (auto &p : promises) {
81
            if (p.accepted_v.has_value() && p.accepted_n > best_n) {
82
                best_n = p.accepted_n; adopt_v = p.accepted_v;
83
            }
84
        }
85
        int v = adopt_v.has_value() ? *adopt_v : my_v;
86
87
        // Phase 2: Accept
88
        int accept_count = 0; optional<int> decided;
89
        for (auto &a : accs) {
90
            if (a.on_accept(my_n, v)) {
91
                ++accept_count;
92
                auto d = learner.on_accepted({my_n, v});
93
                if (d.has_value()) decided = d;
94
            }
95
        }
96
        if (accept_count < quorum) {
97
            cerr << "No quorum in Phase 2; try again.\n";
98
            return nullopt;
99
        }
100
        return decided; // decided value once majority accepted
101
    }
102
};
103
104
int main(){
105
    ios::sync_with_stdio(false);
106
    cin.tie(nullptr);
107
108
    // Three acceptors tolerate one crash failure for safety (majority quorum = 2)
109
    vector<Acceptor> accs(3);
110
    for (int i = 0; i < 3; ++i) accs[i].id = i;
111
    Learner learner((int)accs.size());
112
113
    // One proposer suggests value 42 with proposal number 1
114
    Proposer p1(1, 42);
115
    auto decided = p1.run(accs, learner);
116
117
    if (decided.has_value()) {
118
        cout << "Decided value: " << *decided << "\n";
119
    } else {
120
        cout << "No decision (try higher proposal number or handle contention).\n";
121
    }
122
123
    return 0;
124
}
125

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Simple 1D linear regression: y ≈ w*x + b
5
// Multiple clients hold local (x,y) pairs. Each performs E local SGD steps and returns updated (w,b).
6
// The server computes a weighted average by client sample counts.
7
8
struct Client {
9
    vector<pair<double,double>> data; // (x, y)
10
11
    // Perform E local SGD steps starting from (w,b)
12
    pair<double,double> local_update(double w, double b, int E, double lr) {
13
        for (int e = 0; e < E; ++e) {
14
            // For simplicity, one pass over data per epoch
15
            for (auto &xy : data) {
16
                double x = xy.first, y = xy.second;
17
                double yhat = w * x + b;
18
                double err = yhat - y;
19
                // Gradients of 1/2 * err^2: d/dw = err*x, d/db = err
20
                double gw = err * x;
21
                double gb = err;
22
                w -= lr * gw;
23
                b -= lr * gb;
24
            }
25
        }
26
        return {w, b};
27
    }
28
};
29
30
int main(){
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
34
    // Create synthetic clients
35
    int K = 5; // clients
36
    vector<Client> clients(K);
37
38
    // True model: y = 3x + 2 with noise
39
    std::mt19937 rng(123);
40
    std::normal_distribution<double> noise(0.0, 0.2);
41
    int points_per_client = 50;
42
    for (int k = 0; k < K; ++k) {
43
        for (int i = 0; i < points_per_client; ++i) {
44
            double x = (k+1) + 0.1*i; // different ranges per client (non-IID-ish)
45
            double y = 3.0 * x + 2.0 + noise(rng);
46
            clients[k].data.emplace_back(x, y);
47
        }
48
    }
49
50
    // Server model
51
    double w = 0.0, b = 0.0; // initial parameters
52
    double lr = 1e-4;        // local learning rate
53
    int E = 1;               // local epochs per round
54
    int R = 20;              // rounds
55
56
    for (int r = 0; r < R; ++r) {
57
        // Broadcast current model to all clients, collect updates
58
        vector<pair<double,double>> updates; updates.reserve(K);
59
        vector<int> sizes; sizes.reserve(K);
60
        for (int k = 0; k < K; ++k) {
61
            auto upd = clients[k].local_update(w, b, E, lr);
62
            updates.push_back(upd);
63
            sizes.push_back((int)clients[k].data.size());
64
        }
65
        // Weighted average by sample counts (FedAvg)
66
        long long N = accumulate(sizes.begin(), sizes.end(), 0LL);
67
        double w_new = 0.0, b_new = 0.0;
68
        for (int k = 0; k < K; ++k) {
69
            double wk = updates[k].first;
70
            double bk = updates[k].second;
71
            double weight = (double)sizes[k] / (double)N;
72
            w_new += weight * wk;
73
            b_new += weight * bk;
74
        }
75
        w = w_new; b = b_new;
76
77
        // Report loss on a small validation sample (approximate)
78
        double loss = 0.0; int cnt = 0;
79
        for (int k = 0; k < K; ++k) {
80
            for (int i = 0; i < (int)clients[k].data.size(); i += 10) { // sample every 10th point
81
                double x = clients[k].data[i].first;
82
                double y = clients[k].data[i].second;
83
                double err = (w * x + b) - y;
84
                loss += 0.5 * err * err; ++cnt;
85
            }
86
        }
87
        cout << "Round " << r << ": w=" << w << ", b=" << b << ", sample loss=" << (loss / max(1, cnt)) << "\n";
88
    }
89
90
    cout << "Final model approx: y = " << w << " * x + " << b << "\n";
91
    return 0;
92
}
93