In the previous article, I have introduced the concept of tips selection using unweighted random walk (URW) algorithm. However, URW has its weakness that could crash the IOTA ecosystem. Fortunately, there is a better tips selection method known as the weighted random walk(WRW). In this article, I shall introduce the concept of WRW with the help of some illustrations.
The Lazy Tips
The main issue of using the URW algorithm is the occurrence of lazy tips. Lazy tips are tips that choose to approve some old transactions rather than actively looking to approve new transactions. We label them lazy tips because they could not be bothered to update the latest state of the IOTA Tangle network.
With reference to the diagram above, transaction 17 and transaction 18 are lazy tips as they only approved some old transactions, as shown clearly in the diagram. If we employ the unweighted random walk selection method, these two tips have equal chances to get approved as other tips. Their behaviors would not even be penalized by the IOTA system. If there are too many lazy tips exist in the system, the Tangle will become stagnated or simply failed, as illustrated in the diagram below.
In the diagram above, we notice that the transactions 30 to 38 chose to approve very old transactions, leaving transactions 25 to 29 unapproved, or became orphans. In such situation, the Tangle structure will just stop propagating and eventually crumbles.
Weighted Random Walk
How should we overcome the ‘Lazy Tips’ phenomenon? We might impose a rule that
Weighted random walk uses the bias strategy to select the path towards a particular tip. The bias strategy involves choosing a path that has the highest approved transactions over the path that has very few approved transactions. Here we introduce a term called cumulative weight to denote the number of approvers of the transactions. It means that the higher the number of approvers, the higher the cumulative weight and vice versa. The approvers could both be direct or indirect approvers. Let’s examine the following diagram.
In order to approve tip number 13, the walker needs to walk to transaction number 5. However, transaction 5 only has a cumulative weight of 1, therefore the walker will not continue on this path. Instead, it will look for the path that has the highest cumulative weight. In our example, transaction 3 has a weight of 6, therefore the walker will choose this path and eventually reach transaction 14 and approve it.
The Parameter Alpha
However, even the weighted random walk method has its own weakness. If we insist that every approval of the transactions must follow the rule strictly, we will do away with randomness completely and many tips will be left unapproved. The Tangle system will end up having many unapproved transactions, or orphans. *I introduced my own word orphan which may not be accurate in accordance with the IOTA white paper. You can read the IOTA white paper here.
To overcome the issues, IOTA introduced a parameter α to control the ‘weight’ of the weighted random walk. If α =0, it becomes
Therefore, it is important to find a good balance between approving too many lazy tips and not leaving too many orphaned tips behind. To sum up, finding an ideal value for α is important to maintain the coherence of the Tangle ecosystem championed by IOTA.