snowball

Documentation

Index

• Constants
• Variables
• type Binary
• type Consensus
  • func NewFlat(factory Factory, params Parameters, choice ids.ID) Consensus
  • func NewTree(factory Factory, params Parameters, choice ids.ID) Consensus
• type Factory
• type Flat
  • func (f *Flat) RecordPoll(votes bag.Bag[ids.ID]) bool
• type Nnary
• type Parameters
  • func (p Parameters) MinPercentConnectedHealthy() float64
  • func (p Parameters) Verify() error
• type Tree
  • func (t *Tree) Add(choice ids.ID)
  • func (t *Tree) RecordPoll(votes bag.Bag[ids.ID]) bool
  • func (t *Tree) RecordUnsuccessfulPoll()
  • func (t *Tree) String() string
• type Unary

Constants

const (
	// MinPercentConnectedBuffer is the safety buffer for calculation of
	// MinPercentConnected. This increases the required percentage above
	// alpha/k. This value must be [0-1].
	// 0 means MinPercentConnected = alpha/k.
	// 1 means MinPercentConnected = 1 (fully connected).
	MinPercentConnectedBuffer = .2
)

Variables

var (
	DefaultParameters = Parameters{
		K:                     20,
		AlphaPreference:       15,
		AlphaConfidence:       15,
		BetaVirtuous:          20,
		BetaRogue:             20,
		ConcurrentRepolls:     4,
		OptimalProcessing:     10,
		MaxOutstandingItems:   256,
		MaxItemProcessingTime: 30 * time.Second,
	}

	ErrParametersInvalid = errors.New("parameters invalid")
)

Types

type Binary

type Binary interface {
	fmt.Stringer

	// Returns the currently preferred choice to be finalized
	Preference() int

	// RecordSuccessfulPoll records a successful poll towards finalizing the
	// specified choice
	RecordSuccessfulPoll(choice int)

	// RecordPollPreference records a poll that preferred the specified choice
	// but did not contribute towards finalizing the specified choice
	RecordPollPreference(choice int)

	// RecordUnsuccessfulPoll resets the snowflake counter of this instance
	RecordUnsuccessfulPoll()

	// Return whether a choice has been finalized
	Finalized() bool
}

Binary is a snow instance deciding between two values. The caller samples k nodes and then calls 1. RecordSuccessfulPoll if choice collects >= alphaConfidence votes 2. RecordPollPreference if choice collects >= alphaPreference votes 3. RecordUnsuccessfulPoll otherwise

type Consensus

type Consensus interface {
	fmt.Stringer

	// Adds a new choice to vote on
	Add(newChoice ids.ID)

	// Returns the currently preferred choice to be finalized
	Preference() ids.ID

	// RecordPoll records the results of a network poll. Assumes all choices
	// have been previously added.
	//
	// If the consensus instance was not previously finalized, this function
	// will return true if the poll was successful and false if the poll was
	// unsuccessful.
	//
	// If the consensus instance was previously finalized, the function may
	// return true or false.
	RecordPoll(votes bag.Bag[ids.ID]) bool

	// RecordUnsuccessfulPoll resets the snowflake counters of this consensus
	// instance
	RecordUnsuccessfulPoll()

	// Return whether a choice has been finalized
	Finalized() bool
}

Consensus represents a general snow instance that can be used directly to process the results of network queries.

func NewFlat

func NewFlat(factory Factory, params Parameters, choice ids.ID) Consensus

func NewTree

func NewTree(factory Factory, params Parameters, choice ids.ID) Consensus

type Factory

type Factory interface {
	NewNnary(params Parameters, choice ids.ID) Nnary
	NewUnary(params Parameters) Unary
}

Factory produces Nnary and Unary decision instances

var (
	SnowballFactory  Factory = snowballFactory{}
	SnowflakeFactory Factory = snowflakeFactory{}
)

type Flat

type Flat struct {
	// wraps the n-nary snow logic
	Nnary
	// contains filtered or unexported fields
}

Flat is a naive implementation of a multi-choice snow instance

func (*Flat) RecordPoll

func (f *Flat) RecordPoll(votes bag.Bag[ids.ID]) bool

type Nnary

type Nnary interface {
	fmt.Stringer

	// Adds a new possible choice
	Add(newChoice ids.ID)

	// Returns the currently preferred choice to be finalized
	Preference() ids.ID

	// RecordSuccessfulPoll records a successful poll towards finalizing the
	// specified choice. Assumes the choice was previously added.
	RecordSuccessfulPoll(choice ids.ID)

	// RecordPollPreference records a poll that preferred the specified choice
	// but did not contribute towards finalizing the specified choice. Assumes
	// the choice was previously added.
	RecordPollPreference(choice ids.ID)

	// RecordUnsuccessfulPoll resets the snowflake counter of this instance
	RecordUnsuccessfulPoll()

	// Return whether a choice has been finalized
	Finalized() bool
}

