Home About MIT CC BY-SA 4.0 RSS

Thoughts and Stuff

photography, coding, running

Volume II

Priorities.

NCurses Notes

Collection of API used for ncurses.

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.

Feature Phones

Recently, I came across on reddit a very cool project – the “Cosmos Browser” – which is a browser which sends HTTP requests over SMS. Communicating over SMS isn’t a novel concept – many SMS APIs exist to communicate between the phone and the outside world (Chicago’s Bus Tracker being one such example). What’s striking here is that I finally understand why these APIs exist: why, given all the smartphones in the world today, with their fancy app stores, would we want to still make apps based on SMS communication? One of the app-makers in the original Reddit post mentioned that a strength of this is the J2ME architecture of the browser – that is, we can install the browser on not just smart phones, but dumb phones as well.

An Update on dOPT

In the process of implementing Cormack’s correction to the dOPT algorithm, I’ve come across several other papers which provide a more complete background of operational transforms and may be of use in the future. They are listed here for sake of documentation – a review of these papers will be provided once I read them carefully.

Concurrency Control in Groupware Systems

What follows is an overview of a 1989 journal article by Ellis and Gibbs regarding collaborative editing. It is the origin of the use of operational transforms. For me, it is particularly useful as the dOPT algorithm for reconstructing a cohoerent global state is introduced here. The global state, in the case of the concurrent text editor, is the contents of the document. In more complex scenarios, the state can consist of much more ill-defined properties – in the case of Google Docs, the state would consist of not only the document text, but also the style rendered (bold, italic, etc.). Indeed, much of the work in finally implementing a robust operational transform framework was actually done while developing Google Wave.

A Counterexample to dOPT (Cormack 1995)

Cormack’s 1995 paper shows a flaw in the original dOPT algorithm, in showing that the strength of the algorithm – the completely decentralized nature of the messaging protocol – leads to divergent states across different clients. Fortunately, Cormack outlines a possible way to fix the algorithm, provided that message passing between nodes is retricted to a point-to-point protocol – that is, we can no longer afford the luxury in a network topology of having circular circuits. Fortunately, for our collaborative editing needs, having a p2p network is actually counterintuitive to our needs, and will not inhibit our needs.

Operational Transform

For the past few months, I’ve been attempting to develop a collaborative code editor in the command line. What that entails essentially is a Google Doc-like interface, but using ncurses, allow the program to be used in the terminal. There are of course software out which allows editing collaboration away from the browser, but a scant few offer this capability from the command line. What I want to do is build a vi-like editor which can be connected to from halfway around the world, as well as locally.

Hi

Like Python, sometimes it’s easier to write in a compile-once-run-many fashion. That is, there are times I find myself wishing that I kept track of some strange idea I had in the middle of the night, or explaining to multiple people some concept or story. Thus, I have created this blog as a reference for both myself and others in the hope that it may be, at best, a learning experience, or at worst, an interesting story to read.