Skip to content

Instantly share code, notes, and snippets.

Avatar

Denis Rystsov rystsov

View GitHub Profile
@rystsov
rystsov / cas.js
Created Aug 10, 2020
epoch and hash
View cas.js
// by default ballot has a form of a tuple (tick, node_id)
// so in this piece of code
appeal = casCmd.apply(function(state) {
    if (state.epoch == epoch) {
        state.requests = requests;
        state.epoch += 1;
    }
    return state;
View track-linearizability.js
function write(key, value, prevEtag) {
var etag = GUID.NewGuid();
var record = {
prevEtag: prevEtag,
value: value,
etag: etag
};
log(`${DateTime.now()}: writing(${key}, ${record})`);
db.updateWhen(key, record, x => x.etag == prevEtag);
log(`${DateTime.now()}: written(${key}, ${record})`);
View sc-read-fix.js
function fixed_read(db, key) {
var value = db.read(key);
while (true) {
// If we try to write the read value then we
const written = db.updateWhen(key, {
predicate: `x => x.ver==${value.ver}`,
value: { ver: value.ver+1, val: value.val}
});
if (!written.isConflict) {
// either succeed and return the just written value
View nkbl.cs
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
ForceVsIntelligence();
Console.WriteLine("Intelligence won!");
}
View promiseloop.js
let flag = true;
async function frozen(promise) {
flag = await promise;
console.info("done");
}
let complete = null;
frozen(new Promise((reply, reject) => {
complete = reply;
}));
// you'll never see 'done'
View paxos-made-trivial.js
// Please read the following posts to understand this code:
// - "How Paxos works"
// http://rystsov.info/2015/09/16/how-paxos-works.html
// - "Read write quorums in Paxos"
// http://rystsov.info/2015/12/30/read-write-quorums.html
// - "Best of both worlds: Raft's joint consensus + Single Decree Paxos"
// http://rystsov.info/2016/01/05/raft-paxos.html
// 1. Leader Election (LE)
View state-transition-functions.js
function sign(value, general) {
value.signOffs[general] = true;
if (len(value.signOffs) == 2) {
value.isSent = true;
}
return value;
}
function unsign(value, general) {
if (value == null) {
View fsm.js
function FSM() {
this.state = null;
this.execute = function(action, msg) {
this.state = action(this.state, msg)
};
}
View shifter_binary_search.py
def search(xs, b, e, x):
if b==e:
return b if xs[b] == x else -1
m = (b+e)/2
# [x_b .. x_m x_{m+1} .. x_e]
# x_b <= x_m and x_{m+1} <= x_e # normal, normal
if xs[b] <= xs[m] and xs[m+1] <= xs[e]:
if xs[b] <= x <= xs[m]:
return search(xs, b, m, x)
if xs[m+1] <= x <= xs[e]:
View how-paxos-proposer.py
class Proposer:
def __init__(self, nodes, q, node_id):
self.q = q
self.nodes = nodes
self.node_id = node_id
# generates a new ballot number which is greater than v
def get_n(self, v):
# ...
@endpoint
def change_query(self, change, query, due):