In testing my implementation of a distributed failure detector, I needed to be able to: Spawn n instances of the detector, each listening on a different port on localost, making a small local cluster. Redirect each process’ standard output and error streams to separate logfiles, named such that they can be tied back to the generating processes later. After running for some time, terminate all processes, and then analyse the generated logs.

The bakery algorithm was proposed by Leslie Lamport as a solution to Dijkstra’s concurrent programming problem. In the problem, Dijkstra had first identified the need for mutual exclusion among a group of concurrently executing processes. We want to run N processes concurrently, with exclusive access to a shared resource. Modern day languages solve this with help from hardware. But the bakery algorithm allows for pure software mutual exclusion by making sure that at most one process is executing its critical section, while other non-faulty processes are either in their non-critical section, or spinning in place, waiting to get to the critical section.

This is a note to self on computing the lower bound on number of messages each process in a distributed failure detector must send to guarantee adherence to pre-specified values for: Time to first detection of a true failure. False positive detection rate. Message loss rate. In other words, the failure detector accepts as parameters the above three values, and for those guarantees to be respected, each node in the failure detector cluster must send at least $m$ number of messages, which is what we are after.

Gossip based protocols are widely used in distributed systems for robust dissemination of information. The problem: spreading a message among a set of processes. For example, in the Bitcoin P2P network, whenever a new transaction happens, it needs to be broadcast to all peers in order for it to end up on the blockchain. Typically, such information originates at one of the nodes in the network, and needs to be communicated to the rest of the peers.

Suppose we have a bunch of files we’d like to have backed up on a remote host periodically. In this post, I’ll describe my setup that uses rsync with cron. Remote host setup 🔗First we’ll need a place to back up to. I also have a Digital Ocean box, whose IP address is known to me. Any remote box with sufficient disk space would do: all we need is a way to access it.

Hashing is commonly used when we want to reduce a message of an arbitrary size to a fixed length “digest”, for purposes ranging from integrity checking of files downloaded from the internet to building blocks for cryptocurrencies. There are many functions one can use to map the input message to its hash. The only requirement is that the output be of a known, fixed size. For example, consider the function

Numbers are abstractions invented by humans to aid with various activities, mainly counting, and sometimes recreation. While the “three” might be the number of coins in my pocket right now, the number “three” is in itself an abstract entity, worthy of study in its own right. It is defined as the successor to the integer “two”. It is, in general, really hard to define what data is. According to one definition, we define data in terms of operations possible on it, and certain constraints on these operations, like an axiomatic system.

In these exercises, we deal with continued fractions. These are remarkable ways of writing rational and irrational numbers as a sum of an integer and another number, which is itself recursively written as a continued fraction. For instance, $\sqrt{19}$ can be represented as $$ \sqrt{19} = 4+\frac{1}{2+\frac{1}{1 + \frac{1}{3 + \frac{1}{1+\frac{1}{2+\frac{1}{8+…}}}}}} $$ with the continued fractional part being a continued fraction of period 6. Here’s an implementation of the continued fraction computation function in Scheme:

On Linux, most programs that daemonize write their process number to a file, which can be used to send signals to the daemon. To automate deployment (in case you already do not have upstart or systemd integration with the program in question), here’s one approach to stop a daemon with potentially many child processes: Send SIGTERM to the parent process id (known via, say, a file written to by the program while daemonizing).

This approach requires ffmpeg (forked to avconv on Debian), and is not really limited to OpenCV. If you can write raw video frames to stdout, you can use this method. OpenCV video frames are represented as numpy arrays in Python, and the .tostring() method will give the raw frame data that can be piped to ffmpeg. Here is a small program that captures the first video stream and pipes it to ffmpeg to make a video output file called ouput.