Ashwin Madavan

Paxos Made Simpler

Tue, 10 Apr 2018 04:20:00 +0000

The only certainty in distributed systems is that machines will fail. The key challenge in building fault-tolerant distributed systems is constructing reliable systems from unreliable components. Distributed databases replicate data across a cluster of machines. By storing copies in different places, distributed databases are tolerant of individual machine failures.

Replication solves the problem of fault-tolerance, but creates another; the various replicas must be kept consistent with each other. A naïve approach is to require all replicas to first agree to apply any modifications made to the database. This would ensure that all replicas remained identical. However, this approach is not fault-tolerant. If any replica were to fail, then no modifications could ever be made to the database until it recovered. Instead, fault-tolerant distributed databases require only a majority of replicas to reach agreement before modifications can be safely applied. This ensures that any majority of replicas will contain at least one that has the latest copy of the database while remaining tolerant of a minority of individual machine failures. Reaching majority agreement in a distributed system is known as consensus, and it is a relatively well-studied problem. In this section, we explore different consensus algorithms culminating with the approach taken in Beaker.

Terminology

We define a proposal as a candidate operation on a group of replicas and a proposer as the replica that initiates consensus on a proposal. Over the course of this discussion, we will gradually refine this definition of a proposal until we arrive at the one used by Beaker.

Replicas communicate by sending messages. We assume that delivered messages cannot be reordered; if message $A$ was delivered before message $B$, then $A$ was sent before $B$. In practice, this assumption is satisfied by most networking protocols including TCP.

Two-Phase Commit

In Two-Phase Commit, the proposer prepares a proposal by first acquring locks on a majority of replicas. If it successfully acquires all locks, the proposer informs all replicas to learn the proposal. When a proposal is learned, its operation is applied and all locks are subsequently released.

Two-Phase Commit is not fault-tolerant. If the proposer were to fail after it successfully prepared a proposal but before it requested that it be learned, the locks that it acquired would never be released and no new proposals could ever be learned. We will see in Paxos how we can modify the protocol to guarantee fault-tolerance.

Paxos

Paxos makes two modifications to Two-Phase Commit to address its fault-intolerance. First, it associates each proposal with a monotonically-increasing, globally-unique ballot number. Proposals are totally-ordered and uniquely-identified by their ballot. Each replica keeps track of the latest ballot that it has seen. Second, it introduces an intermediate accept phase to the protocol. We will see that this additional phase allows the system to recover from proposer failure.

In Paxos, the proposer prepares a proposal by assigning it a ballot greater than any it has seen and sending it to all replicas. If the ballot is greater than the latest it has seen, a replica promises not to accept any proposal less than it and returns any proposal that it has already accepted. Otherwise, the replica ignores the request. Intuitively, ballots function as a kind of a lock that the proposer holds until another proposer prepares a greater ballot. If a majority of replicas do not respond to its prepare request, the proposer retries with a greater ballot. Otherwise, the proposer selects a proposal to be accepted. If any replica returned an accepted proposal, then the proposer must select the latest accepted proposal and set its ballot to the one that it prepared. Otherwise, the proposer selects its own proposal. Intuitively, this allows the system to pick up where it left off when a proposer fails after convinced a majority to accept its proposal but before it could be learned. A replica accepts a proposal if and only if it has not promised not to. When a replica accepts a proposal, it requests that all replicas learn it. A replica learns a proposal when a majority of replicas have requested that it be learned. When a replica is learned, its operation is applied and any accepted proposals are removed. Intuitively, this allows the system to reset and begin consensus on another proposal.

Paxos guarantees that all non-faulty replicas will learn proposals in the same order. Often, this guarantee is unnecessary because a large number of operations on a distributed system are commutative and so they may be performed in any order. For example, reads and writes to different keys in a database may be performed in any order without compromising consistency. We will see in Generalized Paxos that we can exploit commutativity to improve performance.

It is known that no deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous network. Paxos is no exception. If a higher ballot is continuously prepared before any proposal can be accepted, no proposal will ever be learned. Implementations of Paxos typically elect a distinguished replica, called a leader, to which all other replicas forward their proposals to guarantee liveness. Whenever leaders fail, replicas run an instance of Paxos to acquire leadership of the cluster. The reliance on the existence of a single, stable leader is both a important simplifying assumption and a performance limitation. If there exists a leader, then prepare messages are superfluous. Intuitively, the leader implicitly holds a lock on all replicas because no other replica can initiate proposals. This allows proposals to be learned in just two message delays. However, the reliance on the leader to initiate all proposals is also a significant bottleneck at scale. The entire system moves at the rate of the leader. In fact, this is the fundamental limitation in implementations of Paxos like ZooKeeper and Chubby. We will see in Egalitarian Paxos that we can remove the dependence on a leader to improve performance.

Generalized Paxos

Generalized Paxos addresses the scalability of Paxos by exploiting commutativity. An operation $A$ commutes with $B$ if performing $A$ after $B$ has the same effect as performing $B$ after $A$. For example, addition is commutative but division is not; $4 + 3 = 3 + 4$ but $\frac{4}{3} \ne \frac{3}{4}$. In fact, most operations on a distributed database are commutative. Reads commute with each other and reads and writes to different keys commute.

Generalized Paxos associates each proposal with a sequence of operations. We say that proposal $A$ is equivalent to proposal $B$ if all non-commutative operations in $A$ and $B$ are in the same order. All equivalent proposals have the same effect. Generalized Paxos permits replicas to learn different proposals as long as they are equivalent.

In Generalized Paxos, proposers do not forward their requests to leader. Instead, they immediately request that all replicas accept their proposed operation. A replica appends the operation to their currently accepted proposal and requests that all replicas learn it. A proposal is learned when a replica a majority of replicas have requested that it or an equivalent proposal be learned. If no majority of replicas can agree on the ordering of non-commutative operations, it is the responsibility of the leader to select one and to run an instance of Paxos to convince the other replicas to accept its choice before resuming normal operation.

Like Paxos, Generalized Paxos relies on the existence of a single, stable leader to mediate ordering disagreements between replicas and guarantees that all commutative operations will be learned in two message delays. Unlike Paxos, it does not require all proposals to originate from the leader. If most operations are commutative, the leader will rarely be required to arbitrate. However, the existence of a leader can still be a scalability bottleneck. We will see in Egalitarian Paxos that we can remove the dependence on a leader to improve the performance of the system.

