paxos

type Accept ¶

type Accept struct {
	ID   grp.ID
	Slot SlotID
	Rnd  ProposerRound
	Val  Value
}

type Acceptor ¶

type Acceptor interface {
	Actor
	GetState(afterSlot SlotID, release <-chan bool) *AcceptorSlotMap
	GetMaxSlot(release <-chan bool) *AcceptorSlotMap
	SetState(slotmap *AcceptorSlotMap)
	SetLowSlot(slot SlotID)
}

The interface an Acceptor must fulfill.

type AcceptorSlot ¶

type AcceptorSlot struct {
	ID   SlotID
	VRnd ProposerRound // The highest proposal number in which we have casted a vote
	VVal Value         // The value voted for with proposal number vrnd
}

In MultiPaxos we need to maintain multiple instances of Paxos. We call each of these instances a slot. In this case, this AcceptorSlot contains the slot state that is used by an Acceptor.

type AcceptorSlotMap ¶

type AcceptorSlotMap struct {
	Slots   map[SlotID]*AcceptorSlot
	Rnd     ProposerRound // The highest proposal number in which we have participated
	MaxSeen SlotID
}

An AcceptorSlotMap allows easy maintenance of slots. It contains a map from SlotId to an AcceptorSlot, as well as the highest accessed SlotId.

func CopyAccSlotMapRange(afterSlotID SlotID, sourceSlotMap *AcceptorSlotMap) *AcceptorSlotMap

func NewAcceptorSlotMap() *AcceptorSlotMap

func (sm *AcceptorSlotMap) GetSlot(id SlotID) *AcceptorSlot

type Actor ¶

type Actor interface {
	Start()
	Stop()
}

A Paxos actor implements Start() and Stop() methods. Maybe this could be generalized as an interface for a Module which we Start() and Stop() in the server module.

type Adu ¶

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

func NewAdu(sid SlotID) *Adu

func (a *Adu) Increment()

func (a *Adu) String() string

func (a *Adu) Value() SlotID

type CatchUpRequest ¶

type CatchUpRequest struct {
	ID     grp.ID
	Ranges []RangeTuple
}

type CatchUpResponse ¶

type CatchUpResponse struct {
	ID   grp.ID
	Vals []ResponseTuple
}

type Learn ¶

type Learn struct {
	ID          grp.ID
	Slot        SlotID
	Rnd         ProposerRound
	Val         Value
	EpochVector []grp.Epoch
}

type Learner ¶

type Learner interface {
	Actor
}

The interface a Learner must fulfill.

type LearnerLrSlot ¶

type LearnerLrSlot struct {
	ID         SlotID
	Learned    bool
	Rnd        ProposerRound
	Learns     []*Learn
	Votes      uint
	Voted      map[grp.ID]bool
	LearnedVal Value
	Decided    bool
	CheckVQ    bool
}

The state that a LrLearner needs to maintain for every Slot.

type LearnerLrSlotMap ¶

type LearnerLrSlotMap struct {
	Slots   map[SlotID]*LearnerLrSlot
	MaxSeen SlotID
}

A LearnerSlotMap allows easy access to the slots of a Learner.

func NewLearnerLrSlotMap() *LearnerLrSlotMap

func (llrsm *LearnerLrSlotMap) GetSlot(id SlotID) *LearnerLrSlot

type LearnerSlot ¶

type LearnerSlot struct {
	ID         SlotID
	Learned    bool
	Rnd        ProposerRound
	Learns     []*Learn
	Votes      uint
	LearnedVal Value
	Decided    bool
}

The state that a Learner needs to maintain for every Slot.

type LearnerSlotMap ¶

type LearnerSlotMap struct {
	Slots   map[SlotID]*LearnerSlot
	MaxSeen SlotID
}

A LearnerSlotMap allows easy access to the slots of a Learner.

func NewLearnerSlotMap() *LearnerSlotMap

