cruisectl

package
v0.38.0-preview.0.0.9 Latest Latest
Warning

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

 Go to latest Published: Nov 27, 2024 License: AGPL-3.0 Imports: 12 Imported by: 0

README

Cruise Control: Automated Block Time Adjustment for Precise Epoch Switchover Timing

Overview

Context

Epochs have a fixed length, measured in views. The actual view rate of the network varies depending on network conditions, e.g. load, number of offline replicas, etc. We would like for consensus nodes to observe the actual view rate of the committee, and adjust how quickly they proceed through views accordingly, to target a desired weekly epoch switchover time.

High-Level Design

The BlockTimeController observes the current view rate and adjusts the timing when the proposal should be released. It is a PID controller. The essential idea is to take into account the current error, the rate of change of the error, and the cumulative error, when determining how much compensation to apply. The compensation function $u[v]$ has three terms:

  • $P[v]$ compensates proportionally to the magnitude of the instantaneous error
  • $I[v]$ compensates proportionally to the magnitude of the error and how long it has persisted
  • $D[v]$ compensates proportionally to the rate of change of the error

📚 This document uses ideas from:

Choice of Process Variable: Targeted Epoch Switchover Time

The process variable is the variable which:

  • has a target desired value, or setpoint ($SP$)
  • is successively measured by the controller to compute the error $e$

👉 The BlockTimeController controls the progression through views, such that the epoch switchover happens at the intended point in time. We define:

  • $\gamma = k\cdot \tau_0$ is the remaining epoch duration of a hypothetical ideal system, where all remaining $k$ views of the epoch progress with the ideal view time $\tau_0$.
  • The parameter $\tau_0$ is computed solely based on the Epoch configuration as $\tau_0 := \frac{<{\rm total\ epoch\ time}>}{<{\rm total\ views\ in\ epoch}>}$ (for mainnet 22, Epoch 75, we have $\tau_0 \simeq$ 1250ms).
  • $\Gamma$ is the actual time remaining until the desired epoch switchover.

The error, which the controller should drive towards zero, is defined as:

e := \gamma - \Gamma

From our definition it follows that:

  • $e > 0$ implies that the estimated epoch switchover (assuming ideal system behaviour) happens too late. Therefore, to hit the desired epoch switchover time, the time we spend in views has to be smaller than $\tau_0$.
  • For $e < 0$ means that we estimate the epoch switchover to be too early. Therefore, we should be slowing down and spend more than $\tau_0$ in the following views.

Reasoning:

The desired idealized system behaviour would a constant view duration $\tau_0$ throughout the entire epoch.

However, in the real-world system we have disturbances (varying message relay times, slow or offline nodes, etc) and measurement uncertainty (node can only observe its local view times, but not the committee’s collective swarm behaviour).

After a disturbance, we want the controller to drive the system back to a state, where it can closely follow the ideal behaviour from there on.

  • Simulations have shown that this approach produces very stable controller with the intended behaviour.

    Controller driving $e := \gamma - \Gamma \rightarrow 0$

    • setting the differential term $K_d=0$, the controller responds as expected with damped oscillatory behaviour to a singular strong disturbance. Setting $K_d=3$ suppresses oscillations and the controller's performance improves as it responds more effectively.

    • controller very quickly compensates for moderate disturbances and observational noise in a well-behaved system:

    • controller compensates massive anomaly (100s network partition) effectively:

    • controller effectively stabilizes system with continued larger disturbances (20% of offline consensus participants) and notable observational noise:

    References:

Detailed PID controller specification

Each consensus participant runs a local instance of the controller described below. Hence, all the quantities are based on the node’s local observation.

Definitions

Observables (quantities provided to the node or directly measurable by the node):

  • $v$ is the node’s current view
  • ideal view time $\tau_0$ is computed solely based on the Epoch configuration: $\tau_0 := \frac{<{\rm total\ epoch\ time}>}{<{\rm total\ views\ in\ epoch}>}$ (for mainnet 22, Epoch 75, we have $\tau_0 \simeq$ 1250ms).
  • $t[v]$ is the time the node entered view $v$
  • $F[v]$ is the final view of the current epoch
  • $T[v]$ is the target end time of the current epoch