Egalitarian Paxos

Egalitarian Paxos makes a subtle modification to Generalized Paxos to remove its dependence on a leader. Egalitarian Paxos associates with proposal with a directed acyclic graph of operations. The benefit of using a directed acyclic graph is its various strongly connected components can be performed in parallel. This has huge ramifications for performance, particularly in databases because reads and writes are relatively expensive operations.

In Egalitarian Paxos, an operation depends on all accepted proposals for which it does not commute. The proposer builds a dependency graph for a proposal from any proposals that it has already accepted and requests that all replicas accept it. A replica supplements the dependency graph of the proposal with any proposals that it has accepted and requests that the result be learned. If no majority of replicas can agree on the dependency graph of a proposal, it is the responsibility of the proposer to select one and to run an instance of Paxos to convince the other replicas to accept its choice before resuming normal operation.

Egalitarian Paxos implicitly assumes that operations are idempotent. An operation $A$ is idempotent if repeated non-sequential applications of $A$ have the same effect as a single application of $A$. For example, multiplication by one is idempotent but by two is not; $4 * 1 = 4 * 1 * 1$ but $4 * 2 \ne 4 * 2 * 2$. In Beaker, we show how Egalitarian Paxos can be modified to implement a distributed, fault-tolerant database.

Beaker

Tue, 13 Mar 2018 04:20:00 +0000

The full code and documentation is available on Github. Cover photograph by Samyuktha Sridhar.

Beaker

Beaker is a distributed, transactional key-value store that is consistent and available. Beaker uses a leader-less variation of Generalized Paxos to consistently execute transactions. Beaker permits a minority of failures and hence it is N / 2 fault tolerant. Beaker assumes that failures are fail-stop. It makes no assumptions about the underlying network except that messages are received in the order they were sent. Most networking protocols, including TCP, satisfy this requirement.

Introduction

A database is a transactional key-value store. Databases map keys to versioned values, called revisions. Revisions are uniquely identified and totally ordered by their version. A transaction depends on the versions of a set of keys, called its readset, and changes the values of a set of keys, called its writeset. Transactions may be committed if and only if the versions they depend on are greater than or equal to their versions in the database. Revisions are monotonic; if a transaction changes a key for which there exists a newer revision, the modification is discarded. This ensures that transactions cannot undo the effect of other transactions. We say that a transaction A conflicts with B if either reads or writes a key that the other writes.

A distributed database is a collection of beakers. Each beaker maintains its own replica of the database. In order to maintain consistency across beakers, a majority of beakers must agree to commit every transaction. Reaching agreement in a distributed system is often referred to as consensus, and it is a relatively well studied problem in computer science. There are a variety of algorithms that solve this problem, most notably Paxos, that have proven to be correct and performant. Beaker employs a variation of Paxos that has several desirable properties. First, beakers may simultaneously commit non-conflicting transactions. Second, beakers automatically repair replicas that have stale revisions. Third, beakers may safely commit transactions as long as they are connected to at least a majority of their non-faulty peers.

Consensus

Beakers reach consensus on proposals. A proposal is a collection of non-conflicting transactions. These transactions may conditionally apply changes or unconditionally repair stale revisions. Proposals are uniquely identified and totally ordered by a ballot number. We say that a proposal A conflicts with B if a transaction that is applied by A conflicts with a transaction that is applied by B. We say that a proposal A is older than B if A conflicts with B and A has a lower ballot than B. We say that a proposal A matches B if A applies the same transactions as B. Proposals A and B may be merged by taking the maximum of their ballots, combining the transactions they apply choosing the transactions in the newer proposal in the case of conflicts, and combining their repairs choosing highest revision changes in the case of duplicates.

The leader for a proposal P first prepares P on a majority of beakers. If a beaker has not made a promise to a newer proposal, it responds with a promise not to accept any proposal that conflicts with the proposal it returns that has a lower ballot than P. If a beaker has already accepted proposals older than P, merges them together and returns the result. Otherwise, it returns the proposal with a zero ballot. If the leader does not receive a majority of promises, it retries with a higher ballot. Otherwise, it merges the returned promises into a single proposal P'. If P does not match P', it retries with P'. Otherwise, the leader gets the latest versions of the keys that are read by P from a majority of beakers. The leader discards all transactions in P that cannot be committed given the latest versions, and sets its repairs to the latest revisions of keys that are read - but not written - by P for which the beakers disagree on their version. The leader then requests a majority of beakers to accept P. A beaker accepts a proposal if it has not promised not to. When a beaker accepts a proposal, it discards all older accepted proposals and broadcasts a vote for it. We say that a proposal is accepted if a majority of beakers vote for it. A beaker learns a proposal once a majority of beakers vote for it. If a beaker learns a proposal, it commits its transactions and repairs on its replica of the database.

Correctness

The proof of correctness relies on the assumption of connectivity, beakers are always connected to all of their non-faulty peers, and the fact of quorum intersection, any majority of beakers will contain at least one beaker in common.

Liveness. An accepted proposal A will eventually be learned. Proof. By quorum intersection, at least one promise will contain A. Therefore, A must be proposed enough beakers learn A such that A is no longer accepted by a majority. By assumption of connectivity, if any beaker learns a proposal then all beakers will eventually learn it.

Linearizability. If a proposal A is accepted, then any conflicting proposal B that is accepted after A will be learned after A. Proof. Because A was accepted before B, the majority that accepted A before B will vote for A before B. Because messages are delivered in order, A will be learned before B.

Commutativity. Let R denote the repairs for an accepted proposal A. Any accepted proposal B that conflicts with A + R but not A commutes with A + R. Proof. Because B conflicts with A + R but not A, B must read a key k that is read by A. By linearizability, B must read the latest version of k because B is accepted. Suppose that B is committed first. Because B reads and does not write k, A + R can still be committed. Suppose that A + R is committed first. Because A + R writes the latest version of k and B reads the latest version, B can still be committed.

Consistency. If a proposal A is accepted, it can be committed. Proof. Suppose there exists a transaction that cannot be committed. Then, the transaction must read a key for which there exists a newer version. This implies that there exists a proposal B that was accepted after but learned before A that changes a key k that is read by A. By linearizability, B cannot conflict with A. Therefore, B must repair k. By commutativity, A may still be committed.

