brahms

README

Brahms

An implementation of Brahms: Byzantine resilient random membership sampling. It describes a byzantine resilient gossip protocol that creates a well-connected overlay network with each member only needing to knowing at most O(∛n) other peers.

Documentation

Index

• Variables
• type Core
  • func NewCore(rnd *rand.Rand, self *Node, v0 View, p P, tr Transport, ito time.Duration) (c *Core)
  • func (c *Core) Deactivate()
  • func (c *Core) IsActive() (ok bool)
  • func (c *Core) ReadView() View
  • func (c *Core) ReceiveNode(other Node)
  • func (c *Core) Sample() View
  • func (c *Core) Self() (n Node)
  • func (c *Core) UpdateView(to time.Duration)
  • func (c *Core) ValidateSample(to time.Duration)
• type NID
  • func (id NID) Bytes() []byte
  • func (id NID) IsNil() bool
  • func (id NID) String() string
• type Node
  • func N(ip string, port uint16) (n *Node)
  • func (n *Node) Hash() (id NID)
  • func (n Node) IsZero() bool
  • func (n *Node) String() string
• type P
  • func NewParams(α, β, γ float64, l1, l2, vn int) (p P, err error)
• type Prober
• type SampleRank
  • func (sr SampleRank) ToInt() *big.Int
• type Sampler
  • func NewSampler(rnd *rand.Rand, l2 int, pr Prober, ito time.Duration) (s *Sampler)
  • func (s *Sampler) Clear()
  • func (s *Sampler) RecentlyInvalidated(id NID) (ok bool)
  • func (s *Sampler) Sample() (v View)
  • func (s *Sampler) Update(v View)
  • func (s *Sampler) Validate(rnd *rand.Rand, n int, to time.Duration)
• type Transport
• type View
  • func Brahms(self *Node, rnd *rand.Rand, p P, to time.Duration, s *Sampler, tr Transport, ...) View
  • func NewView(ns ...*Node) (v View)
  • func (v View) Concat(vs ...View) View
  • func (v View) Copy() View
  • func (v View) Diff(other View) (d View)
  • func (v View) Inter(other View) (sect View)
  • func (v View) Pick(r *rand.Rand, n int) (p View)
  • func (v View) Read(id NID) *Node
  • func (v View) Sorted() (ns []Node)
  • func (v View) String() string

Variables

var (

	//ErrPartsDonAddToOne is returned when the partials don't add up to 1
	ErrPartsDonAddToOne = errors.New("α, β, γ don't add together to 1.0")

	//ErrL1AtLeast is returns if l1 was too low
	ErrL1AtLeast = errors.New("l1 must be at least " + strconv.Itoa(minL1))

	//ErrL2AtLeast is returned when l2 is too low
	ErrL2AtLeast = errors.New("l2 must be at least 1" + strconv.Itoa(minL2))
)

var MaxSampleRank = SampleRank{
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
}

MaxSampleRank is the maximum rank a sample can reach

Types

type Core

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

Core keeps the state of a node in the gossip network

func NewCore

func NewCore(rnd *rand.Rand, self *Node, v0 View, p P, tr Transport, ito time.Duration) (c *Core)

NewCore initializes the core

func (*Core) Deactivate

func (c *Core) Deactivate()

Deactivate clears the view and sets the core to non-active state

func (*Core) IsActive

func (c *Core) IsActive() (ok bool)

IsActive is called whenever a remote needs to know if this core is still up

func (*Core) ReadView

func (c *Core) ReadView() View

ReadView returns a copy of our current local view

func (*Core) ReceiveNode

func (c *Core) ReceiveNode(other Node)

ReceiveNode gets called when another peer pushes its info

func (*Core) Sample

func (c *Core) Sample() View

Sample returns a copy of the peer samples this core has

func (*Core) Self

func (c *Core) Self() (n Node)

Self returns this core's own info

func (*Core) UpdateView

func (c *Core) UpdateView(to time.Duration)

UpdateView runs the algorithm to update the view

func (*Core) ValidateSample