Derived quantities

  • remaining views of the epoch $k[v] := F[v] +1 - v$
  • time remaining until the desired epoch switchover $\Gamma[v] := T[v]-t[v]$
  • error $e[v] := \underbrace{k\cdot\tau_0}_{\gamma[v]} - \Gamma[v] = t[v] + k[v] \cdot\tau_0 - T[v]$
Precise convention of View Timing

Upon observing block B with view $v$, the controller updates its internal state.

Note the '+1' term in the computation of the remaining views $k[v] := F[v] +1 - v$ . This is related to our convention that the epoch begins (happy path) when observing the first block of the epoch. Only by observing this block, the nodes transition to the first view of the epoch. Up to that point, the consensus replicas remain in the last view of the previous epoch, in the state of having processed the last block of the old epoch and voted for it (happy path). Replicas remain in this state until they see a confirmation of the view (either QC or TC for the last view of the previous epoch).

In accordance with this convention, observing the proposal for the last view of an epoch, marks the start of the last view. By observing the proposal, nodes enter the last view, verify the block, vote for it, the primary aggregates the votes, constructs the child (for first view of new epoch). The last view of the epoch ends, when the child proposal is published.

Controller

The goal of the controller is to drive the system towards an error of zero, i.e. $e[v] \rightarrow 0$. For a PID controller, the output $u$ for view $v$ has the form:

u[v] = K_p \cdot e[v]+K_i \cdot \mathcal{I}[v] + K_d \cdot \Delta[v]

With error terms (computed from observations)

  • $e[v]$ representing the instantaneous error as of view $v$ (commonly referred to as ‘proportional term’)
  • $\mathcal{I} [v] = \sum_v e[v]$ the sum of the errors (commonly referred to as ‘integral term’)
  • $\Delta[v]=e[v]-e[v-1]$ the rate of change of the error (commonly referred to as ‘derivative term’)

and controller parameters (values derived from controller tuning):

  • $K_p$ be the proportional coefficient
  • $K_i$ be the integral coefficient
  • $K_d$ be the derivative coefficient

Measuring view duration

Each consensus participant observes the error $e[v]$ based on its local view evolution. As the following figure illustrates, the view duration is highly variable on small time scales.

Therefore, we expect $e[v]$ to be very variable. Furthermore, note that a node uses its local view transition times as an estimator for the collective behaviour of the entire committee. Therefore, there is also observational noise obfuscating the underlying collective behaviour. Hence, we expect notable noise.

Managing noise

Noisy values for $e[v]$ also impact the derivative term $\Delta[v]$ and integral term $\mathcal{I}[v]$. This can impact the controller’s performance.

Managing noise in the proportional term

An established approach for managing noise in observables is to use exponentially weighted moving average [EWMA] instead of the instantaneous values. Specifically, let $\bar{e}[v]$ denote the EWMA of the instantaneous error, which is computed as follows:

\eqalign{
\textnormal{initialization: }\quad \bar{e} :&= 0 \\
\textnormal{update with instantaneous error\ } e[v]:\quad \bar{e}[v] &= \alpha \cdot e[v] + (1-\alpha)\cdot \bar{e}[v-1]
}

The parameter $\alpha$ relates to the averaging time window. Let $\alpha \equiv \frac{1}{N_\textnormal{ewma}}$ and consider that the input changes from $x_\textnormal{old}$ to $x_\textnormal{new}$ as a step function. Then $N_\textnormal{ewma}$ is the number of samples required to move the output average about 2/3 of the way from $x_\textnormal{old}$ to $x_\textnormal{new}$.

see also Python Ewma implementation

Managing noise in the integral term

