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 regexp.py
import string
def ltot(l):
def _ltot(l, i):
if len(l)==i: return ()
return (l[i], _ltot(l, i+1))
return _ltot(l, 0)
def symbol(x):
def parser(txt):