Skip to content

Instantly share code, notes, and snippets.

@ilap

ilap/The_Hitchhikers_Guide_To_The_Shelley_Chapter_One.md

Last active July 4, 2021 18:04
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save ilap/af8282ff5f81ee5f763fc9994e36b526 to your computer and use it in GitHub Desktop.
Save ilap/af8282ff5f81ee5f763fc9994e36b526 to your computer and use it in GitHub Desktop.
Download ZIP
The Hitchhikers Guide To The Shelley - Chapter 1 - The Network
Raw
The_Hitchhikers_Guide_To_The_Shelley_Chapter_One.md

The Hitchhikers Guide To The Shelley - Chapter 1 - The Network

This chapters covers the information about the underlying P2P network of Shelley's ITN implemented in Jormungandr.

The Explanation

The very simple explanation of the poldercast network relating to jormungandr.

  • Poldercast is a Topic Based Pub/Sub System.
  • Jormungandr has two topics the Blocks and Messages with low, normal and high priority.
  • The nodes can be subscribers (receive topic messages) and publishers (send topic messages).
  • Pools (active nodes) are Blocks (i.e. block created by that node) publishers,
    • However every node can be Messages topic publisher (i.e. sending transaction to the network).
    • but, only pools can be Blocks publishers.
  • Full-node wallets (Daedalus, cardano-wallet-jormungandr) are Messages (i.e. transaction) publishers.
  • Every nodes are susbscribers of both topics, which means they receive topic messages (from both topics) sent by publishers.
  • Block announcements, are (Blocks) topic messages sent by scheduled leader's node to all subscribers,
    • i.e. to all nodes to the Blocks topic ring (explanation later),
    • and they prefer pools to send, as usualy they have set the high priority for both topics in the node's config file.
  • Transactions are also topic messages (Messages topic) that are usually sent by wallets to every nodes.
    • i.e. to nodes that are in the Message topic ring,
  • Both rings ( Blocks topic ring Message topic ring) in jormungandr should be the same and should include all nodes are joined to the network,
    • because, every nodes in the jormungandr network are subsrcibed to every topics.
    • That's not really the case, as I can see a very few nodes that are not subscribed to anything, probably they commented out the topics_of_interest stanza in the config file.
  • The gossip is just a fixed-list of random nodes and their details to send to a recipient to exchange with the sender to update the view of the overlay (toppology) of the sender and the recipient.
  • overlay is the node's view of the P2P topology, represented as a list of node profiles (node_profile contains address, id, node's subscription etc.) of the particular node.

The Rings

Every nodes that are joined to the Jormungandr network maintain as many views (Rings view) of the network as as many topics they're subscribed to.

These views (Rings view) are a form of rings (Topic rings) and each of the rings connects all nodes that are subscribed to that topic (and just only them). The nodes in the rings are linked to an other based on the sorted node_ids.

These rings form a single, connected ring called overlay (topology).

In jormungandr, all nodes are subscribed to the both topics, therefore each of them maintain 2 per-topic rings, and therefore the jormungandr overlay is built from these 2 topic rings (and from other nodes that are joined to the network), see an example below.

Note: In simple words: The jormungandr overlay, is a node_id (as sorted by node_ids) based circular linked list that contains all of the nodes that are joined to the network.

Ring

