vector

Documentation

Index

• type BranchSeq
  • func (seq BranchSeq) IsForkDetected() bool
• type HighestBeforeSeq
  • func NewHighestBeforeSeq(size int) HighestBeforeSeq
  • func (b HighestBeforeSeq) Get(i idx.Validator) BranchSeq
  • func (b *HighestBeforeSeq) Set(i idx.Validator, seq BranchSeq)
  • func (b HighestBeforeSeq) Size() int
• type HighestBeforeTime
  • func NewHighestBeforeTime(size int) HighestBeforeTime
  • func (b HighestBeforeTime) Get(i idx.Validator) inter.Timestamp
  • func (b *HighestBeforeTime) Set(i idx.Validator, time inter.Timestamp)
  • func (b HighestBeforeTime) Size() int
• type Index
  • func NewIndex(config IndexConfig, validators *pos.Validators, db kvdb.KeyValueStore, ...) *Index
  • func (vi *Index) Add(e *inter.EventHeaderData)
  • func (vi *Index) DropNotFlushed()
  • func (vi *Index) Flush()
  • func (vi *Index) ForklessCause(aID, bID hash.Event) bool
  • func (vi *Index) GetHighestBeforeAllBranches(id hash.Event) HighestBeforeSeq
  • func (vi *Index) GetHighestBeforeSeq(id hash.Event) HighestBeforeSeq
  • func (vi *Index) GetHighestBeforeTime(id hash.Event) HighestBeforeTime
  • func (vi *Index) GetLowestAfterSeq(id hash.Event) LowestAfterSeq
  • func (vi *Index) MedianTime(id hash.Event, genesisTime inter.Timestamp) inter.Timestamp
  • func (vi *Index) NoCheaters(selfParent *hash.Event, options hash.Events) hash.Events
  • func (vi *Index) Reset(validators *pos.Validators, db kvdb.KeyValueStore, ...)
  • func (vi *Index) SetHighestBefore(id hash.Event, seq HighestBeforeSeq, time HighestBeforeTime)
  • func (vi *Index) SetLowestAfter(id hash.Event, seq LowestAfterSeq)
• type IndexCacheConfig
• type IndexConfig
  • func DefaultIndexConfig() IndexConfig
• type LowestAfterSeq
  • func NewLowestAfterSeq(size int) LowestAfterSeq
  • func (b LowestAfterSeq) Get(i idx.Validator) idx.Event
  • func (b *LowestAfterSeq) Set(i idx.Validator, seq idx.Event)
  • func (b LowestAfterSeq) Size() int

Types

type BranchSeq

type BranchSeq struct {
	Seq    idx.Event // maximum observed e.Seq in the branch
	MinSeq idx.Event // minimum observed e.Seq in the branch
}

BranchSeq encodes Seq and MinSeq into 8 bytes

func (BranchSeq) IsForkDetected

func (seq BranchSeq) IsForkDetected() bool

IsForkDetected returns true if observed fork by a creator (in combination of branches)

type HighestBeforeSeq

type HighestBeforeSeq []byte

HighestBeforeSeq is a vector of highest events (their Seq + IsForkDetected) which are observed by source event

func NewHighestBeforeSeq

func NewHighestBeforeSeq(size int) HighestBeforeSeq

NewHighestBeforeSeq creates new HighestBeforeSeq vector.

func (HighestBeforeSeq) Get

func (b HighestBeforeSeq) Get(i idx.Validator) BranchSeq

Get i's position in the byte-encoded vector clock

func (*HighestBeforeSeq) Set

func (b *HighestBeforeSeq) Set(i idx.Validator, seq BranchSeq)

Set i's position in the byte-encoded vector clock

func (HighestBeforeSeq) Size

func (b HighestBeforeSeq) Size() int

Size of the vector clock

type HighestBeforeTime

type HighestBeforeTime []byte

HighestBeforeTime is a vector of highest events (their ClaimedTime) which are observed by source event

func NewHighestBeforeTime

func NewHighestBeforeTime(size int) HighestBeforeTime

NewHighestBeforeTime creates new HighestBeforeTime vector.

func (HighestBeforeTime) Get

func (b HighestBeforeTime) Get(i idx.Validator) inter.Timestamp

Get i's position in the byte-encoded vector clock

func (*HighestBeforeTime) Set

func (b *HighestBeforeTime) Set(i idx.Validator, time inter.Timestamp)

Set i's position in the byte-encoded vector clock

func (HighestBeforeTime) Size

func (b HighestBeforeTime) Size() int

Size of the vector clock

type Index

type Index struct {
	logger.Instance
	// contains filtered or unexported fields
}

Index is a data to detect forkless-cause condition, calculate median timestamp, detect forks.

