topology

README

Topology

Definitions

In Flow, the term topology captures the distributed protocol by which a node determines its fanout set. The fanout set of a node is a subset of other nodes in the system with whom the node interacts in the event of epidemic dissemination of information. The epidemic dissemination happens when a node multicasts or broadcasts a message. The former refers to the event when a node sends a message targeted for a subgroup of nodes in the system, while the latter refers to the event when a node aims at sending a message to the entire system. (Topology algorithms are not used for direct one-to-one communication). Note that the communications over the fanout set are assumed unidirectional from the node to its fanout set. The distributed and independent invocations of topology protocol on nodes of Flow hence results in a directed graph where the vertices are the Flow nodes, and the edges are the union of the fanout sets of the nodes. This directed graph is called the topology graph. It is required that the topology graph is connected with a very high probability, where the probability is taken over the number of times the topology is constructed. The topology is constructed once at the beginning of each epoch. Hence, it implies that the topology construction protocol should result in a connected graph with a very high probability over the life-time of Flow, which theoretically is infinitely-many epochs. In practice, we consider it as 2^30 many epochs.

The figure below shows an example of a topology graph with 7 nodes in the Flow network, which is a directed and connected graph. There is a path between every two nodes and traversing the topology graph with BFS or DFS visits all the vertices. Also, the fanout set of each node is colored the same as the node itself, e.g., the fanout set of the red node is illustrated using red edges from it to other nodes of the network. Also, in this example, every node has a fanout size of 3.

Topology Interface

The Topology interface provides a way to retrieve a topology for a node. It receives the approved list of nodes in the system and generates and returns the fanout of the node. The current implementations of this topology interface are topic-based topology and randomized topology. Any future topology implementation must also implement this interface to be able to be plugged into the node.

TopicBasedTopology

The topic-based topology breaks the communication space of Flow into topics, where each topic corresponds to a single channel. Running an instance of topic-based topology on a node generates a fanout set for each topic the node is subscribing to. As the result of independent invocations of topic-based topology on different nodes in Flow, several overlapping connected components are shaped among the nodes, each corresponding to a single topic. The topology graph of the entire network is then the union of these connected components. Since the individual topic-based components are connected, the entire topology graph of the network is also connected. The figure below shows the general idea of building the topology graph of the system using connected components as it happens in the topic-based topology. The topic-based topology provides deterministic connectedness among the nodes subscribing to a topic by creating a fanout of (x+1)/2 per node using the linear fanout function, where x is the number of nodes subscribed to the topic. In this way, the resulted graph component of the topic is guaranteed with connectedness. The topic-based topology is the topology in effect of Flow at the moment.

RandomizedTopology

The randomized-topology is similar to the topic-based topology, except that upon constructing a graph component for a topic, instead of choosing a fixed-size fanout per node, it selects the fanout of the node probabilistically using an edge probability, p. For the set of nodes subscribed to a topic, each node includes any other node in its fanout with the probability of p, hence, the expected fanout of a node on the graph component of a topic is p * x where x is the number of nodes subscribed to the topic. Choosing an appropriate edge probability (e.g., 0.05) the randomized topology provides a connected graph with a very high probability (e.g., 1 - 2^-30), while it needs drastically smaller fanout per node. The randomized topology is not yet in effect, however, it is planned to replace the topic-based topology soon to support the scalability of the network.

Documentation

Index

• func CheckMembership(t *testing.T, top flow.IdentityList, all flow.IdentityList)
• func CheckTopologySize(t *testing.T, total int, top flow.IdentityList)
• func ClusterNum(t *testing.T, ids flow.IdentityList, size int) int
• func Connected(t *testing.T, adjMap map[flow.Identifier]flow.IdentityList, ...)
• func LinearFanout(size int) int
• func MockStateForCollectionNodes(t *testing.T, collectorIds flow.IdentityList, clusterNum uint) (protocol.State, flow.ClusterList)
• func MockSubscriptionManager(t *testing.T, ids flow.IdentityList) []network.SubscriptionManager
• type Cache
  • func NewCache(log zerolog.Logger, top network.Topology) *Cache
  • func (c *Cache) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)
• type FanoutFunc
• type RandomizedTopology
  • func NewRandomizedTopology(nodeID flow.Identifier, logger zerolog.Logger, edgeProb float64, ...) (*RandomizedTopology, error)
  • func (r RandomizedTopology) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)
• type TopicBasedTopology
  • func NewTopicBasedTopology(nodeID flow.Identifier, logger zerolog.Logger, state protocol.State) (*TopicBasedTopology, error)
  • func (t TopicBasedTopology) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)

Functions

func CheckMembership

func CheckMembership(t *testing.T, top flow.IdentityList, all flow.IdentityList)

CheckMembership checks each identity in a top list belongs to all identity list.