In particular systematic observation bias are a problem, as it leads to a diverging integral term. The commonly adopted approach is to use a ‘leaky integrator’ [1, 2], which we denote as $\bar{\mathcal{I}}[v]$.

\eqalign{
\textnormal{initialization: }\quad \bar{\mathcal{I}} :&= 0 \\
\textnormal{update with instantaneous error\ } e[v]:\quad \bar{\mathcal{I}}[v] &= e[v] + (1-\lambda)\cdot\bar{\mathcal{I}}[v-1]
}

Intuitively, the loss factor $\lambda$ relates to the time window of the integrator. A factor of 0 means an infinite time horizon, while $\lambda =1$ makes the integrator only memorize the last input. Let $\lambda \equiv \frac{1}{N_\textnormal{itg}}$ and consider a constant input value $x$. Then $N_\textnormal{itg}$ relates to the number of past samples that the integrator remembers:

  • the integrators output will saturate at $x\cdot N_\textnormal{itg}$
  • an integrator initialized with 0, reaches 2/3 of the saturation value $x\cdot N_\textnormal{itg}$ after consuming $N_\textnormal{itg}$ inputs

see also Python LeakyIntegrator implementation

Managing noise in the derivative term

Similarly to the proportional term, we apply an EWMA to the differential term and denote the averaged value as $\bar{\Delta}[v]$:

\eqalign{
\textnormal{initialization: }\quad \bar{\Delta} :&= 0 \\
\textnormal{update with instantaneous error\ } e[v]:\quad \bar{\Delta}[v] &= \bar{e}[v] - \bar{e}[v-1]
}

Final formula for PID controller

We have used a statistical model of the view duration extracted from mainnet 22 (Epoch 75) and manually added disturbances and observational noise and systemic observational bias.

The following parameters have proven to generate stable controller behaviour over a large variety of network conditions:

👉 The controller is given by

u[v] = K_p \cdot \bar{e}[v]+K_i \cdot \bar{\mathcal{I}}[v] + K_d \cdot \bar{\Delta}[v]

with parameters:

  • $K_p = 2.0$
  • $K_i = 0.6$
  • $K_d = 3.0$
  • $N_\textnormal{ewma} = 5$, i.e. $\alpha = \frac{1}{N_\textnormal{ewma}} = 0.2$
  • $N_\textnormal{itg} = 50$, i.e. $\lambda = \frac{1}{N_\textnormal{itg}} = 0.02$

The controller output $u[v]$ represents the amount of time by which the controller wishes to deviate from the ideal view duration $\tau_0$. In other words, the duration of view $v$ that the controller wants to set is

\widehat{\tau}[v] = \tau_0 - u[v]
Limits of authority

[Latest update: Crescendo Upgrade, June 2024]

In general, there is no bound on the output of the controller output $u$. However, it is important to limit the controller’s influence to keep $u$ within a sensible range.

  • upper bound on view duration $\widehat{\tau}[v]$ that we allow the controller to set:

    The current timeout threshold is set to 1045ms and the largest view duration we want to allow the controller to set is $\tau_\textrm{max}$ = 910ms. Thereby, we have a buffer $\beta$ = 135ms remaining for message propagation and the replicas validating the proposal for view $v$.

    Note the subtle but important aspect: Primary for view $v$ controls duration of view $v-1$. This is because its proposal for view $v$ contains the proof (Quorum Certificate [QC]) that view $v-1$ concluded on the happy path. By observing the QC for view $v-1$, nodes enter the subsequent view $v$.

  • lower bound on the view duration:

    Let $t_\textnormal{p}[v]$ denote the time when the primary for view $v$ has constructed its block proposal. On the happy path, a replica concludes view $v-1$ and transitions to view $v$, when it observes the proposal for view $v$. The duration $t_\textnormal{p}[v] - t[v-1]$ is the time between the primary observing the parent block (view $v-1$), collecting votes, constructing a QC for view $v-1$, and subsequently its own proposal for view $v$. This duration is the minimally required time to execute the protocol. The controller can only delay broadcasting the block, but it cannot release the block before $t_\textnormal{p}[v]$ simply because the proposal isn’t ready any earlier.