This overlay contains two rings (it's like a horizontal overlay) the overlay rings (rings that are layered on top of another ring, so like a vertical overlay, explanation later), the Blocks and Messages overlay rings.

Overlay building

Building overlay relies on three modules that maintain thier own view of the network, managed by separate gossiping protocol (one per each module), which gossips periodically, asyncrhonously and independently:

  • Rings (discovers the node's successor and precedessor, i.e. direct ring links, of a topic),
  • Vicinity (provide a few arbitrary neighbors, i.e. arbitrary links, to Ring module for all node's topics) and
    • so, it finds the node's closest neighbors out of the whole network. In jormungandr it's the whole network
    • the neighbours ranked by the nr. of the shared topics and the topics priority, in jormungandr:
      • pools have "high/high"
      • relay/passive nodes "normal/normal"
      • edge/wallet nodes "low/normal"
  • Cyclon (peer sampling using some uniform random links)
    • Keeps the whole set of subscribers connected to single partition in churn, large-scale failures or susbscription changes.
    • Source of links selected uniformly at random from the whole network (overlay).

Brief responsibility of the modules:

  • Rings: Maintaining the (topic) rings
  • Vicinity: collecting nodes with similar interests for
    • a. feedings the Ring layer to build and maintain the induced ring per topic
    • b. acting as a pool for random shortcuts between the nodes with similar interests.
  • Cyclon: keeping the overlay connected and providing purely random shortcuts.

Therefore, each nodes in the network maintains a view of each of the module's

  • neighbours and
  • periodically gossips /w them to discover nodes (closer proximity).

Note: the three gossiping protocols are executed continuously, due to nodes departing or joining, crashing at any time (even changing thir subscription) there is no notion of final convergence. Instead, nodes engage in a constant convergence process. In jomrungandr, it's 10seconds.

Also, each modules maintains its

  • view size (number of neighbours maintained, default=20) and
  • gossip size (maximum number of neighbours included in a gossip message, default=10).

Rings in brief

Imagine a very big ring /w thousand of nodes. Every node has two links, one to the next (successor) and one to the previous (precedessor) nodes. And they, just communicate to these two their direct neighbours in this layer. It's similar to the old IBM Token Ring (802.5), but the main differences is that Poldercast Rings' communication is bidirectional.

Note: It's a bit more complex, but I do not want to deep dive in now, for the sake of simplicity.

Vicinity in Brief

It is collecting the nodes with similar interests for

  1. feedings the Ring layer to build and maintain the induced ring per topic
  2. acting as a pool for random shortcuts between the nodes with similar interests.

Imagine the above ring in Rings. Vicinity collects all the nodes that are interested in the specific topic e.g. in Blocks, and passing to the Ring to build it's Ring view and creating links between some random nodes that are not direct neighbours.

Cyclon in Brief

As the above topic ring as an example, it maintains the connections between nodes and providing random links (shortcuts) to these arbitrary nodes.

The Details

Rings detailed

Rings's module responsibility is to discover the node's successor and precedessor of the topic t, by initially considering few existing random links to arbitrary subsrciber nodes, and periodically gossipping with them for the gradually closer t topic's subscriber ids.

The Rings module manages the ring links and tries discovering a node’s successor and predecessor for each topic in its subscription, and at quickly adapting to new successors/predecessors in dynamic networks.

So, each node maintains their ring neighbors for each topic in its subscription (ring/2 with lower and ring/2 with higher id, default=4, i.e. 2 of each) and periodically picks a node for gossipin from its Rings view. The picks based on LRU selection policy, that plays an important role in churn handling.

Then the two nodes exchange up to gossip size (10) neighbors to help each other improve their Rings views.

For example how it, probably, works in jormunganrd:

  1. p node randomly selects its q neighbour from its current Rings view.
  2. p merges its view from all 3 modules
  • collecting all q's subscribers of both the Block and Messages topics in all 3 modules
  • p creates a union view of all 3 modules
  • p shorts them bey node_id and for each topic in common in q
  • p selects view size / 2 lower ids and same number of higher ids that q's id.
  • if 'view size > gossip size' the it randomly selects gossip size / 2 nodes from each of both list.
  1. it sends these nodes' profiles to q.
  2. q do the same.

Ideally, they should just need two links, the direct ring links (precedessor's and successors), but this above helps to pick up some fail-safe ring link on sucessors/precedessors failure and/or churn and also have.

Vicinity module

Vicinity module is responsible for feeding the Rings module with the a few neighbours (for each topic) of arbitrary ids. This feeding mechanism is based on some proximity function that are trying to discover each node's closest other nodes. This proximity function is based on the rank i.e. number of topics that two nodes share.

In other words, it's responsible fro maintaining interest-induced random links between nodes that share at least 1 topic and propagated events to arbitrary subscribers of a topic.

This links are the input to the Ring module.

For example how it, probably, works in jormunganrd:

  1. Similar to Ring's modules point 1.
  2. Similar to Ring's modules point 2., but the details are different
  • it selects vicinity's gossip size number of nodes closest to q, by applying a proximity function
  • it sends these nodes' profiles to q.
  1. q do the same.

Cyclon module

Is a lightweight peer sampling service, providing each node with a continuous stream of neighbours chosen uniformly at random from the whole network, whihc is essential for keeping the whole overlay connected while enabling flexible overlay maintenance in failures and node churn.

Appendixes

References

Definitions

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment