Consensus-Based Coordination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

// Basic Paxos (Single-Decree) Implementation
 
interface PaxosMessage {
    proposalNumber: number;
    value?: string;
}
 
interface Promise {
    promised: boolean;
    acceptedProposal?: number;
    acceptedValue?: string;
}
 
class PaxosAcceptor {
    private promisedNumber: number = 0;
    private acceptedNumber: number = 0;
    private acceptedValue: string | null = null;
 
    // Phase 1: Respond to Prepare
    prepare(proposalNumber: number): Promise {
        if (proposalNumber > this.promisedNumber) {
            this.promisedNumber = proposalNumber;
            return {
                promised: true,
                acceptedProposal: this.acceptedNumber,
                acceptedValue: this.acceptedValue || undefined
            };
        }
        return { promised: false };
    }
 
    // Phase 2: Respond to Accept
    accept(proposalNumber: number, value: string): boolean {
        if (proposalNumber >= this.promisedNumber) {
            this.promisedNumber = proposalNumber;
            this.acceptedNumber = proposalNumber;
            this.acceptedValue = value;
            return true;
        }
        return false;
    }
}
 
class PaxosProposer {
    private proposalCounter: number = 0;
    private serverId: number;
    private acceptors: PaxosAcceptor[];
    private quorumSize: number;
 
    constructor(serverId: number, acceptors: PaxosAcceptor[]) {
        this.serverId = serverId;
        this.acceptors = acceptors;
        this.quorumSize = Math.floor(acceptors.length / 2) + 1;
    }
 
    async propose(value: string): Promise<string | null> {
        // Generate unique proposal number (timestamp + serverId)
        const proposalNumber = this.generateProposalNumber();
 
        // ====== PHASE 1: PREPARE ======
        const promises = await Promise.all(
            this.acceptors.map(a => a.prepare(proposalNumber))
        );
 
        const successfulPromises = promises.filter(p => p.promised);
        
        if (successfulPromises.length < this.quorumSize) {
            // Failed to get majority - retry with higher number
            return null;
        }
 
        // Determine value to propose
        let proposedValue = value;
        const previouslyAccepted = successfulPromises
            .filter(p => p.acceptedProposal !== undefined)
            .sort((a, b) => b.acceptedProposal! - a.acceptedProposal!);
 
        if (previouslyAccepted.length > 0) {
            // MUST use the value from highest-numbered accepted proposal
            // This is how Paxos ensures safety
            proposedValue = previouslyAccepted[0].acceptedValue!;
        }
 
        // ====== PHASE 2: ACCEPT ======
        const accepts = await Promise.all(
            this.acceptors.map(a => a.accept(proposalNumber, proposedValue))
        );
 
        const acceptCount = accepts.filter(a => a).length;
        
        if (acceptCount >= this.quorumSize) {
            return proposedValue; // Consensus achieved!
        }
 
        return null; // Failed - retry
    }
 
    private generateProposalNumber(): number {
        // Proposal number must be globally unique and increasing
        // Combine timestamp + server ID
        this.proposalCounter++;
        return Date.now() * 1000 + this.serverId;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

// Raft Protocol Implementation
 
type NodeState = 'FOLLOWER' | 'CANDIDATE' | 'LEADER';
 
interface LogEntry {
    term: number;
    index: number;
    command: string;
}
 
interface RaftNode {
    id: string;
    state: NodeState;
    currentTerm: number;
    votedFor: string | null;
    log: LogEntry[];
    commitIndex: number;
    lastApplied: number;
}
 
class RaftServer implements RaftNode {
    id: string;
    state: NodeState = 'FOLLOWER';
    currentTerm: number = 0;
    votedFor: string | null = null;
    log: LogEntry[] = [];
    commitIndex: number = 0;
    lastApplied: number = 0;
 
    private peers: RaftServer[];
    private electionTimeout: NodeJS.Timeout | null = null;
    private heartbeatInterval: NodeJS.Timeout | null = null;
 
    // ====== LEADER ELECTION ======
    
    startElectionTimer(): void {
        // Randomized timeout: 150-300ms (prevents split votes)
        const timeout = 150 + Math.random() * 150;
        
        this.electionTimeout = setTimeout(() => {
            this.startElection();
        }, timeout);
    }
 
    async startElection(): Promise<void> {
        this.state = 'CANDIDATE';
        this.currentTerm++;
        this.votedFor = this.id;
        
        console.log(`[${this.id}] Starting election for term ${this.currentTerm}`);
 
        const votes = await Promise.all(
            this.peers.map(peer => this.requestVote(peer))
        );
 
        const voteCount = votes.filter(v => v).length + 1; // +1 for self
        const majority = Math.floor((this.peers.length + 1) / 2) + 1;
 
        if (voteCount >= majority && this.state === 'CANDIDATE') {
            this.becomeLeader();
        } else {
            this.state = 'FOLLOWER';
            this.startElectionTimer();
        }
    }
 
    async requestVote(peer: RaftServer): Promise<boolean> {
        const lastLogIndex = this.log.length - 1;
        const lastLogTerm = this.log[lastLogIndex]?.term ?? 0;
 
        // Peer grants vote if:
        // 1. Candidate's term >= peer's term
        // 2. Peer hasn't voted for someone else this term
        // 3. Candidate's log is at least as up-to-date
        return peer.handleVoteRequest(
            this.currentTerm,
            this.id,
            lastLogIndex,
            lastLogTerm
        );
    }
 
    handleVoteRequest(
        term: number,
        candidateId: string,
        lastLogIndex: number,
        lastLogTerm: number
    ): boolean {
        if (term < this.currentTerm) return false;
        
        if (term > this.currentTerm) {
            this.currentTerm = term;
            this.votedFor = null;
            this.state = 'FOLLOWER';
        }
 
        const myLastIndex = this.log.length - 1;
        const myLastTerm = this.log[myLastIndex]?.term ?? 0;
        
        const logOk = (lastLogTerm > myLastTerm) || 
                      (lastLogTerm === myLastTerm && lastLogIndex >= myLastIndex);
 
        if ((this.votedFor === null || this.votedFor === candidateId) && logOk) {
            this.votedFor = candidateId;
            this.resetElectionTimer();
            return true;
        }
 
        return false;
    }
 
    // ====== LOG REPLICATION ======
 
    becomeLeader(): void {
        this.state = 'LEADER';
        console.log(`[${this.id}] Became leader for term ${this.currentTerm}`);
        
        // Send initial empty heartbeat
        this.sendHeartbeats();
        
        // Start heartbeat timer
        this.heartbeatInterval = setInterval(() => {
            this.sendHeartbeats();
        }, 50); // Send heartbeats every 50ms
    }
 
    async appendEntry(command: string): Promise<boolean> {
        if (this.state !== 'LEADER') {
            throw new Error('Not the leader');
        }
 
        const entry: LogEntry = {
            term: this.currentTerm,
            index: this.log.length,
            command
        };
 
        this.log.push(entry);
 
        // Replicate to followers
        const results = await Promise.all(
            this.peers.map(peer => this.replicateToFollower(peer, entry))
        );
 
        const successCount = results.filter(r => r).length + 1;
        const majority = Math.floor((this.peers.length + 1) / 2) + 1;
 
        if (successCount >= majority) {
            this.commitIndex = entry.index;
            return true;
        }
 
        return false;
    }
}