Reconfiguration

Each beaker is required to be connected to a majority of non-faulty peers in order to guarantee correctness. However, this correctness condition is only valid when the cluster is static. In practical systems, beakers may join or leave the cluster arbitrarily as the cluster grows or shrinks in size. In this section, we describe how fresh beakers are bootstrapped when they join an existing cluster. When a fresh beaker joins a cluster, its database is initially empty. In order to guarantee correctness, its database must be immediately populated with the latest revision of every key-value pair. Otherwise, if N -+ 1 fresh beakers join a cluster of size N it is possible for a quorum to consist entirely of fresh beakers.

A naive solution might be for the fresh beaker to propose a read-only transaction that depends on the initial revision of every key-value pair in the database and conflicts with every other proposal. Then, the fresh beaker would automatically repair itself in the process of committing this transaction. However, this is infeasible in practical systems because databases may contain arbitrarily many key-value pairs. This approach would inevitably saturate the network because for a database of size D such a proposal consumes D * (3 * N / 2 + N * N) in bandwidth. Furthermore, it prevents any proposals from being accepted in the interim.

We can improve this solution by decoupling bootstrapping and consensus. A fresh beaker joins the cluster as a non-voting member; it learns proposals, but does not participate in consensus. The fresh beaker reads the contents of the database from a quorum. It then assembles a repair transaction and commits it on its replica. It then joins the cluster as a voting member. This approach consumes just D * N / 2 in bandwidth and permits concurrent proposals.

Caustic

Mon, 06 Nov 2017 04:20:00 +0000

The full code and documentation is available on Github. Cover photograph by Samyuktha Sridhar.

Introduction

Caustic is a transactional programming language for building race-free distributed systems. It allows programmers to write applications as if they were single-threaded, but distribute them arbitrarily without error.

Suppose there exist two programs $A$ and $B$ that each increment a shared counter $C$. Formally, each program reads the current value of $C$, $x$, and then writes $C = x + 1$. If $B$ reads after $A$ writes, then $B$ reads $x + 1$ and writes $C = x + 2$. However, if $B$ reads before $A$ writes but after $A$ reads, then both $A$ and $B$ will read $x$ and write $C = x + 1$. This is known as a race condition, because the value of $C$ depends on the order in which $A$ and $B$ are executed. Race conditions may seem relatively benign, but they can have catastrophic consequences in practical systems. What if your bank determined your balance differently depending on the order in which deposits are made?

Programmers have a variety of synchronization mechanisms at their disposal for dealing with race conditions. However, usage of these mechanisms is cumbersome and error-prone. Caustic implicitly synchronizes wherever it is required by a program. Because the language takes care of synchronization, building distributed systems in Caustic is remarkably simple. Let’s look at a few examples to see just how simple it is in practice.

Distributed Counter

Let’s revisit the distributed counter problem from before. Our algorithm is straightforward, but it is difficult to find simple implementation of a generic, distributed counter. Contrast the implementation of a GCounter in the Akka project with its equivalent in Caustic.

module caustic.example

/**
 * A distributed counter.
 */
service Counter {

  /**
   * Increments the total and returns its current value.
   *
   * @param x Reference to total.
   * @return Current value.
   */
  def increment(x: Int&): Int = {
    if (x != null) x += 1 else x = 1
    x
  }

}

Distributed Queue

Let’s examine a more complicated example. Many distributed systems rely on queues to pass information between decoupled components. Contrast the implementation of a DistributedQueue in the Curator project with its equivalent in Caustic.

module caustic.example

/**
 * A distributed message queue.
 */
service Queue {

  /**
   * Adds the message to the end of the queue.
   *
   * @param queue Queue.
   * @param message Message.
   */
  def push(queue: List[String]&, message: String): Unit =
    queue.set(queue.size, message)

  /**
   * Returns the message at the front of the queue.
   *
   * @param queue Queue.
   * @return Head.
   */
  def peek(queue: List[String]&): String =
    queue.get(0)

  /**
   * Removes and returns the message at the front of the queue.
   *
   * @param queue Queue.
   * @return Head.
   */
  def pop(queue: List[String]&): String = {
    var head = peek(queue)
    queue.set(0, null)
    head
  }

  /**
   * Returns the number of messages in the queue.
   *
   * @param queue Queue.
   * @return Length.
   */
  def size(queue: List[String]&): Int =
    queue.size

}

Nightcrawler

Tue, 28 Feb 2017 04:20:00 +0000

Our news industry thrives off instability and uncertainty, and it’s because Up to 13,000 hanged in Syria’s ‘slaughterhouse’ makes for a much better headline than “Everybody Got Along Today.”

Dan Gilroy’s Nightcrawler, expertly depicts the sensationalism of modern news. It features Jake Gyllenhaal as a sociopathic freelance news cameraman. Jake Gyllenhaal’s character, Louis Bloom, begins the movie trying to make a quick buck recording local crime; however, he quickly finds out that “if it bleeds, it leads.” The more graphic the content, the larger his paycheck. As the movie progresses, he begins to tamper with crime scenes in order to stage them for the best possible shot. He breaks into people’s homes, films the deaths of peers, and shows no restraint in his pursuit of bloody headlines. The movie climaxes in a triple homicide hit-and-run, in which Louis withholds evidence in order to stage a shootout in a crowded restaurant and capture it on camera.

The movie highlights that the news is not designed to best inform, it’s designed to best perform in the ratings. Each night, the news director at the local news station and Louis’s love interest, Nina, and her crew sit together in a room and decide which stories are newsworthy. Nina admits that they, “find [their] viewers are more interested in urban crime creeping into the suburbs. What that means is a victim or victims, preferably well-off and/or white, injured at the hands of the poor, or a minority.” Nina isn’t giving her audience the news that they need to hear, she’s giving them what they want to hear. She and her team selectively purchase and report on news that fits into their narrative. Even after they realized that the triple homicide was not a suburban home invasion but a drug roberry, Nina refused to air the story because it didn’t fit into her portrait of reality. In a conversation with Nina, Louis says that he’s “focusing on framing. A proper frame not only draws the eye into a picture, but keeps it there longer, dissolving the barrier between the subject and the outside of the frame.” Louis almost exclusively films graphic crime scenes and car accidents, but he wants to “dissolve the barrier” between his audience and his images. He doesn’t want to just portray an image of “urban crime creeping into the suburbs” he wants his audience to feel like they are right there alongside the blood and gore. It’s clear that the purpose of the news today isn’t to inform, it’s to create a visceral reaction that supports whatever narrative is pushed by the media.

