Median

Definition

The median algorithm returns the middle value from a sorted list of validator reports. It is most naturally used for numerical data but can be applied to any ordered set of data.

A possible variant is the weighted median - Let $w^i$ be the stake of data validator $i$, and assume that $\sum_{i=1}^Nw^i=1$. Also, for simplicity, assume that $r_t^1,r_t^2,...,r_t^N$ are sorted. The weighted median is an element $r_t^k$ such that

$$\sum_{i=1}^{k-1} w^i \leq \frac{1}{2} \text{ and } \sum_{i=k+1}^{N} w^i \leq \frac{1}{2}$$

Rationale and Properties

• Resistant to extreme values and outliers, as they only affect the tails of the sorted list—ignores the impact of anomalous data points due to its reliance on central values.

• The aggregation value will always be between the honest reports, assuming a majority of the stake belongs to honest validators (weighted median)

Limitations

• May not reflect the influence of large/small prices if they are outliers

• Non-incremental - the aggregated value cannot be updated upon each report in an online manner (as opposed to mean, for example, which supports $m_n=\frac{n-1}{n}\cdot m_{n-1}+\frac{r_n}{n}$ where $m_i$

  is the mean after $i$ reports and $r_i$ is the $i$-th report).