Part 2: Thinking non-linearly

In this tutorial, we’ll talk about forks, what they are, and how we can use them to improve our TODO list process.

Note: we are referring to forks in a process map, not at the blockchain level.

The full code for the project is available here: https://github.com/stratumn/indigo-tutorials/tree/part2-v0.1.0

Why forks are a good thing

In part 1 of this tutorial series, we defined a simple process for a TODO list. The process goes from one step to another, and looks something like this:

A linear process

It clearly shows that, in order, we created a TODO list, added an item, added another item, then finally completed an item. The segments are connected in a linear fashion. There is only one way to traverse our graph — from one step to the next. The last segment contains the latest state of our process.

Our process could have multiple participants. What happens if two participants append to, for instance, the second segment? It creates a fork. We now have two versions of our TODO list, each containing different items:

A linear fork

While sometimes multiple versions of an object can be useful, in our case it creates more problems than it solves. Which segment contains the latest state of our process? Which fork should we append to? How do we prevent participants from appending to the same segment?

The problem is not that forks are possible — it’s that we thought of our process as a list of sequential steps. One thing happens, then the next thing happens, etc… In a concurrent world with multiple participants, this is difficult to achieve, especially if different scenarios can occur after the same step. Our forks could happen accidentally if two people decide to add an item around the same time.

We are not going to discuss how to prevent forks. Process forks are not a problem — they are a tool. A tool we can use to solve the very problem we are having: concurrency. Instead of eliminating forks, we are going to rethink our process with that in mind. Here’s how it will work:

  1. A TODO list is created, resulting in segment A
  2. To add items, we always append to segment A, resulting in segments Bn (B1, B2, etc…)
  3. To complete an item, we append to the item’s segment (B1 for item 1), resulting in segment Cn (C1 for item 1)

A complete process will look like this:

A non-linear-fork

Unlike our previous process, we don’t have forks corresponding to different, separate versions of a list. Instead, the segments combined together form the current state of our process. In the previous img, the map states that we have two items in our list, and that both are complete. Each item has a subprocess represented by a fork, and we always know which fork to append to. As a result, by looking at the entire process, we can all agree on its current state, and we removed the possibility of unintended forks.

Indigo has a feature called tags. We can add a list tag to segment A. We can add an item tag to all the segments Bn, and finally a completion tag to all the segments Cn. To get all the lists, we can query for segments that have the tag list across all maps. To get all the complete items within a list, we can query for segments that have the tag completion in its map. To check if all the items of a list are complete, we can compare the number of segments with the item tag to the number of segments with the completion tag in its map. Using such queries, we can get information about our process’ current state as a whole.

It’s important to note that while our map is non-linear, our timeline is not. Because our timeline is blockchain-based, even though our graph is non-linear, we still know the exact order of events. The segments are stored sequentially in the transactions of our blockchain. Our blockchain gives us a common timeline for the segments (time). The map shows us the connections between the segments (space). Combine space and time, and we get a complete picture.

Finally, note that a process that has both linear and non-linear parts is possible. By combining these two tools, anything can be turned into a process.

Making our process non-linear

Perhaps counterintuitively, our new process is simpler to define — the code will be shorter. Open ./agent/lib/actions-todo.js with your text editor. Let’s update the init function to reflect our new logic:

  /**
   * Creates a new TODO list.
   * @param {string} title - a name for the list
   */
  init: function(title) {
    // Save the list info.
    this.state = {
      title: title
    };

    // Set the `list` tag.
    this.meta.tags = ['list'];

    // Create the first segment.
    this.append();
  },

The first difference is that we no longer save an empty list. We don’t need too — we only care that it’s a list and that it has a title. We don’t need to keep the items in the state because the forks will represent them. Each item will have its own segment. The second difference is that we add the list tag to the segment by adding it to this.meta.tags. We now have the ability to query for segments that represent lists if we need to.

Now let’s update our addItem action:

  /**
   * Adds an item to the TODO list.
   * @param {string} description - a description of the item
   */
  addItem: function(description) {
    // Make sure we are appending a list segment. It should have the `list` tag.
    if (this.meta.tags.indexOf('list') < 0) {
      return this.reject('not a list');
    }

    // Save the item info.
    this.state = {
      description: description
    };

    // Set the `item` tag.
    this.meta.tags = ['item'];

    // Append the new segment.
    this.append();
  },

There are a few things to notice here. First, we no longer require an ID for an item. Since every item has its own segment, we can implicitly use the link hash as the ID of the item. Second, we make sure that an item can only be appended to a segment of the “kind” list by checking the current tags. Third, in the state we only save the description of the item. We already have a segment that describes the list, so why repeat information? We also set the item tag and remove the list tag so that our new segment is of the “kind” item. We can now query for segments that represent items if we need to.

We also need to update our validation rules to show that we don’t require an ID anymore. Update ./validation/rules.json:

{
    "todo": [
        {
            "type": "init",
            "schema": {
                "type": "object",
                "properties": {
                    "title": {
                        "type": "string"
                    }
                },
                "required": [
                    "title"
                ]
            }
        },
        {
            "type": "addItem",
            "schema": {
                "type": "object",
                "properties": {
                    "description": {
                        "type": "string"
                    }
                },
                "required": [
                    "description"
                ]
            }
        }
    ]
}

Finally, let’s update our completeItem action:

  /**
   * Completes an item in the TODO list.
   */
  completeItem: function() {
    // Make sure we are appending an item segment. It should have the `item` tag.
    if (this.meta.tags.indexOf('item') < 0) {
      return this.reject('not an item');
    }

    // We don't need anything in the state.
    this.state = {};

    // Set the `completion` tag.
    this.meta.tags = ['completion'];

    // Append the new segment.
    this.append();
  },

It no longer requires an item ID. We implicitly know which item is complete because it is the previous segment. We also don’t need anything in the state. The fact that we set the completion tag and that we are appending to the segment corresponding to the item gives us all the information we need. If we want to find out if an item is complete, we just need to check if the item segment has a child completion segment.

These are the only changes to our TODO list process. You can use the map explorer (http://localhost:4000) to try the modified actions.

Updating test cases

One last thing — we need to update the test cases. Most changes are minor, and some tests are no longer needed. The only addition is that we check that, for instance, we can only append an item segment to a list segment.

You can find the updated test suite for our non-linear process here: https://github.com/stratumn/indigo-tutorials/blob/part2-v0.1.0/agent/test/actions-todo.js

Exercises

Using the web interface (http://localhost:4000):

  1. Create a new map
  2. Add items to the map
  3. Complete the items
  4. Make sure that if you try to complete a list segment an error occurs
  5. In the Segments section, try finding segments by tag such as item