Despite being surrounded by news on a daily basis, it seems that, more than ever, people are uninformed. It’s not because they aren’t watching the news or paying attention to current events. It’s because a bunch of people in suits get together each night and decide what the world will talk about tomorrow. Towards the end of the movie, Louis admits to the police detective that he’d “like to think if you’re seeing me you’re having the worst day of your life.” Why can’t the news see us on our best days?

Cover photograph by images5.alphacoders.com.

Prime Product Compression

Wed, 08 Feb 2017 04:20:00 +0000

Introduction

This project was inspired by the famous Lockers Riddle. Suppose that there are 1000 lockers in a school with 1000 students. If the first student opens each locker, the second student closes every second locker, the third student opens every third locker if it’s closed and closes it if it’s open, and so on and so forth; which lockers will be closed once every student has had their turn? The answer to this puzzle is relatively straightforward - every perfect-square numbered locker will be closed and all others will be open. However, we may generalize this notion of lockers and students to compression of arbitrary sequences of binary data.

We may think of these 1000 lockers as a sequence of bits, or bit string, in which the value of each bit indicates whether or not the corresponding locker is open or closed. Furthermore, we may think of these students as applying periodic bit flips to this bit string - the first student flips every bit, the second second flips every second bit, etc. We may then represent any bit-string as the sequence of periodic bit flips required to generate it. For example, the bit string 0101 may be generated by flipping every second bit of the zero bit string. Therefore, we may represent the four bit string using just the two bits required to encode the number 2.

Algorithm

Given some bit string $B = \{0, 1\}^N$, allocate some $B' = \{0\}^N$. For each $i = 1, \ldots, N$, if $B_i \neq B'_i$ then for all $\alpha i \leq N$ for $\alpha \in \mathbb{Z}^{+}$ set $B'_{\alpha i} = \neg B'_{\alpha i}$ and append $i$ to some sequence $X$. This procedure corresponds to $i^{th}$ student opening every $i^{th}$ locker if it is closed and closing it if it is open. Clearly, the original bit string $B$ may be recovered by applying the periodic bit flips in $X$ to the zero bit string.

Correctness

Theorem: Upon termination, $B = B'$. Proof: If $B_i \neq B'_i$, the algorithm flips every $i^{th}$ bit. Therefore, after the $i^{th}$ iteration of the algorithm $B_i = B'_i$. Because the algorithm iterates over increasing $i$, future iterations are guaranteed to preserve previous results. Clearly, if $j > i$ and $B_j \neq B'_j$ then $\alpha j > i$ because $j > i$ and $\alpha \geq 1$ so the $i^{th}$ bit is unaffected by the $j^{th}$ iteration. Therefore, upon termination, for each $i$, $B_i = B'_i$. This implies that $B = B'$ upon termination.

Complexity

The $i^{th}$ iteration of the algorithm may require up to $\frac{N}{i}$ bit flips. Therefore, in the worst case, all $N$ iterations may require up to $N \sum_{i=1}^{N} \frac{1}{i}$ bit flips. Clearly, $\sum_{i=1}^{N} \frac{1}{i}$ is the $N^{th}$ partial sum of a harmonic series, which is approximately equal to O(ln N). Therefore, the algorithm is $O(N ln N)$.

Implementation

The algorithm encodes a binary string as a sequence of periodic bit flips and is correctly able to decode this sequence of bit flips back into the original binary string. We may encode this sequence of periodic bit flips as a single prime number $p = \prod prime(X_i)$ where $prime(n)$ returns the $n^{th}$ prime number. Clearly, this number can be decomposed into its prime factors to recover the sequence of periodic bit flips. The implementation of the algorithm and the prime product representation is including below.

from itertools import izip
import random
import math

# List of the first 168 prime numbers (http://primos.mat.br/indexen.html).
primes = [
    -1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 
    83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
    179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 
    271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 
    379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 
    479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 
    599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 
    701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 
    823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 
    941, 947, 953, 967, 971, 977, 983, 991, 997
]


def simulate(n, length):
    """
    Perform a simulation of n trials of bit strings of the specified length. Prints the 
    average compression ratio and the percentage of bit strings that were compressable.

    :param n: Number of trials.
    :param length: Length of bit string.
    """
    def step():
        # Construct and encode a random sequence of bits.
        r = [bool(random.getrandbits(1)) for i in range(length)]
        e = encode(r)

        # Ensure that the decoding is consistent with the original.
        assert r == decode(*e)

        # Calculate the size of the encoding.
        return math.ceil(math.log(abs(e[1]) + 1, 2)) + 1

    s = [step() for i in range(n+1)]
    print("Average bits: " + str(sum(s) / len(s)))
    print("Compressable: " + str(sum(map(lambda x: 1.0 if x < length else 0.0, s)) / len(s)))


def encode(bits):
    """
    Encodes the specified bits as the product of the prime numbers corresponding to the 
    indices in a bit string of all zeroes or all ones (depending on which is smaller), 
    that need to be flipped to generate the bits.
    
    :param bits: Bits to encode.
    :return: Compressed bits.
    """
    copy = [False] * len(bits)
    flip = []

    # Determine the necessary bit flips required to copy the bit string.
    for i, (b, c) in enumerate(izip(bits, copy)):
        if b != c:
            flip.append(i)
            for j in range(i, len(copy), i + 1):
                copy[j] = not copy[j]
    
    if not flip:
        # If there are no bit flips, then return 0.
        return (len(bits), 0)
    else:
        # Otherwise, return the product of the prime numbers associated with each index.
        product = reduce(lambda x, y: x * y, map(lambda x: primes[x], flip))
        return (len(bits), product)


def decode(length, product):
    """
    Decode the prime product by finding its prime factorization and performing the 
    required bit flips on a bit string of all zeroes or all ones (depending on the 
    sign of the product).

    :param length: Length of bit string.
    :param product: Prime product.
    :return: Decoded bits.
    """
    # Find the prime factorization of the product to determine the bit flips.
    if product == 0:
        flip = []
    else:
        flip = [0] if product < 0 else []
        flip.extend([i for i in range(1, length) if abs(product) % primes[i] == 0])
    
    # Perform the bit flips in order on the bit string.
    bits = [False] * length
    for f in flip:
        for i in range(f, length, f + 1):
            bits[i] = not bits[i]
    return bits