func CheckTopologySize

func CheckTopologySize(t *testing.T, total int, top flow.IdentityList)

TODO: fix this test after we have fanout optimized. CheckTopologySize evaluates that overall topology size of a node is bound by the fanout of system.

func ClusterNum

func ClusterNum(t *testing.T, ids flow.IdentityList, size int) int

ClusterNum is a test helper determines the number of clusters of specific `size`.

func Connected

func Connected(t *testing.T, adjMap map[flow.Identifier]flow.IdentityList, ids flow.IdentityList, f flow.IdentityFilter)

Connected checks if the graph represented by the adjacency matrix is connected. It traverses the adjacency map starting from an arbitrary node and checks if all nodes that satisfy the filter were visited.

func LinearFanout

func LinearFanout(size int) int

LinearFanoutFunc guarantees full network connectivity in a deterministic way. Given system of `size` nodes, it returns `size+1/2`.

func MockStateForCollectionNodes

func MockStateForCollectionNodes(t *testing.T, collectorIds flow.IdentityList, clusterNum uint) (protocol.State, flow.ClusterList)

MockStateForCollectionNodes is a test helper function that generate a mock state clustering collection nodes into `clusterNum` clusters.

func MockSubscriptionManager

func MockSubscriptionManager(t *testing.T, ids flow.IdentityList) []network.SubscriptionManager

MockSubscriptionManager returns a list of mocked subscription manages for the input identities. It only mocks the Channels method of the subscription manager. Other methods return an error, as they are not supposed to be invoked.

Types

type Cache

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

Cache provides caching the most recently generated topology. It implements the same GenerateFanout as a normal topology, so can easily replace any topology implementation. As long as the input IdentityList to it is the same, the cached topology is returned without invoking the underlying GenerateFanout. This is vital to provide a deterministic topology interface, as by its nature, the Topology interface does not guarantee a deterministic behavior.

Note: as a convention with other topology implementations, Cache is not concurrency-safe, and should be invoked in a concurrency safe way, i.e., the caller should lock for it.

func NewCache

func NewCache(log zerolog.Logger, top network.Topology) *Cache

NewCache creates and returns a topology Cache given an instance of topology implementation.

func (*Cache) GenerateFanout

func (c *Cache) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)

GenerateFanout receives IdentityList of entire network and constructs the fanout IdentityList of this instance. It caches the most recently generated fanout list, so as long as the input list is the same, it returns the same output. It invalidates and updates its internal cache the first time input list changes. A node directly communicates with its fanout IdentityList on epidemic dissemination of the messages (i.e., publish and multicast). Independent invocations of GenerateFanout on different nodes collaboratively must construct a cohesive connected graph of nodes that enables them talking to each other.

Note that this implementation of GenerateFanout preserves same output as long as input is the same. This should not be assumed as a 1-1 mapping between input and output.

type FanoutFunc

type FanoutFunc func(size int) int

FanoutFunc represents a function type that receiving total number of nodes in flow system, returns fanout of individual nodes.

type RandomizedTopology

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

RandomizedTopology generates a random topology per channel. By random topology we mean a node is connected to any other co-channel nodes with some edge probability.

func NewRandomizedTopology

func NewRandomizedTopology(nodeID flow.Identifier, logger zerolog.Logger, edgeProb float64, state protocol.State) (*RandomizedTopology, error)

NewRandomizedTopology returns an instance of the RandomizedTopology.

func (RandomizedTopology) GenerateFanout

func (r RandomizedTopology) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)

GenerateFanout receives IdentityList of entire network and constructs the fanout IdentityList of this instance. A node directly communicates with its fanout IdentityList on epidemic dissemination of the messages (i.e., publish and multicast). Independent invocations of GenerateFanout on different nodes collaboratively must construct a cohesive connected graph of nodes that enables them talking to each other. This should be done with a very high probability in randomized topology.

type TopicBasedTopology

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

TopicBasedTopology is a deterministic topology mapping that creates a connected graph component among the nodes involved in each topic.

func NewTopicBasedTopology

func NewTopicBasedTopology(nodeID flow.Identifier, logger zerolog.Logger, state protocol.State) (*TopicBasedTopology, error)

NewTopicBasedTopology returns an instance of the TopicBasedTopology.

func (TopicBasedTopology) GenerateFanout

func (t TopicBasedTopology) GenerateFanout(ids flow.IdentityList, channels network.ChannelList) (flow.IdentityList, error)

GenerateFanout receives IdentityList of entire network and constructs the fanout IdentityList of this instance. A node directly communicates with its fanout IdentityList on epidemic dissemination of the messages (i.e., publish and multicast). Independent invocations of GenerateFanout on different nodes collaboratively must construct a cohesive connected graph of nodes that enables them talking to each other.