Breaking down Tangram’s consensus mechanism: Part 2

“A man with a watch knows what time it is. A man with two watches is never sure.”

Published in

Tangram

6 min readApr 28, 2019

In the first part of this series we examined BFT and pBFT, describing on a high-level what a distributed consensus algorithm is. In addition we discussed how Tangram will be using pBFT and its mechanisms, while touching lightly on Byzantine Clock Synchronization and more. In this second part, we will be looking at Interval Tree Clocks and how Tangram uses this mechanism to causally order transactions / block(s).

Interval Tree Clocks — Determining the partial ordering of events

When active nodes on a network interact, it is difficult to efficiently track the order of events as they progress. As the number of participating nodes increases, this becomes increasingly hard. Because such distributed setups are dynamic and rather unpredictable, designing a system able to track the history of events can be rather intricate. Global clocks are limited in their ability to accurately represent the version of events, and as such are not suited for application. Rather, causal history is employed. Tangram employs Interval Tree Clocks as its causality tracking mechanism.

Proposed in a 2008 paper by Almeida, Baquero and Fonte, Interval Tree Clocks offer a novel way of causality tracking which “can be used in scenarios with a dynamic number of participants, allowing a completely decentralized creation of processes or replicas without need for global identifiers”. Members on the network are however able to create, retire or reuse ids as applicable without the need for global management. This makes ITC suitable for practical usage where space and scale are critical factors. To gain better knowledge of Interval Tree Clocks (ITC), it is advisable to read the paper which describes the model.

In the aforementioned paper, ITC is described as the first model for dynamic systems which ignores the need for globally unique ids, does not reuse ids of retired participants, nor requires the global coordination of ids. It manages causal tracking of events in dynamic systems by creating and retiring processes or replicas in a decentralised manner. Like other causality tracking mechanisms, it is modelled by a set of fork-event-join operations which act on stamps structured as a pair of an id and an event, (i , e). However, unlike many other classic mechanisms which may suffer from a bloated size as a result of the use of fixed, predefined functions for ids, ITC allows the manipulation of the id component of a stamp in order to make room for a dynamic number of participants. This allows it to shrink or expand the number of nodal entities as applicable, thereby improving its ability to efficiently manage space and scale requirements.

Fork-Event-Join Model

Tangram uses a C# implementation of ITC, which employs the Fork-Event-Join operations in the manipulation of seed stamps composed of an ID and an event tree.

sample code

This is used to order blocks from a node posting a transaction- that is, ensure that blocks sent from one node carry the same clock stamp when traveling to the next node. After blocks get validated, the node will stamp and sign the block using the ITC method.

Fork

The Fork operation enables the cloning of a seed stamp, generating a pair of stamps which carry identical copies of the stamp’s event component, but unique ids. Unlike other classical mechanisms, ITC’s fork operation does not have to reassign new identifiers to new nodes. Instead it provides a share of the interval (real-valued between 0 and 1) of an existing node to the new node, allowing the assignment of distinct ids to the two nodes. This makes it incredibly suited to a dynamic system where a global authority is absent.

sample code

In Tangram, forking allows the addition of new nodes to the system without bloating the network. To add a new node, an existing node is merely forked and a share of its interval is offered to the new node.

Peek

Peek is specific case of fork which results in two stamps where one has 0 identity and the other retains all the identity of the parent stamp. With Peek it is possible to provide a stamp that can harbour a data record or communicate a message.

sample code

Event

The Event operation modifies the event component of the seed stamp, so that causally the new event happens after the previous. This is used to inflate the stamp or tick the logical clock

sample code

Join

Join operation combines two stamps and returns one that causally dominates both with elements from both ids present. This means both id and event components are merged. The result could be normalized, if possible, and potentially reduce the size of the stamp,. For distributed networks, the join operation is used when nodes want to leave the system. In that case, the departing node surrenders its share of the interval to the live node. This does not require knowledge of any globally unique identifier since the nodes only need to know about their share of the interval. On Tangram’s network where it is envisaged that nodes will come and go at will, this is especially important and will lead to improved efficiency.

sample code

Send & Receive are operations which are derived from the core Fork-Event-Join operations.

Send

A Send operation is the atomic composition of Event followed by a Peek

sample code

Receive

A receive operation, on the other hand, combines a Join and an Event.

sample code

ITC Example Diagram:

The diagram below from the referenced paper shows how ITC’s mechanisms adapts to the number of participants in the network while allowing for multiplication after forks and simplification after joins.

Here, we see the run begins with a single participant with a seed stamp which forks into two; one suffers an event and forks, and the other suffers two events, after which time there are now three participants in the network. The third participant suffers an event while the remaining two synchronize by doing a join followed by a fork. Each carry distinct ids and all take a share of the interval of the parent seed stamp. Though many more operations may follow, ITC is able to accommodate these changes while keeping the seed stamp compact. For example, the event after the final join operation inflated the event tree such that the resulting event is represented by a single integer.

Using ITC allows Tangram to take advantage of robust ordering processes that would be otherwise clunky and sometimes prone to error. Furthermore, while ITC in itself helps significantly in optimizing causality, it is often combined with other methods inside a distributed system that requires overall integrity within a network. In addition to ITC, Tangram uses pBFT, SWIM, Gossip protocol and PoS amongst other things to achieve a more consolidated system.

In Summary

We use Interval Tree Clocks for dynamic participants that do not require global unique identifiers, thereby ensuring consistency of data amongst nodes, decreasing the amount of space needed over time, and improving communication / network latency amongst other things.