👉 Let $\hat{t}[v]$ denote the time when the primary for view $v$ broadcasts its proposal. We assign:

\hat{t}[v] := \max\Big(t[v-1] +\min(\widehat{\tau}[v-1],\ \tau_\textrm{max}),\  t_\textnormal{p}[v]\Big)

This equation guarantees that the controller does not drive consensus into a timeout, as long as broadcasting the block and its validation together require less than time $\beta$. Currently, we have $\tau_\textrm{max}$ = 910ms as the upper bound for view durations that the controller can set. In comparison, for HotStuff's timeout threshold we set $\texttt{hotstuff-min-timeout} = \tau_\textrm{max} + \beta$, with $\beta$ = 135ms.

Further reading

Edge Cases

A node is catching up

When a node is catching up, it observes the blocks significantly later than they were published. In other words, from the perspective of the node catching up, the blocks are too late. However, as it reaches the most recent blocks, also the observed timing error approaches zero (assuming approximately correct block publication by the honest supermajority). Nevertheless, due to its biased error observations, the node catching up could still try to compensate for the network being behind, and publish its proposal as early as possible.

Assumption: With only a smaller fraction of nodes being offline or catching up, the effect is expected to be small and easily compensated for by the supermajority of online nodes.

A node has a misconfigured clock

Cap the maximum deviation from the default delay (limits the general impact of error introduced by the BlockTimeController). The node with misconfigured clock will contribute to the error in a limited way, but as long as the majority of nodes have an accurate clock, they will offset this error.

Assumption: With only a smaller fraction of nodes having misconfigured clocks, the effect will be small enough to be easily compensated for by the supermajority of correct nodes.

Near epoch boundaries

We might incorrectly compute high error in the target view rate, if local current view and current epoch are not exactly synchronized. By default, they would not be, because EpochTransition events occur upon finalization, and current view is updated as soon as QC/TC is available.

Solution: determine epoch locally based on view only, do not use EpochTransition event.

EFM

When the network is in EFM, epoch timing is anyway disrupted. The main thing we want to avoid is that the controller drives consensus into a timeout. This is largely guaranteed, due to the limits of authority. Beyond that, pretty much any block timing on the happy path is acceptable. Through, the optimal solution would be a consistent view time throughout normal Epochs as well as EFM.

Implementation Aspects

