The Hedera network is known for delivering high performance and scale for applications built on the network. Contributors to the Hedera codebase continually innovate based on how well the system responds to real-world traffic load and scenarios, particularly as usage continues its rapid growth. Recent efforts by contributors have been geared towards increasing efficiency while also improving the system's tuning capabilities.
These efforts have resulted in an optimization in the core algorithms, specifically optimizing how nodes select events as other-parents to ensure a more efficient hashgraph is created during the consensus process.
The Hedera network uses the hashgraph consensus algorithm, which is based on gossip, where each node on the network exchanges informational “events” that contain transactions. Nodes exchange events to achieve consensus on the ordering and timestamping of the transactions contained within these events.
Events are linked together, forming a parent-child relationship. When a node creates a new event, it selects other events to be the parents of the new event: one self parent (i.e., the last event the node created) and one other-parent (i.e., an event recently created by a different node).
Selecting an event's parents determines the topology of the hashgraph. Choosing a good parent results in a graph that has a shape that leads to faster consensus. Making a poor choice in parentage can lead to a graph which results in slower consensus. It is even possible that poorly selecting a parent could create a new event that does nothing to advance consensus, which is a missed opportunity.
To ensure peak efficiency, nodes should choose other-parents in a manner that fosters a good hashgraph. This blog introduces a newly implemented approach to selecting the other-parent in order to enhance hashgraph performance significantly.
In the early stages of development of the Hedera network, the selection of other-parents relied primarily on random choices from the global list of nodes, which was sufficient for the network's initial scale. However, as the network expanded over time, this approach required refinement.
Enter Optimized Other-Parent Selection, an algorithm that allows nodes to analyze the topological properties of various potential parents and rank their quality. While the specific details of how this works is outside the scope of this blog, there’s a detailed description of the algorithm available on Github.
Nevertheless, let's delve into this topic from a broader perspective. An important concept is the introduction of a novel parameter called a "tipset" that is associated with each event within the network. A tipset serves as a representation of the latest event that is known from every individual node within the network, as perceived when looking at all ancestors of a particular event. In other words, there is a downward path in the hashgraph from this event to each event in its tipset.
For example, the diagram above shows the tipset mapping for Event 103:
Node A = 103, is in its own tipsetNode B = 101, shared directly known via Event 103
Node C = 96, known via Event 100Node D = 100, known via Event 101
Node E = 94, known via Event 101, Event 100, and finally Event 99
With the introduction of the tipset parameter mapping, other-parent selection can be evaluated to see which choice of other-parent yields a tipset that advances consensus the most when compared to previous “snapshot” of tipsets.
To illustrate this concept, consider Event 107 as an example. In the diagram below, you can observe Node A’s new Event 107 marked in blue, for which it must choose an other-parent. In this example, we’ll consider the purple nodes as the snapshot of the tipsets by which we can evaluate and score the options for other-parent selection.
From the four options listed we can calculate an advancement count of each option. The advancement count is the number of events that will become part of the tipset if selected as the other-parent. The count is starting after the tipset snapshot and includes the new event itself. Here’s the results of the example above:
Option
Advancement Count
Tipset mapping
1
3
Event 107, Event 106, Event 104
2
Event 107, Event 104
Event 107, Event 102
4
Event 107, Event 105, Event 10
When evaluated there are two options with the highest advancement count: options 1 and 4. If one of the choices has a higher score than the other, it is chosen and a new event is created with the selected parent. In the event of a tie, as in our case, the algorithm will randomly select an event from the two options.
Note: The example above has been simplified for illustrative purposes and differs from actual implementation. Please refer to the detailed description on Github for further reference.
The optimized other-parent selection feature was integrated into Release 41, which was deployed on the network on September 20, 2023. Upon analyzing the data, several favorable outcomes of this change became evident.
One noteworthy observation is that this optimization has allowed Hedera to maintain its transaction volume and latency while reducing the number of events shared between nodes by about half. As mentioned earlier, this improvement streamlines the consensus process, achieving the same results with a significantly lower event count.
The Grafana dashboard above provides a visual representation of the average number of events sent out by a node per second. There is a noticeable and sustained decrease of almost 50% immediately following the deployment of Release 41. This graph highlights the significant impact of the optimization introduced in this release.
System throttles play a pivotal role in upholding the stability of the Hedera network. They serve as essential safeguards that help prevent the system from scaling resources to a point of potential overload and maximum capacity breach.
A new tipset related throttle, MaxCreationRate, has been introduced to govern the maximum rate at which a node can generate events. This addition has demonstrated remarkable effectiveness in regulating the event creation rate.
This can be observed in the Grafana dashboard below, which uses various colors to illustrate the mean number of events generated by each node on Mainnet.
Before Release 41 was deployed, there was significant variability in the number of events generated by nodes across the network. However, after Release 41 on September 20, 2023, the event creation rate exhibits a consistent, flatline pattern that is largely uniform across nodes. This development presents an additional method for fine-tuning the network, ensuring it maintains steady and reliable performance as it adapts to the evolving demands of the network over time.
These initial results indicate that the optimizations have made substantial strides in enhancing efficiency, paving the way for sustained usage growth while upholding performance and latency standards.
Key takeaways from these optimizations include:
Maintained throughput and performance.
A remarkable reduction of approximately half the number of events created per second.
Introduction of a new parameter for network tuning.
Optimizations like these, implemented at the core protocol level, consistently bolster the performance and scalability of decentralized applications on the Hedera network. Thank you to all of the Hedera contributors for continuing to push the boundaries of low latency, high throughput, and massive scale.