Results

The algorithm proved to have relatively poor compression ratios for randomly generated bit strings. However, it is possible that for certain kinds of files this compression strategy may prove to be performant. More rigorous validation is definitely required, but initial results are not promising.

Cover photograph by Tech Crunch.

Bricks

Wed, 08 Feb 2017 04:20:00 +0000

The full code and documentation is available on Github.

Introduction

Facebook Messenger recently launched Instant Games, a new social gaming platform directly integrated into the Messenger application. However, what should have been a fun competition among friends, quickly became an obsession. Tired of waking up every morning to six new notifications about how my high score in Brick Pop had been bested the night before, I set about doing what anyone else would have done in my position - writing an automated solver.

Mechanics

Brick pop is similar to other tile-matching games like Bejewled and Candy Crush. The games begins with a 10x10 matrix of bricks each assigned one of six colors (red, teal, yellow, blue, purple, and gray). The goal of the game is to remove adjacent bricks with matching colors until no bricks remain on the board. Each time that a brick is removed, the bricks above it fall down. Each time an entire column of bricks is removed, the bricks to their right move left. For example, the screenshot below is of a sample game.

Solver

Because the game is relatively small, its sufficient to provide a brute force solution; even the brute force solution terminates in a handful of milliseconds. The brute force algorithm recursively removes adjacent bricks with matching colors and terminates when no bricks remain or all sequences of removals have been tried. By greedily selecting the largest neighborhood of matching color bricks first, the algorithm is likely to find a maximum score path; however, it is not guaranteed to do so.

Determine the set of all neighborhoods of similarly colored bricks. Neighborhoods can be determined using a variation of flood fill, and is guaranteed to visit each brick exactly once.
Sort neighborhoods by size. Removing more bricks at a time produces an exponentially higher score. By greedily selecting the largest possible neighborhood, we ensure that the algorithm earns the highest possible score without having to try all possibilities.
Remove and recurse. Remove each neighborhood and recursively try to solve the remaining board, until some sequence of removals produces an empty board or until all sequences of removals have been tried. Because it is impossible to solve a board in which there exists exactly one brick of any particular color, we can also stop recursing when this condition is met.

Image Processing

Because manual input of individual brick positions proved to be a extraordinarily difficult task, I wrote some simple image processing code that enables you to upload a screenshot of the game from which brick positions are extracted.

Future Work

It would be cool to simulate iPhone touches which would allow the solver to directly play the game without manual intervention.

Cover photograph by Wallpapers Wide.

Swara

Fri, 23 Sep 2016 04:20:00 +0000

The full code and documentation is available on Github. Cover photograph by Samyuktha Sridhar.

Introduction

Swara is the South Indian word for a musical note. It’s an appropriate name for a musical machine learning project that attempts to imitate the legends of South Indian music, who leverage their vast and varied musical experiences to extemporaneously produce profoundly intricate sequences of swaras.

Musical machine learning is an area of active research (e.g. Google Magenta and Jukedeck). In this article, I’ll describe my approach to the development of a variety of musical applications and the various musical and machine learning models that enable them.

Musical Modeling

The first challenge with Swara was to develop a library, swara-music, for digitally representing sheet music. The library enables the programmatic construction and modification of the various musical elements of a song while retaining their underlying musical meaning. For example, a waltz tempo may be constructed using the library in the following manner.

// Waltz Tempo.
val waltz = Tempo(
  signature = Length(4, 4),
  bpm = 80.0
)

The swara-music library currently supports the following musical elements: Song, Fragment, Key, Tempo, Phrase, Voice, Chord, Note, Pitch, and Length. These simple musical primitives can be combined to form highly complex musical arrangements. For example, this code produces the following fragment of sheet music (rendered using MuseScore 2).

However, the library is still too unwieldy to be frequently used to directly write music. To facilitate interoperability with existing music writing tools, the library provides adapters for various file formats (midi, json, etc.).

Working with midi is notoriously difficult
Cool builder pattern

Machine Learning

The next challenge with Swara was to develop swara-learn, a library of generalized machine learning models. Disclaimer: this library does not pretend to compete with high-performance machine learning implementations like TensorFlow and Caffe. This library is simply the result of genuine curiosity into the inner workings of artificial intelligence.

Discrete Markov Chain