Timing Reference Points

  • Under the hood, the controller outputs the unconstrained view time $\widehat{\tau}[v]= \tau_0 - u[v]$ (of type time.Duration), which is wrapped into a happyPathBlockTime (👉 code). The happyPathBlockTime applies the limits of authority, and the resulting ConstrainedBlockTime we capture by the metric Average Target View Time (blue dotted curve in figure above).
  • From taking a look at the hotatuff.EventHandler, we can confirm that the BlockTimeController and the metric Observed View Time use practically the same reference time to determine view progression: 
    func (e *EventHandler) OnReceiveProposal(proposal *model.Proposal) error {
  ⋮

  // store the block.
  err := e.forks.AddValidatedBlock(block)
  if err != nil {
    return fmt.Errorf("cannot add proposal to forks (%x): %w", block.BlockID, err)
  }

  _, err = e.paceMaker.ProcessQC(proposal.Block.QC)
  if err != nil {
    return fmt.Errorf("could not process QC for block %x: %w", block.BlockID, err)
  }

  _, err = e.paceMaker.ProcessTC(proposal.LastViewTC)
  if err != nil {
    return fmt.Errorf("could not process TC for block %x: %w", block.BlockID, err)
  }

  ⋮
    • The call to forks.AddValidatedBlock emits the OnBlockIncorporated notification for block with view $v$, which the BlockTimeController uses as its starting point for the view: 
      TimedBlock{Block: block, TimeObserved: time.Now().UTC()}
      So for the BlockTimeController, the start of view v is the TimeObserved for proposal with view v.
    • Right after, the PaceMaker ingests the QC for view v-1, which is included in the proposal for view v. The call to paceMaker.ProcessQC updates the metric consensus_hotstuff_cur_view, based on which we calculate Observed Average (10m) View Time [s] (blue solid curve in figure above).
  • As the TargetPublicationTime for block v+1, the BlockTimeController calculates: 
    targetPublicationTime := TimeObserved.Add(ConstrainedBlockTime)
  • The EventHandler triggers the computation of the Block Publication Delay metric (dashed purple curve) right when it hands its proposal for view v+1 to the MessageHub 
    publicationDelay := time.Until(targetPublicationTime)
if publicationDelay < 0 {
  publicationDelay = 0 // Controller can only delay publication of proposal. Hence, the delay is lower-bounded by zero.
}
metrics.ProposalPublicationDelay(publicationDelay)
  • The MessageHub repeats exactly that computation of publicationDelay to determine how long it should sleep before broadcasting the proposal.

Estimator for consensus runtime:

  • The Observed Average View Time measurement starts when we see the parent block while Block Publication Delay starts to measure when the child block is constructed. Observed Average View Time and Block Publication Delay use nearly identical temporal reference points to stop their respective measurement (discrepancy is smaller than 1ms based on prior benchmarks of the EventHandler). Therefore, the following is an estimator for how long it takes for the protocol to complete one view on the happy path (running it fast as it possibly can without any delays): 
     \texttt{Observed Average View Time} - \texttt{Block Publication Delay}
  • There are some additional computation steps that we haven't accounted for, which could introduce errors. However, the EventHandler is very fast with execution times of single-digit milliseconds in practise. Hence, the uncertainty of this estimator is minimal (expected order of single milliseconds).

Controller's observation of blocks (OnBlockIncorporated) must approximately match the time when other replicas observe the proposal

On Testnet (devnet51) August 14-18, 2024 we observed the following discrepancy for a consensus committee of 7 nodes:

  • There was a significant discrepancy between the Observed Average View Time vs the Average Target View Time:
  • This resulted in the controller having reduced limits of authority: the limits of authority are computed based on the Target View Time, which the controller set to the largest permitted value of 910ms (higher values were not allowed to prevent the controller from driving consensus into timeouts). However, in reality the view progression was notably faster, meaning consensus would have tolerated larger delays without risk of timeouts.
Learning

This discrepancy between what the controller was setting vs the networks real-world response was due to a systematic observation bias:

  • For small consensus committee sizes, a node being selected as leader for successive rounds needs to be taken into account. In this scenario, it is especially important that the leader "observes its own proposal" approximately at the same time when the other replicas receive it.
  • Having the leader's cruise control "observes the own proposal" at the time when the proposal is constructed, before adding the controller's delay, would introduce a significant observation bias. In this case, only the leader would assume that the view has started much earlier compared to the other replicas. Therefore, it assumes it has much less time until other nodes would presumably trigger their timeout. Hence, the node erroneously restricts the possible delay it can impose before broadcasting the child block.
  • For larger consensus committee sizes, this systematic observation bias persists, but the probability of is much lower: The probability for a leader to be selected as leader decreases with $\frac{1}{n}$ for $n$ the committee size. As the bias only affects the second of the two consecutive views, the overall impact of this bias declines with increasing consensus committee size.

Initial Testing

see Cruise Control: Benchnet Testing Notes

Documentation

Overview

Package cruisectl implements a "cruise control" system for Flow by adjusting nodes' latest ProposalTiming in response to changes in the measured view rate and target epoch switchover time.

It uses a PID controller with the projected epoch switchover time as the process variable and the set-point computed using epoch length config. The error is the difference between the projected epoch switchover time, assuming an ideal view time τ, and the target epoch switchover time (based on a schedule).

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BlockTimeController 

type BlockTimeController struct {
	component.Component
	// protocol.Consumer consumes protocol state events
	protocol.Consumer
	// contains filtered or unexported fields
}

BlockTimeController dynamically adjusts the ProposalTiming of this node, based on the measured view rate of the consensus committee as a whole, in order to achieve a desired switchover time for each epoch. In a nutshell, the controller outputs the block time on the happy path, i.e.

  • Suppose the node is observing the parent block B0 at some time `x0`.
  • The controller determines the duration `d` of how much later the child block B1 should be observed by the committee.
  • The controller internally memorizes the latest B0 it has seen and outputs the tuple `(B0, x0, d)`

This low-level controller output `(B0, x0, d)` is wrapped into a `ProposalTiming` interface, specifically `happyPathBlockTime` on the happy path. The purpose of the `ProposalTiming` wrapper is to translate the raw controller output into a form that is useful for the EventHandler. Edge cases, such as initialization or epoch fallback are implemented by other implementations of `ProposalTiming`.

func NewBlockTimeController 

func NewBlockTimeController(log zerolog.Logger, metrics module.CruiseCtlMetrics, config *Config, state protocol.State, curView uint64) (*BlockTimeController, error)

NewBlockTimeController returns a new BlockTimeController.

func (*BlockTimeController) EpochCommittedPhaseStarted added in v0.37.1 

func (ctl *BlockTimeController) EpochCommittedPhaseStarted(_ uint64, first *flow.Header)

EpochCommittedPhaseStarted ingests the respective protocol notifications. The notification is queued for async processing by the worker. We must process _all_ `EpochCommittedPhaseStarted` notifications.

func (*BlockTimeController) EpochExtended added in v0.37.1 

func (ctl *BlockTimeController) EpochExtended(_ uint64, first *flow.Header, _ flow.EpochExtension)

EpochExtended listens to `EpochExtended` protocol notifications. The notification is queued for async processing by the worker. We must process _all_ `EpochExtended` notifications.

func (*BlockTimeController) OnBlockIncorporated 

func (ctl *BlockTimeController) OnBlockIncorporated(block *model.Block)

OnBlockIncorporated listens to notification from HotStuff about incorporating new blocks. The event is queued for async processing by the worker. If the channel is full, the event is discarded - since we are taking an average it doesn't matter if we occasionally miss a sample.

func (*BlockTimeController) TargetPublicationTime 

func (ctl *BlockTimeController) TargetPublicationTime(proposalView uint64, timeViewEntered time.Time, parentBlockId flow.Identifier) time.Time

TargetPublicationTime is intended to be called by the EventHandler, whenever it wants to publish a new proposal. The event handler inputs

  • proposalView: the view it is proposing for,
  • timeViewEntered: the time when the EventHandler entered this view
  • parentBlockId: the ID of the parent block, which the EventHandler is building on

TargetPublicationTime returns the time stamp when the new proposal should be broadcasted. For a given view where we are the primary, suppose the actual time we are done building our proposal is P:

  • if P < TargetPublicationTime(..), then the EventHandler should wait until `TargetPublicationTime` to broadcast the proposal
  • if P >= TargetPublicationTime(..), then the EventHandler should immediately broadcast the proposal

Note: Technically, our metrics capture the publication delay relative to this function's _latest_ call. Currently, the EventHandler is the only caller of this function, and only calls it once per proposal.

Concurrency safe.

type Config 

type Config struct {
	TimingConfig
	ControllerParams
}

Config defines configuration for the BlockTimeController.

func DefaultConfig 

func DefaultConfig() *Config

DefaultConfig returns the default config for the BlockTimeController.

type ControllerParams 

type ControllerParams struct {
	// N_ewma defines how historical measurements are incorporated into the EWMA for the proportional error term.
	// Intuition: Suppose the input changes from x to y instantaneously:
	//  - N_ewma is the number of samples required to move the EWMA output about 2/3 of the way from x to y
	// Per convention, this must be a _positive_ integer.
	N_ewma uint

	// N_itg defines how historical measurements are incorporated into the integral error term.
	// Intuition: For a constant error x:
	//  - the integrator value will saturate at `x•N_itg`
	//  - an integrator initialized at 0 reaches 2/3 of the saturation value after N_itg samples
	// Per convention, this must be a _positive_ integer.
	N_itg uint

	// KP, KI, KD, are the coefficients to the PID controller and define its response.
	// KP adjusts the proportional term (responds to the magnitude of error).
	// KI adjusts the integral term (responds to the error sum over a recent time interval).
	// KD adjusts the derivative term (responds to the rate of change, i.e. time derivative, of the error).
	KP, KI, KD float64
}

ControllerParams specifies the BlockTimeController's internal parameters.

type Ewma 

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

Ewma implements the exponentially weighted moving average with smoothing factor α. The Ewma is a filter commonly applied to time-discrete signals. Mathematically, it is represented by the recursive update formula 

value ← α·v + (1-α)·value

where `v` the next observation. Intuitively, the loss factor `α` relates to the time window of N observations that we average over. For example, let α ≡ 1/N and consider an input that suddenly changes from x to y as a step function. Then N is _roughly_ the number of samples required to move the output average about 2/3 of the way from x to y. For numeric stability, we require α to satisfy 0 < a < 1. Not concurrency safe.

func NewEwma 

func NewEwma(alpha, initialValue float64) (Ewma, error)

NewEwma instantiates a new exponentially weighted moving average. The smoothing factor `alpha` relates to the averaging time window. Let `alpha` ≡ 1/N and consider an input that suddenly changes from x to y as a step function. Then N is roughly the number of samples required to move the output average about 2/3 of the way from x to y. For numeric stability, we require `alpha` to satisfy 0 < `alpha` < 1.

func (*Ewma) AddObservation 

func (e *Ewma) AddObservation(v float64) float64

AddObservation adds the value `v` to the EWMA. Returns the updated value.

func (*Ewma) AddRepeatedObservation 

func (e *Ewma) AddRepeatedObservation(v float64, k int) float64

AddRepeatedObservation adds k consecutive observations with the same value v. Returns the updated value.

func (*Ewma) Value 

func (e *Ewma) Value() float64

type LeakyIntegrator 

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

LeakyIntegrator is a filter commonly applied to time-discrete signals. Intuitively, it sums values over a limited time window. This implementation is parameterized by the loss factor `ß`: 

value ← v + (1-ß)·value

where `v` the next observation. Intuitively, the loss factor `ß` relates to the time window of N observations that we integrate over. For example, let ß ≡ 1/N and consider a constant input x:

  • the integrator value will saturate at x·N
  • an integrator initialized at 0 reaches 2/3 of the saturation value after N samples

For numeric stability, we require ß to satisfy 0 < ß < 1. Further details on Leaky Integrator: https://www.music.mcgill.ca/~gary/307/week2/node4.html Not concurrency safe.

func NewLeakyIntegrator 

func NewLeakyIntegrator(beta, initialValue float64) (LeakyIntegrator, error)

NewLeakyIntegrator instantiates a new leaky integrator with loss factor `beta`, where `beta relates to window of N observations that we integrate over. For example, let `beta` ≡ 1/N and consider a constant input x. The integrator value will saturate at x·N. An integrator initialized at 0 reaches 2/3 of the saturation value after N samples. For numeric stability, we require `beta` to satisfy 0 < `beta` < 1.

func (*LeakyIntegrator) AddObservation 

func (e *LeakyIntegrator) AddObservation(v float64) float64

AddObservation adds the value `v` to the LeakyIntegrator. Returns the updated value.

func (*LeakyIntegrator) AddRepeatedObservation 

func (e *LeakyIntegrator) AddRepeatedObservation(v float64, k int) float64

AddRepeatedObservation adds k consecutive observations with the same value v. Returns the updated value.

func (*LeakyIntegrator) Value 

func (e *LeakyIntegrator) Value() float64

type ProposalTiming 

type ProposalTiming interface {
	hotstuff.ProposalDurationProvider

	// ObservationView returns the view of the observation that the controller
	// processed and generated this ProposalTiming instance in response.
	ObservationView() uint64

	// ObservationTime returns the time, when the controller received the
	// leading to the generation of this ProposalTiming instance.
	ObservationTime() time.Time
}

ProposalTiming encapsulates the output of the BlockTimeController. On the happy path, the controller observes a block and generates a specific ProposalTiming in response. For the happy path, the ProposalTiming describes when the child proposal should be broadcast. However, observations other than blocks might also be used to instantiate ProposalTiming objects, e.g. controller instantiation, a disabled controller, etc. The purpose of ProposalTiming is to convert the controller output to timing information that the EventHandler understands. By convention, ProposalTiming should be treated as immutable.

type TimedBlock 

type TimedBlock struct {
	Block        *model.Block
	TimeObserved time.Time // timestamp when BlockTimeController received the block, per convention in UTC
}

TimedBlock represents a block, with a timestamp recording when the BlockTimeController received the block

type TimingConfig 

type TimingConfig struct {
	// FallbackProposalDelay is the minimal block construction delay. When used, it behaves like the
	// old command line flag `block-rate-delay`. Specifically, the primary measures the duration from
	// starting to construct its proposal to the proposal being ready to be published. If this
	// duration is _less_ than FallbackProposalDelay, the primary delays broadcasting its proposal
	// by the remainder needed to reach `FallbackProposalDelay`
	// It is used:
	//  - when Enabled is false
	//  - when epoch fallback has been triggered
	FallbackProposalDelay *atomic.Duration

	// MaxViewDuration is a hard maximum on the total view time targeted by ProposalTiming.
	// If the BlockTimeController computes a larger desired ProposalTiming value
	// based on the observed error and tuning, this value will be used instead.
	MaxViewDuration *atomic.Duration

	// MinViewDuration  is a hard maximum on the total view time targeted by ProposalTiming.
	// If the BlockTimeController computes a smaller desired ProposalTiming value
	// based on the observed error and tuning, this value will be used instead.
	MinViewDuration *atomic.Duration

	// Enabled defines whether responsive control of the GetProposalTiming is enabled.
	// When disabled, the FallbackProposalDelay is used.
	Enabled *atomic.Bool
}

TimingConfig specifies the BlockTimeController's limits of authority.

func (TimingConfig) GetEnabled 

func (ctl TimingConfig) GetEnabled() bool

GetEnabled returns whether the controller is enabled.

func (TimingConfig) GetFallbackProposalDuration 

func (ctl TimingConfig) GetFallbackProposalDuration() time.Duration

GetFallbackProposalDuration returns the proposal duration used when Cruise Control is not active.

func (TimingConfig) GetMaxViewDuration 

func (ctl TimingConfig) GetMaxViewDuration() time.Duration

GetMaxViewDuration returns the max view duration returned by the controller.

func (TimingConfig) GetMinViewDuration 

func (ctl TimingConfig) GetMinViewDuration() time.Duration

GetMinViewDuration returns the min view duration returned by the controller.

func (TimingConfig) SetEnabled 

func (ctl TimingConfig) SetEnabled(enabled bool) error

SetEnabled sets whether the controller is enabled.

func (TimingConfig) SetFallbackProposalDuration 

func (ctl TimingConfig) SetFallbackProposalDuration(dur time.Duration) error

SetFallbackProposalDuration sets the proposal duration used when Cruise Control is not active.

func (TimingConfig) SetMaxViewDuration 

func (ctl TimingConfig) SetMaxViewDuration(dur time.Duration) error

SetMaxViewDuration sets the max view duration returned by the controller.

func (TimingConfig) SetMinViewDuration 

func (ctl TimingConfig) SetMinViewDuration(dur time.Duration) error

SetMinViewDuration sets the min view duration returned by the controller.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.