Nnary is a snow instance deciding between an unbounded number of values. The caller samples k nodes and then calls 1. RecordSuccessfulPoll if choice collects >= alphaConfidence votes 2. RecordPollPreference if choice collects >= alphaPreference votes 3. RecordUnsuccessfulPoll otherwise

type Parameters

type Parameters struct {
	// K is the number of nodes to query and sample in a round.
	K int `json:"k" yaml:"k"`
	// Alpha is used for backwards compatibility purposes and is only referenced
	// during json parsing.
	Alpha *int `json:"alpha,omitempty" yaml:"alpha,omitempty"`
	// AlphaPreference is the vote threshold to change your preference.
	AlphaPreference int `json:"alphaPreference" yaml:"alphaPreference"`
	// AlphaConfidence is the vote threshold to increase your confidence.
	AlphaConfidence int `json:"alphaConfidence" yaml:"alphaConfidence"`
	// BetaVirtuous is the number of consecutive successful queries required for
	// finalization on a virtuous instance.
	BetaVirtuous int `json:"betaVirtuous" yaml:"betaVirtuous"`
	// BetaRogue is the number of consecutive successful queries required for
	// finalization on a rogue instance.
	BetaRogue int `json:"betaRogue" yaml:"betaRogue"`
	// ConcurrentRepolls is the number of outstanding polls the engine will
	// target to have while there is something processing.
	ConcurrentRepolls int `json:"concurrentRepolls" yaml:"concurrentRepolls"`
	// OptimalProcessing is used to limit block creation when a large number of
	// blocks are processing.
	OptimalProcessing int `json:"optimalProcessing" yaml:"optimalProcessing"`

	// Reports unhealthy if more than this number of items are outstanding.
	MaxOutstandingItems int `json:"maxOutstandingItems" yaml:"maxOutstandingItems"`

	// Reports unhealthy if there is an item processing for longer than this
	// duration.
	MaxItemProcessingTime time.Duration `json:"maxItemProcessingTime" yaml:"maxItemProcessingTime"`
}

Parameters required for snowball consensus

func (Parameters) MinPercentConnectedHealthy

func (p Parameters) MinPercentConnectedHealthy() float64

func (Parameters) Verify

func (p Parameters) Verify() error

Verify returns nil if the parameters describe a valid initialization.

An initialization is valid if the following conditions are met:

- K/2 < AlphaPreference <= AlphaConfidence <= K - 0 < BetaVirtuous <= BetaRogue - 0 < ConcurrentRepolls <= BetaRogue - 0 < OptimalProcessing - 0 < MaxOutstandingItems - 0 < MaxItemProcessingTime

Note: K/2 < K implies that 0 <= K/2, so we don't need an explicit check that AlphaPreference is positive.

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree implements the Consensus interface by using a modified patricia tree.

func (*Tree) Add

func (t *Tree) Add(choice ids.ID)

func (*Tree) RecordPoll

func (t *Tree) RecordPoll(votes bag.Bag[ids.ID]) bool

func (*Tree) RecordUnsuccessfulPoll

func (t *Tree) RecordUnsuccessfulPoll()

func (*Tree) String

func (t *Tree) String() string

type Unary

type Unary interface {
	fmt.Stringer

	// RecordSuccessfulPoll records a successful poll that reaches an alpha
	// confidence threshold.
	RecordSuccessfulPoll()

	// RecordPollPreference records a poll that receives an alpha preference
	// threshold, but not an alpha confidence threshold.
	RecordPollPreference()

	// RecordUnsuccessfulPoll resets the snowflake counter of this instance
	RecordUnsuccessfulPoll()

	// Return whether a choice has been finalized
	Finalized() bool

	// Returns a new binary snowball instance with the agreement parameters
	// transferred. Takes in the new beta value and the original choice
	Extend(beta, originalPreference int) Binary

	// Returns a new unary snowflake instance with the same state
	Clone() Unary
}

Unary is a snow instance deciding on one value. The caller samples k nodes and then calls 1. RecordSuccessfulPoll if choice collects >= alphaConfidence votes 2. RecordPollPreference if choice collects >= alphaPreference votes 3. RecordUnsuccessfulPoll otherwise