$$ \newcommand \SoftVote {\mathrm{SoftVote}} \newcommand \CredentialHistory {\mathbf{C}} \newcommand \CredentialHistorySize {|\CredentialHistory|} \newcommand \CredentialIdx {i^\ast} \newcommand \Timeout {T_\SoftVote} \newcommand \TimeoutGracePeriod {T_\epsilon} \newcommand \lambdaMin {\lambda_\text{0min}} \newcommand \lambdaMax {\lambda_\text{0max}} \newcommand \deltaL {\delta_\text{lag}} $$

Dynamic Filter Timeout

An adaptive algorithm computes the dynamic filter timeout (i.e., the timeout to trigger a call to \( \SoftVote \)).

In regular conditions, the filtering timeout \( \Timeout \) tends to the minimum \( \lambdaMin \).

Whenever network conditions force the round advancement to stall, \( \Timeout \) will diverge towards the maximum of \( \lambdaMax \).

See the formal definition of the filtering timeout parameters in the ABFT normative section.

⚙️ IMPLEMENTATION

Dynamic filter timeout to reference implementation.

Algorithm

Let \( \CredentialHistory \) be a circular array of size \( \CredentialHistorySize \), whose elements are rounds’ minimum credential arrival time, defined as the time (elapsed since the start of \( r \)) at which the highest priority proposal vote was observed for that round.

See the formal definition of the lowest credential priority function in the ABFT normative section.

We now define the credential round lag, as:

$$ \deltaL = \min \left\{ \left\lfloor \frac{2\lambda}{\lambdaMin} \right\rfloor, 8 \right\} $$

to be the rounds’ lookback¹ for \( \CredentialHistory \).

The node tracks in \( \CredentialHistory \) the minimum credential arrival time for a certain number of rounds before \( r - \deltaL \).

Every time a round \( r \) is “successfully” completed², the node looks up the arrival time of the relevant credential for the round \( r - \deltaL \), and pushes it into \( \CredentialHistory \). If the circular array is full, the oldest entry is deleted).

It is worth noting that only rounds completed in the first attempt (\( p = 0 \)) are considered and relevant for \( \CredentialHistory \). If the round is completed in later periods (\( p > 0 \)), that round is skipped and \( \CredentialHistory \) remains unchanged.

⚙️ IMPLEMENTATION

Update credential arrival history reference implementation.

When computing the dynamic filter timeout, if a sufficient history of credentials is available (i.e., the node stored \( \CredentialHistorySize \) past credential arrival times), the array holding this history is sorted in ascending order.

Then \( \CredentialIdx \)-th element is selected as the filtering timeout value³.

Finally, a \( \TimeoutGracePeriod \) extra time is added to the selected entry, for the final filter timeout to be returned as

$$ \Timeout = \CredentialHistory[\CredentialIdx] + \TimeoutGracePeriod $$

Note that the filter timeout \( \lambdaMin \leq \Timeout \leq \lambdaMax \) is clamped on the minimum and maximum bounds defined in the ABFT normative section.

⚙️ IMPLEMENTATION

\( \CredentialIdx \)-th element selection reference implementation.

Parameters

1. With current values for \( \lambda \) and \( \lambdaMin \), \( \deltaL = 2 \). ↩

2. A round is “successfully” completed if a certification bundle is observed and the proposal is already available, or if the proposal for an already present certification bundle is received. ↩

3. With the current parametrization, this corresponds to the 95th percentile of the accumulated arrival times history. ↩