func NewIndex

func NewIndex(config IndexConfig, validators *pos.Validators, db kvdb.KeyValueStore, getEvent func(hash.Event) *inter.EventHeaderData) *Index

NewIndex creates Index instance.

func (*Index) Add

func (vi *Index) Add(e *inter.EventHeaderData)

Add calculates vector clocks for the event and saves into DB.

func (*Index) DropNotFlushed

func (vi *Index) DropNotFlushed()

DropNotFlushed not connected clocks. Call it if event has failed.

func (*Index) Flush

func (vi *Index) Flush()

Flush writes vector clocks to persistent store.

func (*Index) ForklessCause

func (vi *Index) ForklessCause(aID, bID hash.Event) bool

ForklessCause calculates "sufficient coherence" between the events. The A.HighestBefore array remembers the sequence number of the last event by each validator that is an ancestor of A. The array for B.LowestAfter remembers the sequence number of the earliest event by each validator that is a descendant of B. Compare the two arrays, and find how many elements in the A.HighestBefore array are greater than or equal to the corresponding element of the B.LowestAfter array. If there are more than 2n/3 such matches, then the A and B have achieved sufficient coherency.

If B1 and B2 are forks, then they cannot BOTH forkless-cause any specific event A, unless more than 1/3W are Byzantine. This great property is the reason why this function exists, providing the base for the BFT algorithm.

func (*Index) GetHighestBeforeAllBranches

func (vi *Index) GetHighestBeforeAllBranches(id hash.Event) HighestBeforeSeq

GetHighestBeforeAllBranches returns HighestBefore vector clock without branches, where branches are merged into one

func (*Index) GetHighestBeforeSeq

func (vi *Index) GetHighestBeforeSeq(id hash.Event) HighestBeforeSeq

GetHighestBeforeSeq reads the vector from DB

func (*Index) GetHighestBeforeTime

func (vi *Index) GetHighestBeforeTime(id hash.Event) HighestBeforeTime

GetHighestBeforeTime reads the vector from DB

func (*Index) GetLowestAfterSeq

func (vi *Index) GetLowestAfterSeq(id hash.Event) LowestAfterSeq

GetLowestAfterSeq reads the vector from DB

func (*Index) MedianTime

func (vi *Index) MedianTime(id hash.Event, genesisTime inter.Timestamp) inter.Timestamp

MedianTime calculates weighted median of claimed time within highest observed events.

func (*Index) NoCheaters

func (vi *Index) NoCheaters(selfParent *hash.Event, options hash.Events) hash.Events

NoCheaters excludes events which are observed by selfParents as cheaters. Called by emitter to exclude cheater's events from potential parents list.

func (*Index) Reset

func (vi *Index) Reset(validators *pos.Validators, db kvdb.KeyValueStore, getEvent func(hash.Event) *inter.EventHeaderData)

Reset resets buffers.

func (*Index) SetHighestBefore

func (vi *Index) SetHighestBefore(id hash.Event, seq HighestBeforeSeq, time HighestBeforeTime)

SetHighestBefore stores the vectors into DB

func (*Index) SetLowestAfter

func (vi *Index) SetLowestAfter(id hash.Event, seq LowestAfterSeq)

SetLowestAfter stores the vector into DB

type IndexCacheConfig

type IndexCacheConfig struct {
	ForklessCause     int `json:"forklessCause"`
	HighestBeforeSeq  int `json:"highestBeforeSeq"`
	HighestBeforeTime int `json:"highestBeforeTime"`
	LowestAfterSeq    int `json:"lowestAfterSeq"`
}

IndexCacheConfig - config for cache sizes of Index

type IndexConfig

type IndexConfig struct {
	Caches IndexCacheConfig `json:"cacheSizes"`
}

IndexConfig - Index config (cache sizes)

func DefaultIndexConfig

func DefaultIndexConfig() IndexConfig

DefaultIndexConfig return default index config for tests

type LowestAfterSeq

type LowestAfterSeq []byte

LowestAfterSeq is a vector of lowest events (their Seq) which do observe the source event

func NewLowestAfterSeq

func NewLowestAfterSeq(size int) LowestAfterSeq

NewLowestAfterSeq creates new LowestAfterSeq vector.

func (LowestAfterSeq) Get

func (b LowestAfterSeq) Get(i idx.Validator) idx.Event

Get i's position in the byte-encoded vector clock

func (*LowestAfterSeq) Set

func (b *LowestAfterSeq) Set(i idx.Validator, seq idx.Event)

Set i's position in the byte-encoded vector clock

func (LowestAfterSeq) Size

func (b LowestAfterSeq) Size() int

Size of the vector clock