Implementing dOPT

Implementing Cormack’s 1995 paper was more straightforward than I anticipated; as per the previous discussion with the author, I went ahead and implemented the corrected dOPT algorithm for a tree topology. The source code at the time of this writing can be found on Github for reference; all tests are passing, and no known bugs exist. Any questions on the source code can be directed to me.

In general, the trickiest part of implementing Cormack’s modified dOPT algorithm was in finding a way to generalize the point-to-point algorithm into a tree structure, where

1. each node has at most one parent, and
2. there are no circuits in the topology.

Cormack suggested that each node will keep N + 1 versions of the link data, representing the N children and one parent which the node is connected to. Upon receiving a remote update from one of the links, the node will mask that update as a local update, and broadcast the resulting transformation to every node except the original sender. A (non-functioning) mockup of the process is reproduced here for sake of clarity.

/**
 * the example is given in C++ so that the source code may be easier to understand
 */
class OTNode {
	private:
		sit_t s;
		obj_t x;
		upd_t t(upd_t u, upd_t up, sit_t p, sit_t pp);

		// each incoming link will have associated metadata
		std::map<sit_t, int> VS;
		std::map<sit_t, int> Vs;
		std::map<sit_t, log_t> l;
};

/**
 * OTNode::ins and OTNode::del pushes onto the update queue a local update
 * this queue element is processed in OTNode::process
 */
void OTNode::local_update(upd_t U) {
	// V[S] := V[S] + 1
	for(int index = 0; index < this->VS.size(); ++index) {
		this->VS.begin() + index)->second++;
		// ...
		// send this->VS.at(index)->first
		this->send(S, VS, Vs, U);
		// ...
		// L[V[s] + V[S]] := U
		(this->l.begin() + index)->second[VS + Vs] = U;
	}
	// X := U(X)
	this->apply(U);
}

/**
 * OTNode::proc_ins and OTNode::proc_del pushes the remote update onto the update queue
 */
void OTNode::remote_update(sit_t s, vec_t v, upd_t u) {
	// delay until v[s] = V[s] + 1
	if(vs != Vs + 1) { return; }
	// L[V[s] + v[S] + 1 .. V[s] + V[S] + 1] := ...
	for(int k = Vs + VS; k >= Vs + vS + 1; --k) {
		this->l.at(s)[k] = this->l.at(s)[k - 1];
	}
	// L[V[s] + v[S]] := u
	this->l.at(index)[Vs + vS] = U;
	// for k := V[s] + v[S] + 1 to ...
	upd_t U;
	for(int k = Vs + vS + 1; k < Vs + VS + 1; ++k) {
		U = this->l.at(s)[k];
		this->l.at(s)[k] = this->t(U, u, S, s);
		u = this->t(u, U, s, S);
	}
	// V[s] := V[s] + 1
	this->Vs.at(s)++;
	// broadcast
	for(int index = 0; index < this->VS.size(): ++index) {
		if(s != (this->VS.begin() + index)->first) {
			// do a local update relative to s
			(this->VS.begin() + index)++;
			this->send(S, VS, Vs, U);
			(this->l.begin() + index)->second[Vs + VS] = u;
		}
		this->apply(u);
	}
}

Resources

• entangle-server OT implementation code at the time of this writing.