func (llrsm *LearnerSlotMap) GetSlot(id SlotID) *LearnerSlot

type Pack ¶

type Pack struct {
	ID          grp.ID
	Gm          grp.GroupManager
	StopCheckIn *sync.WaitGroup

	Config        *config.Config
	NrOfNodes     uint
	NrOfAcceptors uint

	RunProp bool
	RunAcc  bool
	RunLrn  bool

	Dmx net.Demuxer
	Ld  liveness.LeaderDetector

	Ucast  chan<- net.Packet
	Bcast  chan<- interface{}
	BcastP chan<- interface{}
	BcastA chan<- interface{}
	BcastL chan<- interface{}

	PropChan        <-chan *Value // Proposal values
	DcdChan         chan<- *Value // Decided values
	NewDcdChan      chan bool
	DcdSlotIDToProp chan SlotID

	LocalAdu        *Adu
	FirstSlot       SlotID
	NextExpectedDcd SlotID
}

A Pack is used during the construction of the Paxos actors. This Pack is passed to each of the actor constructors upon instantiation. The actors can then pull the information they need from this pack to function.

For example, each actor will need to pull the Bcast and Ucast channels from this pack and store them locally so that they can send messages to the other replicas:

func NewMultiProposer(pp px.Pack) *MultiProposer {
  return &MultiProposer{
    ...
    ucast:          pp.Ucast,
    bcast:          pp.Bcast,
    ...
  }
}

type Prepare ¶

type Prepare struct {
	ID   grp.ID
	CRnd ProposerRound
	Slot SlotID
}

type Promise ¶

type Promise struct {
	ID          grp.ID
	Rnd         ProposerRound
	AccSlots    []AcceptorSlot
	EpochVector []grp.Epoch
}

type Proposer ¶

type Proposer interface {
	Actor
	SetNextSlot(ns SlotID)
}

The interface a Proposer must fulfill, also includes the base PaxosActor methods.

type ProposerRound ¶

type ProposerRound struct {
	Rnd uint
	ID  grp.ID
}

A ProposerRound, which is guaranteed to be unique among all the Proposers due to the fact that it is based on the Proposer's Id as well as the round number.

func NewProposerRound(id grp.ID) *ProposerRound

func (pr *ProposerRound) Compare(opr ProposerRound) int

func (pr *ProposerRound) Next()

func (pr *ProposerRound) SetOwner(id grp.ID)

type ProposerSlot ¶

type ProposerSlot struct {
	ID        SlotID
	Proposal  *Accept
	SentCount uint8
}

The state that a Proposer needs to maintain for every Slot.

type ProposerSlotMap ¶

type ProposerSlotMap struct {
	Slots   map[SlotID]*ProposerSlot
	MaxSeen SlotID
}

A PropserSlotMap allows easy access to the slots of a Proposer.

func NewProposerSlotMap() *ProposerSlotMap

func (sm *ProposerSlotMap) GetSlot(id SlotID) *ProposerSlot

type RangeTuple ¶

type RangeTuple struct {
	From SlotID
	To   SlotID
}

type ReconfigCmd ¶

type ReconfigCmd struct {
	Nodes map[grp.ID]grp.Node
	New   grp.ID
}

For now only allowing replacement through reconfiguration. Nodes is the new NodeMap to be used. New is the id of the replaced node in the node map. Should be expanded to allow different types of reconfiguration commands: add, remove, replace etc.

type ResponseTuple ¶

type ResponseTuple struct {
	Slot SlotID
	Val  Value
}

type SlotID ¶

type SlotID uint

type Value ¶

type Value struct {
	Vt ValueType
	Cr []*client.Request
	Rc *ReconfigCmd
}

func (v *Value) Equal(o Value) bool

func (v *Value) Hash() uint32

type ValueType ¶

type ValueType int

const (
	Noop ValueType = iota
	App
	Reconfig
)

func (vt ValueType) String() string