macula_hyparview_view (macula v11.4.0)

View Source

HyParView active + passive partial-view data structure (Leitão, Pereira, Rodrigues 2007 — implementation of Part 3 §7.1).

Each realm member holds two bounded views of other members:

  • Active view — symmetric, TCP-like. Default cap 5 (per Part 3 §7.1: max(5, ceil(log₂(N))) capped at 15). Plumtree gossip eager-pushes along active-view edges.
  • Passive view — candidate pool. Default cap is 4 × active. Promoted into the active view on active-peer failure; refreshed via periodic shuffles with active neighbours.

This module is pure. Mutating ops return a new view; the wire-protocol orchestration (JOIN / FORWARD_JOIN / NEIGHBOR / SHUFFLE / SHUFFLE_REPLY) lands in Session 5.2 on top of this.

Eviction policy

Whenever a add_active/2 or promote/2 would push the active view past active_cap, a uniformly-random current active peer is demoted to the passive view to make room. Symmetric removal on the other side is the protocol layer's responsibility.

Whenever add_passive/2 or merge_shuffle/2 would push the passive view past passive_cap, a uniformly-random current passive peer is dropped to make room.

Reference: plans/PLAN_MACULA_V2_PART3_DISCOVERY.md §7.1; plans/PLAN_PHASE_5_BREAKDOWN.md Session 5.1.

Summary

Types

counts/0
eligibility/0
opts/0
peer/0
view/0

Functions

active(_)
active_cap(_)
active_size(_)
add_active(V, Peer)
add_passive(V, Peer)
counts(_)
demote(V, Peer)

Move a peer from active to passive (e.g. on graceful peer disconnect that should be retained as a candidate).

is_active(Peer, _)
is_passive(Peer, _)
merge_shuffle(V, Peers)
new(Self)
new(Self, Opts)
passive(_)
passive_cap(_)
passive_size(_)
place_passive(V, From, Peers, Now)

Place the node_ids new to the view that a frame from From brings, as far as that neighbour's allowance goes at Now. exceeded when some were left out.

promote(V, Peer)

Move a peer from passive to active. The peer must already be in the passive view; otherwise this is equivalent to add_active/2.

random_active(_)
random_active_subset(_, K)
random_passive_subset(_, K)
record_shuffle(V, Now)

Record that this node sent a SHUFFLE at Now.

remove_active(V, Peer)
remove_passive(V, Peer)
self_id(_)
take_shuffle_record(V, Now)

Take the record of the oldest SHUFFLE sent in the 30 seconds before Now that has no reply yet, forgetting older ones. none when there is no such SHUFFLE.

Types

counts/0

-type counts() :: #{active := non_neg_integer(), passive := non_neg_integer()}.

eligibility/0

-type eligibility() :: self | already_active | was_passive | fresh.

opts/0

-type opts() :: #{active_cap => pos_integer(), passive_cap => pos_integer()}.

peer/0

-type peer() :: <<_:256>>.

view/0

-type view() ::
          #{self_id := peer(),
            active_cap := pos_integer(),
            passive_cap := pos_integer(),
            active := sets:set(peer()),
            passive := sets:set(peer()),
            placements := #{peer() => {non_neg_integer(), integer()}},
            shuffles_sent := [integer()]}.

Functions

active(_)

active_cap(_)

active_size(_)

add_active(V, Peer)

-spec add_active(view(), peer()) -> view().

add_passive(V, Peer)

-spec add_passive(view(), peer()) -> view().

counts(_)

demote(V, Peer)

-spec demote(view(), peer()) -> view().

Move a peer from active to passive (e.g. on graceful peer disconnect that should be retained as a candidate).

is_active(Peer, _)

is_passive(Peer, _)

merge_shuffle(V, Peers)

-spec merge_shuffle(view(), [peer()]) -> view().

new(Self)

-spec new(peer()) -> view().

new(Self, Opts)

-spec new(peer(), opts()) -> view().

passive(_)

passive_cap(_)

passive_size(_)

place_passive(V, From, Peers, Now)

-spec place_passive(view(), peer(), [peer()], integer()) -> {view(), within | exceeded}.

Place the node_ids new to the view that a frame from From brings, as far as that neighbour's allowance goes at Now. exceeded when some were left out.

promote(V, Peer)

-spec promote(view(), peer()) -> view().

Move a peer from passive to active. The peer must already be in the passive view; otherwise this is equivalent to add_active/2.

random_active(_)

-spec random_active(view()) -> {ok, peer()} | empty.

random_active_subset(_, K)

-spec random_active_subset(view(), non_neg_integer()) -> [peer()].

random_passive_subset(_, K)

-spec random_passive_subset(view(), non_neg_integer()) -> [peer()].

record_shuffle(V, Now)

-spec record_shuffle(view(), integer()) -> view().

Record that this node sent a SHUFFLE at Now.

remove_active(V, Peer)

-spec remove_active(view(), peer()) -> view().

remove_passive(V, Peer)

-spec remove_passive(view(), peer()) -> view().

self_id(_)

take_shuffle_record(V, Now)

-spec take_shuffle_record(view(), integer()) -> {ok | none, view()}.

Take the record of the oldest SHUFFLE sent in the 30 seconds before Now that has no reply yet, forgetting older ones. none when there is no such SHUFFLE.