func (c *Core) ValidateSample(to time.Duration)

ValidateSample validates if all samples are still responding

type NID

type NID [32]byte

NID is a node id

func (NID) Bytes

func (id NID) Bytes() []byte

Bytes returns the id as a byte slice

func (NID) IsNil

func (id NID) IsNil() bool

IsNil returns whether the is its zero value

func (NID) String

func (id NID) String() string

type Node

type Node struct {
	IP   net.IP
	Port uint16
}

Node describes how to reach another peer in the network

func N

func N(ip string, port uint16) (n *Node)

N describes a node by its ip info

func (*Node) Hash

func (n *Node) Hash() (id NID)

Hash a node description into an ip

func (Node) IsZero

func (n Node) IsZero() bool

IsZero returns whether the node is a zero value

func (*Node) String

func (n *Node) String() string

type P

type P interface {
	L2() int

	L1α() int
	L1β() int
	L1γ() int
	VN() int
}

P offers parameter values to the algorithm

func NewParams

func NewParams(α, β, γ float64, l1, l2, vn int) (p P, err error)

NewParams checks initializes the protocol parameters

type Prober

type Prober interface {
	Probe(ctx context.Context, c chan<- NID, id NID, n Node)
}

Prober allows for probing peers to determine if they are still online

type SampleRank

type SampleRank [32]byte

SampleRank describes a rank based on 32 bytes of data as a big number

func (SampleRank) ToInt

func (sr SampleRank) ToInt() *big.Int

ToInt converts the bytes to the big nr

type Sampler

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

Sampler holds a sample from a node stream such that it is not biased by the nr of times a appears in the stream.

func NewSampler

func NewSampler(rnd *rand.Rand, l2 int, pr Prober, ito time.Duration) (s *Sampler)

NewSampler initializes a sampler with the provided source of randomness

func (*Sampler) Clear

func (s *Sampler) Clear()

Clear the sampler of all samples and mins

func (*Sampler) RecentlyInvalidated

func (s *Sampler) RecentlyInvalidated(id NID) (ok bool)

RecentlyInvalidated returns whether a given node was recently invalidated due to a failing probe

func (*Sampler) Sample

func (s *Sampler) Sample() (v View)

Sample returns a un-biases sample from all seen nodes

func (*Sampler) Update

func (s *Sampler) Update(v View)

Update the sampler with a new set of ids

func (*Sampler) Validate

func (s *Sampler) Validate(rnd *rand.Rand, n int, to time.Duration)

Validate if a random subset of the sampled nodes are still alive

type Transport

type Transport interface {
	Emit(ctx context.Context, c chan<- NID, id NID, msg []byte, to Node)
	Push(ctx context.Context, self Node, to Node)
	Pull(ctx context.Context, c chan<- View, from Node)
	Prober
}

Transport describes how a node communicates with its peers

type View

type View map[NID]Node

View describes a set of node ids

func Brahms

func Brahms(self *Node, rnd *rand.Rand, p P, to time.Duration, s *Sampler, tr Transport, pushes <-chan Node, v View) View

Brahms implements the gossip protocol and takes an old view 'v' and returns a new view.

func NewView

func NewView(ns ...*Node) (v View)

NewView constructs a new view that is a set of a copy of the provided node info.

func (View) Concat

func (v View) Concat(vs ...View) View

Concat views to this view and return it

func (View) Copy

func (v View) Copy() View

Copy returns a copy of this view

func (View) Diff

func (v View) Diff(other View) (d View)

Diff returns all elements that are in this view but not in the other view

func (View) Inter

func (v View) Inter(other View) (sect View)

Inter returns the intersection between two views

func (View) Pick

func (v View) Pick(r *rand.Rand, n int) (p View)

Pick at most n random members from the set and return them as a new view

func (View) Read

func (v View) Read(id NID) *Node

Read a reference to a copy of the node with the provided id

func (View) Sorted

func (v View) Sorted() (ns []Node)

Sorted returns all ids in the view set ordered in lexic order

func (View) String

func (v View) String() string