A DiscreteMarkovChain is an unsupervised random process that undergoes transitions from one state to another. They are a special case of a family of stochastic models known as markov models, which are used to model random processes in which future states depend only on some number of previous states and not on any states prior. This “memoryless” property, is more formally, the requirement that for some discrete sequence $x_0, \ldots, x_n$ the probability $P(x_n \vert x_{n-1}, \ldots, x_{0}) = P(x_n \vert x_{n-1}, \ldots, x_{k}$ for some $k > 0$.

The implementation of discrete markov chains is built off a simple, but high-performance custom Trie and, unlike other implementations, does not require an explicit definition of the state space and the various transition probabilities between states. The DiscreteMarkovChain is fully thread-safe; therefore, it may be simultaneously be trained and used.

Hidden Markov Model

A HiddenMarkovModel is a supervised learning technique that models a system in which every sequence of observations $O_1, \ldots, O_n$ is generated by a Markov process whose state $H_t$ is hidden from the observer. Hidden markov models are especially useful for sequence prediction (e.g. speech-to-text) and generation (e.g. speech generation). The implementation was designed with the following considerations in mind:

Unknown state space: In many problems, the state space is not known a priori. For example, the state space of all possible chords is infinite because they may contain any number of any note; however, all songs only ever use a finite number of distinct chords. Traditional dyamic programming algorithms like the Viterbi Algorithm require you to preallocate an $n$ by $\vert H \vert$ matrix. This is impossible if the underlying state space $H$ is unknown. Therefore, I was forced to use an A* variation instead.
Concurrency: Implementation will be trained on massive datasets, so it would be interesting if it may be used for prediction and generation while it is trained.

Genetic Algorithms

A genetic algorithm is an algorithm that mimics the processes of biological evolution to find optimal solutions to problems. In high school biology, we learned that when two organisms reproduce their genomes are recombined and mutated to produce offspring. Over many generations, favorable traits are naturally selected and become more predominant within a population. By mathematically defining the genetic operators that enable evolution (recombination, mutation, natural selection), we can harness the power of nature to solve arbitrary problems.

The genetic algorithm library exposes the Selector, Mutator, Evaluator, and Recombinator traits which allow the rules of evolution to be arbitrarily defined for any problem. A Population may then be evolved according to these defined rules.

Evaluator: Maps each individual in the population to an evolutionary fitness score, which represents the likilihood an individual will survive and reproduce (ie. analogue of survival of the fittest).
Selector: Defines which individuals are selected for reproduction (ie. analogue of natural selection).
Recombinator: Defines how two parents who have been selected for reproduction produce offspring (ie. analogue of cellular reproduction).
Mutator: Defines how an individual’s genome is mutated. Essential to encourage diversity and variation within a population (ie. analogue of cellular mutation).

For example, consider the problem of function maximization. Suppose we would like to maximize some function $f \colon \mathbb{R} \mapsto \mathbb{R}$ over some interval $(from, until) \subset \mathbb{R}$ but $f$ is not differentiable. Clearly, the standard method of locating maxima by finding points at which the derivative vanishes is not applicable. However, we may still use a genetic algorithm if we first define the rules of evolution in the context of function maximization. We construct a population of randomly selected points $x \in (from, until)$ and define the evaluator to be $eval(x) = f(x)$, the recombinator to be the average $recombine(x_1, x_2) = \frac{x_1 + x_2}{2}$, the mutator to jitter by a gaussian random $mutate(x) = x + \epsilon$ for $\epsilon ~ N(0, 1)$, and the selector to be a standard Tournament Selector.

val generator  = Rand.uniform.map(_ * (until - from) + from)
var population = Population(Seq.fill(100)(generator.draw()))

(1 to 50).foreach { _ =>
  population = population.evolve(
    selector = new TournamentSelector(5),
    recombinator = (f, m) => (f + m) / 2.0,
    mutator = x => x + Rand.gaussian.draw(),
    evaluator = x => f(x),
  )
}

population.members.maxBy(f)

Future Work

The next challenge of Swara will be to build the swara-core library, which will apply the swara-music and swara-learn libraries to build exciting musical technologies like:

Algorithmic Composition: Generating original, but representative scores of music. Create a SoundCloud Profile with entirely computer generated content.
Fingerprinting: Generating a musical fingerprint, or identifier, which uniquely define a piece of music. This fingerprint can then be used to perform musical identification and search (like Shazam).
Musical Translation: Extracting musical information from audio input sources. It is the musical analogue of speech-to-text.

Algorithms (CS 331H)

Wed, 06 Apr 2016 04:20:00 +0000

Workshop Selection

Let $D$ be the set of all possible days to hold a workshop and let $P$ be the set of people interested in attending the workshop such that each person $p_{i}$ wants to attend during $[s_{i}, f_{i}] \subset D$. Each day $d_{i}$ costs $c_{i}$, but each person $p_{i}$ will willing pay $v_{i}$ to attend. Suppose there is no limit to the number of people that can attend on a particular day, what days should you select to maximize profit?

Constrct a flow network $N = (V, E)$ as follows:

Create a source vertex $s \in V$ and a sink vertex $t \in V$
Create a vertex for each person $p_{i} \in P$
Create a vertex for each day $d_{j} \in D$
Create a directed edge $(s, p_{i})$ of capacity $v_{i}$ for all $p_{i} \in P$
Create a directed edge $(d_{i}, t)$ of capacity $c_{i}$ for all $d_{i} \in D$
Create a directed edge $(p_{i}, d_{j})$ of capacity $\infty$ for all $p_{i}$ such that $d_{j} \in [s_{i}, f_{i}]$

For some subset $U \subset V$, let $rev(U) = \sum\nolimits_{p_{i} \in U} v_{p}$ and $cost(U) = \sum\nolimits_{d_{i} \in U} c_{i}$. Clearly, $profit(U) = rev(U) - cost(U)$.

Find the minimum cut $S, T$ of $N$. Because all $s-t$ paths contain edges of finite capacity by construction, the minimum cut must always be finite. Therefore, the cut-set of the minimum cut $S, T$ may only contain edges of the form $(s, p_{i})$ or $(d_{i}, t)$. Because no edges may cross the cut, all the desired days for each person in $S$ must be in $S$. Consequently, the cut capacity is defined as:

\[c(S, T) = \sum\nolimits_{p_{i} \in T} v_{i} + \sum\nolimits_{d_{j} \in S} c_{j} = rev(T) + cost(S)\]

Therefore,

\[\begin{align*}profit(S) &= rev(S) - cost(S) \\ &= rev(V) - (rev(T) + cost(S)) \\ &= rev(V) - c(S, T)\end{align*}\]

Because $c(S, T)$ is minimal, $profit(S)$ must be maximal. Therefore, the days $d_{i} \in S$ generate the maximal profit of $rev(V) - c(S, T)$.

Detecting Arbitrage

Let $C$ be a set of currencies and let the $R$ be the set of exchange rates between currencies such that $r(c_{i}, c_{j}) \in R$ is the exchange rate between currencies $c_{i}$ and $c_{j}$. Clearly, $r(c_{i}, c_{j}) = \frac{1}{r(c_{j}, c_{i})}$. Arbitrage occurs when there are opportunities for riskless profit. How do you detect arbitrage opportunities between currencies?

In the graph $G = (C, R)$ arbitrage occurs where there exists a cycle of currencies $c_{1},c_{2},\ldots,c_{k},c_{1}$ such that:

\[\begin{align*}r(c_{1}, c_{2}) r(c_{2}, c_{3}) \ldots r(c_{k-1}, c_{k}) r(c_{k}, c_{1}) &> 1\\ \log r(c_{1}, c_{2}) + \log r(c_{2}, c_{3}) + \ldots + \log r(c_{k-1}, c_{k}) + \log r(c_{k}, c_{1}) &> 0\\ \log \frac{1}{r(c_{1}, c_{2})} + \log \frac{1}{r(c_{2}, c_{3})} + \ldots + \log \frac{1}{r(c_{k-1}, c_{k})} + \log \frac{1}{r(c_{k}, c_{1})} &< 0\end{align*}\]

Therefore, detecting arbitrage opportunities in $G$ is equivalent to finding negative cost cycles in the graph $G' = (C, \{ \log \frac{1}{r} : r \in R\})$, which can be found in $O(\lvert C \rvert ^{3})$ using the Floyd-Warshall Algorithm.

Tiling

How many ways can one tile a 3 x n rectangle using 2 x 1 tiles? It is immediately clear that $n$ must be even, because it is impossible to tile an odd area with even area tiles. Therefore, $n = 2 \cdot k$ and $k \in \mathbb{N}$. By enumerating the various ways to tile 2 x 1 tiles on a 3 x $2 \cdot k$ rectangle for $k \in \{1, 2, 3\}$, I determined that the number of tilings:

\[\begin{equation*}T(k) = 3 \cdot T(k - 1) + 2 \cdot T(k - 2) + 2 \cdot T(k - 3) + ... + 2 \cdot T(0)\end{equation*}\] \[\begin{equation*}T(k - 1) = 3 \cdot T(k - 2) + 2 \cdot T(k - 3) + ... + 2 \cdot T(0)\end{equation*}\]

By subtraction of these two equations,

\[\begin{align*} T(k) - T(k - 1) &= [3 \cdot T(k - 1) + 2 \cdot T(k - 2) + ... + 2 \cdot T(0)] - \\ &\ \qquad [3 \cdot T(k - 2) + 2 \cdot T(k - 3) + ... + 2 \cdot T(0)] \\ &= 3 \cdot T(k - 1) - T(k - 2)\end{align*}\]

Therefore, $T(k) = 4 \cdot T(k - 1) - T(k - 2)$. The characteristic equation of this linear homogeneous recurrence relation is $r^{2} = 4 \cdot r - 1$. The roots of this characteristic equation are $a_{1} = \frac{4 + \sqrt{12}}{2} = 2 + \sqrt{3}$ and $a_{2} = \frac{4 - \sqrt{12}}{2} = 2 - \sqrt{3}$. Suppose the closed-form solution of the recurrence relation is of the form

\[T(k) = c_{1} a_{1}^{k} + c_{2} a_{2}^{k} = c_{1} (2 + \sqrt{3})^{k} + c_{2} (2 - \sqrt{3})^{k}\] \[\begin{align*}T(0) = 1 \implies 1 &= c_{1} + c_{2} \implies c_{2} = 1 - c_{1} \\ T(1) = 3 \implies 3 &= c_{1} (2 + \sqrt{3}) + c_{2} (2 - \sqrt{3}) \\ &= c_{1} (2 + \sqrt{3}) + (1 - c_{1}) (2 - \sqrt{3}) \\ &= 2 \sqrt{3} c_{1} + 2 - \sqrt{3}\end{align*}\]

Consequently, $c_{1} = \frac{1 + \sqrt{3}}{2 \sqrt{3}}$ and $c_{2} = 1 - \frac{1 + \sqrt{3}}{2 \sqrt{3}} = \frac{\sqrt{3} - 1}{2 \sqrt{3}}$. Therefore, the closed-form solution to the recurrence relation is $T(k) = \frac{1 + \sqrt{3}}{2 \sqrt{3}} (2 + \sqrt{3})^{k} + \frac{\sqrt{3} - 1}{2 \sqrt{3}} (2 - \sqrt{3})^{k}$ and solves the problem in $O(1)$ time and $O(1)$ space.

How many ways can one tile a k x n rectangle using 2 x 1 tiles? Assuming we can tile the first n-1 columns of the rectangle, how many ways are there to tile the last column? We can either tile elements in the last column one-at-a-time using a horizontal tile or two-at-a-time using a vertical tile. Therefore, the number of ways to tile the last column $f(k) = f(k-2) + f(k-1)$. Because the $n^{th}$ Fibonnaci number $F(n) = \frac{\phi^{n}}{\sqrt{5}}$, the number of ways to tile the last column grows exponentially with $k$. Because there are $n$ columns in the matrix, the complexity of the algorithm is $O(\phi^{nk})$.

Cover photograph by aspireblog.

Originals: How Non-Conformists Move the World Review

Fri, 25 Mar 2016 04:20:00 +0000

The book mentions a fascinating social experiment in which Teresa Amabile created book reviews that had identical content but opposite tones and asked people to rate the intelligence of their authors. Amabile found that, “people rated the critical reviewer as 14% more intelligent, and having 16 percent greater literary expertise, than the complimentary reviewer.” Therefore, despite thoroughly enjoying this book, I’ll focus on its faults first in order to look smarter and more literate than I really am.

I found the most glaring weakness to be the lack of sufficient quantitative evidence. Adam Grant frequently cited the results of studies and social experiments when making arguments about the causes of human creativity; however, he left out details about the statistical significance and margin of error of these results. By omitting the more complete statistical picture, Grant forces his readers to take him at his word. It’s difficult to disagree with his interpretation of these scientific findings, because he only provides the data that supports his claims.

That being said, this was easily one of my favorite books. It was rereadable and highly actionable. I especially liked how Grant used a variety of real life examples to support his claims about originality. The following are ten of my favorite quotes from the book.

“People who suffer the most from a given state of affairs are paradoxically the least likely to question, challenge, reject, or change it.” A reminder that when the going gets tough, fucking do something about it.
“Practice makes perfect, but it doesn’t make new.” Doing the same thing over and over again is going to lead to the same results.
“When it comes to idea generation, quantity is the most predictable path to quality.” Don’t bring any biases or prejudices to the idea generation process. Every idea may not be a good idea, but every idea is useful.
“When we judge their greatness, we focus not on their averages, but on their peaks.” People are remembered by who they were at their best.
“It’s true that the early bird gets the worm, but we can’t forget that the early worm gets caught.” Sometimes it’s the first mover disadvantage. Being first to market can be a disadvantage. It’s much more important to be the best than it is to be the first.
“Timing accounted for forty-two percent of the difference between success and failure.” The best idea requires the best timing to be successful.
“The secret to success is sincerity.” You have to be genuine. Mean everything you say. Do everything you believe.
“Strong opinions, weakly held… Argue like you’re right and listen like you’re wrong.” It’s good to be steadfast in your principles, but its bad for your principles to be steadfast. You should always be open to new thoughts, ideas, and perspectives.
“Never doubt that a small group of thoughtful citizens can change the world; indeed, it’s the only thing that ever has.” Preach.
“Becoming original is not the easiest path in the pursuit of happiness, but it leaves us perfectly poised for the happiness of pursuit.” It’s about the journey, not the destination.

Cover photograph from mycreativejourney2015.

VIX Futures Roll

Tue, 20 Oct 2015 04:20:00 +0000

Introduction

What are futures?

A futures contract is an agreement between two parties, in which the parties agree to exchange some underlying asset at a set price, at some specified time in the future.

For example, consider an upstream oil company (exploration & production). The upstream oil company benefits from higher oil prices, because higher prices allow the company to sell extracted oil for more profit. Suppose the company believes that oil prices will fall next year. If the company does nothing, they risk losing revenues to falling oil prices next year. Instead, the company can sell futures contracts in order to guarantee the current price point for oil sold next year. By locking in the current price, the company is protected against falling prices, but loses out on unrealized revenues if the price of oil rises. Clearly, the seller of futures contracts believes that prices will fall and the buyer of futures contracts believes that prices will rise.

One of the important principles of futures contracts is that their price will always converge to the price of the underlying asset at expiration. In other words, the price of Dec ‘16 oil futures will always converge to the price of oil in Dec ‘16. Why? To eliminate arbitrage opportunities. If the price of a Dec ‘16 oil futures contract was $40 and the price of oil in Dec ‘16 was $20, a smart trader could sell Dec ‘16 contracts at $40, fulfill the contract with oil purchased at $20, and profit off the difference. Similarly, if the price of a Dec ‘16 oil futures contract was $20 and the price of oil in Dec ‘16 was $40, a smart trader could short oil at $40, close the short position with the oil purchased from Dec ‘16 contracts at $20, and profit off the difference. As traders exploit these arbitrage opportunities, the price of oil futures and the price of oil will gradually converge.

Futures have two purposes: hedging exposure to prices (in the case of oil companies) and speculating future prices of an asset. The purpose of this investment strategy is to speculate the future prices of VIX futures.

What is VIX?

Volatility represents the inertia of a securities’ price. High volatility securities are likely to experience dramatic fluctuations in price and low volatility securities are likely to experience smaller shifts in price. There are two kinds of volatility: implied volatility and realized volatility. Implied volatility represents the market’s expectation for future volatility and is determined from options prices and realized volatility represents actual volatility experienced by the market.

VIX is an index that tracks the 30-day implied volatility of the S&P 500. The price of VIX futures contracts represents the market’s expectation for the 30-day implied volatility of the S&P 500 at the expiration of the contract.

Strategy

My trading strategy makes two hypotheses about VIX futures:

The price of VIX futures contracts will move toward the price of the subsequent futures contract. For example, the price of Jan ‘15 contracts will move toward that of Feb ‘15 and the price of Dec ‘15 contracts will move toward that of Jan ‘16.
The larger the difference in price between a VIX futures contract and the subsequent futures contract, the larger the magnitude of the move in price will be. For example, if the price of Jan ‘15 contracts is $15, the price of Feb ‘15 contracts is $20, and the price of March ‘15 contracts is $30; then we can expect the price of Feb ‘15 contracts to move the most.

To prove these hypotheses, I found the correlation between the differences in prices of adjacent futures contracts (e.g., Jan ‘15 and Feb ‘15) and the next day price changes (e.g., price of Jan ‘15 on 3/21 and 3/22). The resulting correlation coefficient of r = 0.934 shows a high degree of correlation between price differences and price changes and signifies that our hypotheses are correct.

Attempt 1: Long Positive Price Differences

My first attempt at the strategy was to purchase the future with the most positive price difference. Because we have shown positive price differences are highly correlated with positive price changes, I expected this attempt to perform extremely well. However, when I backtested the strategy against 9 years of VIX futures data, I ended up losing all my money! The graph below shows the cumulative returns curve. The curve represents the change in portfolio value at each point in time.

Attempt 2: Short Negative Price Differences

Clearly, my first attempt at the strategy was a complete failure. However, I was not yet ready to give up. My next attempt at the strategy sold the future with the most negative price difference (opposite of attempt 1). This strategy performed significantly better than the previous attempt. It produced positive returns and had a Sharpe ratio of 1.28 since 3/21/12. Sharpe ratios represent returns in excess of the risk-free rate; in other words, Sharpe ratios represent risk-adjusted returns. Sharpe ratios greater than 1 are good, greater than 2 are great, and greater than 3 are excellent. The graph below shows the cumulative returns curve.

Attempt 3: Hybrid

When analyzing futures, it is often useful to define two terms: backwardation and contango. Contango refers to periods of time in which futures contracts are trading at a premium to the current price of the underlying asset and backwardation refers to periods of time in which futures contracts are trading at a discount. The blue line in the graph below represents the current price of VIX (the current 30-day implied vol of the S&P 500) and the line in red represents the average price of all VIX futures contracts. Periods of time in which the red line is below the blue line signify backwardation and periods of time in which the red line is above the blue line signify contango.

Why were returns so good in the second attempt and so poor in the first attempt? Weren’t both attempts implementations of the same strategy? The answer lies in the graph above. Careful analysis of this graph will reveal an interesting phenomenon. The period of backwardation beginning October 2008 and ending December 2008 lines up perfectly with the spike in returns in the first attempt over the same period. Similarly, the period of contango beginning October 2011 and ending October 2014 lines up perfectly with the spike in returns in the second attempt over the same period.

Clearly, the best implementation of this strategy is a combination of the previous attempts. In other words, we should purchase futures contracts with the most positive price difference during periods of backwardation and we should sell futures contracts with the most negative price difference during periods of contango. This hybrid strategy had by far the best results and had a sharpe ratio of 1.68 since 3/21/12. The graph below shows the cumulative returns of this attempt.

Future Work

When professional traders analyze futures, they typically use a three-dimensional model: price, volume, and open interest. Volume represents the total number of contracts that changed hands and open interest represents the total number of outstanding contracts. Changes in volume and open interest are important indicators of futures market behavior:

Volume	Open Interest	Effect
rises	rises	Confirms a trend in price
rises	falls	Liquidate position
falls	rises	Period of congestion; selling, but not buying
falls	falls	Period of accumulation; buying, but not selling

Another important factor to consider when trading futures is time to expiration. A futures contract closer to expiration is likely to converge faster to the market price than a futures contract farther from expiration.

Cover photograph by stockideas.org.