Breaking down Tangram’s consensus mechanism: Part 2
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.
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.
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 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.
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 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.
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
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.
Receive are operations which are derived from the core Fork-Event-Join operations.
Send operation is the atomic composition of
Event followed by a
receive operation, on the other hand, combines a
Join and an
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
Here, we see the run begins with a single participant with a
seed stamp which forks into two; one suffers an
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.
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.
For further reading on topics mentioned above, please see the below:
Itc4net is a C# implementation of Interval Tree Clocks (ITC), a causality tracking mechanism. - fallin/Itc4netgithub.com
published 2017-05-07, updated 2017-09-07 This post is a rough transcription of a lightning talk I gave at dotScale…blog.separateconcerns.com
If you’re interested, have questions and feedback:
Visit our website: www.tangrams.io
Read our blog: www.medium.com/@tangramd
Subscribe on Reddit: www.reddit.com/r/Tangrams
Discover us on Discord: www.discord.tangrams.io
Message us on Telegram: https://t.me/Tangrams
Follow us on Twitter: www.twitter.com/tangram
Watch on YouTube: https://www.youtube.com/channel/UCoe5hPG_zjltaG_j2n1Oh4Q