Introduction

Avalanche is a novel leaderless Byzantine fault tolerant (BFT) consensus protocol introduced in a 2018 paper by a team from Cornell University. It falls under the broader family of "metastable" consensus protocols, which use repeated randomized subsampled voting to drive agreement across the network.

Protocol Execution The Avalanche protocol operates through repeated subsampled voting among validator nodes to determine whether to accept or reject transactions.

When a node wants to query the status of a transaction, it selects a small random sample of k validators from the total validator set. It sends the transaction to each validator in the sample, asking whether that validator believes the transaction should be accepted.

Each queried validator checks whether the transaction in question conflicts with its current preferred set of transactions. If there is no conflict, and the transaction's parents are also preferred, the validator responds positively. If any preferred transaction conflicts, the validator responds negatively.

After the initial node collects the k responses, it tallies the votes. If at least α responders voted positively, the transaction accumulates a "chit" - a tentative positive acceptance vote. The higher the α threshold, the stronger the safety guarantees.

This query process repeats, with the transaction proposer and other nodes sampling the validator network to accumulate chits for the transaction. Once a transaction gains β chits, it is considered finalized and enters the accepted transaction set.

The β parameter determines the confidence threshold before finalization. A higher β provides stronger guarantees but requires more rounds of voting.

There are no fixed leaders or epochs. Any validator can initiate or respond to a query about any transaction at any time. Queries are ongoing and concurrent.

This leaderless, randomly subsampled voting allows Avalanche to scale efficiently. The per-node communication overhead is constant, rather than growing with the total validator set size.

Key Benefits

Avalanche introduces several key benefits:

• Subsampling - Each node only queries a small subset of k validators per decision. This provides major efficiency and scalability gains compared to protocols that require full-network coordination.
• Instant finality - Transactions are irreversibly finalized after reaching the confidence threshold β. This enables single slot finality.
• Leaderless - Without leaders, Avalanche avoids bottlenecks and centralized points of failure.
• Quick convergence - Randomized querying rapidly converges the network, enabling fast finality.
• Customizable parameters - Avalanche exposes parameters like k, α, and β to tune the protocol as needed.

Limitations

However, there are also some limitations to consider:

• The safety guarantee is still probabilistic rather than absolute. High-value applications may demand tighter assurances. Though this could be remedied by including an accountably safe gadget like Gasper, future research would be required to determine how Avalanche's metastable model could be integrated.