snowball

package
v1.10.16-rc.11 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 22, 2023 License: BSD-3-Clause Imports: 6 Imported by: 23

Documentation

Index

Constants

View Source
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

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

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

Functions

This section is empty.

Types

type BinarySlush

type BinarySlush 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)
}

BinarySlush is a slush instance deciding between two values. After performing a network sample of k nodes, if you have alpha votes for one of the choices, you should vote for that choice.

type BinarySnowball

type BinarySnowball interface{ BinarySnowflake }

BinarySnowball augments BinarySnowflake with a counter that tracks the total number of positive responses from a network sample.

type BinarySnowflake

type BinarySnowflake 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
}

BinarySnowflake is a snowball instance deciding between two values After performing a network sample of k nodes, if you have alpha votes for one of the choices, you should vote for that choice. Otherwise, you should reset.

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 added in v1.10.12

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

func NewTree added in v1.10.12

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

type Flat

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

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

func (*Flat) Preference

func (sb *Flat) Preference() ids.ID

func (*Flat) RecordPoll

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

func (*Flat) RecordPollPreference added in v1.10.12

func (sb *Flat) RecordPollPreference(choice ids.ID)

func (*Flat) RecordSuccessfulPoll

func (sb *Flat) RecordSuccessfulPoll(choice ids.ID)

func (*Flat) String

func (sb *Flat) String() string

type NnarySlush

type NnarySlush interface {
	fmt.Stringer

	// 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)
}

NnarySlush is a slush instance deciding between an unbounded number of values. After performing a network sample of k nodes, if you have alpha votes for one of the choices, you should vote for that choice.

type NnarySnowball

type NnarySnowball interface{ NnarySnowflake }

NnarySnowball augments NnarySnowflake with a counter that tracks the total number of positive responses from a network sample.

type NnarySnowflake

type NnarySnowflake 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
}

NnarySnowflake is a snowflake instance deciding between an unbounded number of values. After performing a network sample of k nodes, if you have alpha votes for one of the choices, you should vote for that choice. Otherwise, you should reset.

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 added in v1.10.3

func (p Parameters) MinPercentConnectedHealthy() float64

func (Parameters) Verify added in v1.2.0

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 snowball 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 UnarySnowball

type UnarySnowball interface {
	fmt.Stringer

	// RecordSuccessfulPoll records a successful poll towards finalizing
	RecordSuccessfulPoll()

	// RecordPollPreference records a poll that strengthens the preference but
	// did not contribute towards finalizing
	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) BinarySnowball

	// Returns a new unary snowball instance with the same state
	Clone() UnarySnowball
}

UnarySnowball is a snowball instance deciding on one value. After performing a network sample of k nodes, if you have alpha votes for the choice, you should vote. Otherwise, you should reset.

type UnarySnowflake

type UnarySnowflake interface {
	fmt.Stringer

	// RecordSuccessfulPoll records a successful poll towards finalizing
	RecordSuccessfulPoll()

	// 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) BinarySnowflake

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

UnarySnowflake is a snowflake instance deciding on one value. After performing a network sample of k nodes, if you have alpha votes for the choice, you should vote. Otherwise, you should reset.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL