Alpha: playing with randomness

If you have been following the Illustrated Introduction to the Tangle series, you might remember a mysterious parameter called α, which affects the level of randomness in the random walk. In this article we will go into the specific way in which α affects tip selection, and mention some issues to consider when writing a software implementation.

Note that this article assumes a basic understanding of how the Tangle is built, and in particular what approvers and cumulative weights are. You should also be comfortable with the exponential function, and have some understanding of probability theory.

Why do we need randomness again?

To set the stage for understanding α, we need to remember why we perform a random walk in the first place. The context is tip selection: each new transaction must approve two previous transactions. The way this choice is made is crucial in determining how the Tangle looks and behaves.

The tip selection method should ideally provide the following two features:

  1. Once a transaction accumulates a large number of approvers, it is very unlikely to get abandoned.
  2. Honest transactions should get approved quickly.

To achieve the first goal, we might decide to perform a deterministic walk from the genesis to the tips, always going towards the approver with the largest cumulative weight. However, this would hurt the second goal: only a single central chain would get approvals, while most transactions would be left behind.

When we choose tips by always going towards the heaviest approver, many transactions are left behind.

In order to reach a compromise between these two goals, we introduce some randomness. We prefer the heavier approvers, but still give some probability to lighter ones as well.

Mathematical definition

We are defining a transition function, that tells us the probability to go from approvee to ...



This content is synced from the rightful owners. Copyright on text and images belong to the original source.

--
This article was first published on: IOTA - Medium