partial order timestamps, realizing the algorithm for processing event timestamps in Fidge (1988)

partial-order-timestamps.js

// 12 June 2024
// realizing the algorithm for processing event timestamps in Fidge (1988),
// "Timestamps in Message-Passing Systems That Preserve the Partial Ordering"
// https://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf


// missing the query or aggregation step that collects the timestamps and sorts
// them by determinate vs. non-determinate ordering.

// determinate ordering should be singular (i.e., only one permutation) whereas
// there can be multiple non-determinate orderings.


var processes = [];
var log = [];


function Process({ id, value }) {
  if (!(this instanceof Process)) {
    return new Process(...arguments);
  }

  var value = Object(value).valueOf();
  var pid = processes.length;
  var time = Array.from({ length: pid + 1 }).reduce(function (o, v, i, a) {
    a[i] = i == pid
      ? 1
      : 0;
    return a;
  }, 0);

  var subscribers = new Set;

  this.pid = function () { return pid; };
  this.time = function () { return time.slice(); };
  this.value = function (...newValue) {
    if (arguments.length) {
      value = arguments[0];
      time[pid] = time[pid] + 1;
    };

    return value;
  };

  this.subscribe = function (p) {
    if (!(p instanceof Process)) {
      return;
    }

    subscribers.add(p);

    p.send({ pid, stamp: this.time() });
  };

  this.update = async function (next) {
    this.value(next);

    return this.notify(value);
  };

  this.notify = function (value) {
    var stamp = this.time();

    subscribers.forEach((p, i) => {
      if (p == this) {
        return;
      }

      p.send({ pid, stamp });
    });

    return { id, time: `[${stamp.join(",")}]` };
  };

  this.send = function ({ pid, stamp }) {
    stamp.forEach((v, i) => {
      if (i == this.pid()) {
        return;
      }

      time[i] = Math.max(
        v,
        i in time
          ? time[i]
          : 0
      );
    });

    log.push({ id, stamp: time.slice() });
  };

  processes.push(this);

  processes.forEach((p, i, a) => {
    if (p == this) {
      return;
    }

    p.send({ pid, stamp: this.time() });
  });
}


/* test it out */


~(function() {
  setTimeout(() => {
    var a = Process({ id: 'a', value: 12 });
    var b = Process({ id: 'b', value: 23 });
    var c = Process({ id: 'c', value: 34 });
    var d = Process({ id: 'd', value: 45 });

    a.subscribe(b);

//     a.update(19).then(t => console.log(t));

    c.subscribe(b);
    c.subscribe(a);

//     c.update(47).then(t => console.log(t));

    b.subscribe(c);

    //b.update(333).then(t => console.log(t));
    a.value(8);

    a.update('a').then(t => console.log(t));

    c.update('w').then(t => console.log(t));
    c.update('x').then(t => console.log(t));

    b.update('o').then(t => console.log(t));

    a.update('c').then(t => console.log(t));

    b.update('p').then(t => console.log(t));

    d.update(12323).then(t => console.log(t));

    c.subscribe(d);

    d.update("twelve").then(t => console.log(t));

    c.update(34).then(t => console.log(t));

    d.subscribe(c);

    d.update("eighteen").then(t => console.log(t));

    c.update('same').then(t => console.log(t));

    console.group("sync");
      console.group("processes");
        processes.forEach(p => {
          console.log(p.pid(), p.value(), p.time())
        });
      console.groupEnd("processes");

      console.group("log");
        log.forEach(item => {
          console.log(`${item.id}: [${item.stamp.join(" ")}]`);
        });
      console.groupEnd("log");
    console.groupEnd("sync");

  }, 100);
})();