Broadcast with Tree Selection on An Overlay Network
Takeshi Kaneko, and Kazuyuki Shudo
Tokyo Institute of Technology
Abstract—On an overlay network where a number of nodes
work autonomously in a decentralized way, the efficiency ofbroadcasts has a significant impact on the performance of a distributed system built on the network. While a broadcast method
using a spanning tree produces a small number of messages, therouting path lengths are prone to be relatively large. Moreover,when multiple nodes can be source nodes, inefficient broadcasts
often occur because the efficient tree topology differs for eachnode. To address this problem, we propose a novel protocol
in which a source node selects an efficient tree from multiple
spanning trees when broadcasting. This technique reduces thefrequency of inefficient broadcasts for multiple source nodes,
and shortens routing paths while maintaining a small number ofmessages. We examined path lengths and the number of messages
for broadcasts on various topologies. As a result, especially for arandom graph, our proposed method shortened path lengths byapproximately 28% compared with a method using a spanningtree, with almost the same number of messages.

I. I NTRODUCTION
An overlay network is an application-level logical network
built on an existing network such as the Internet. It is applied to various distributed systems: e.g. distributed key/value
stores [1], video streaming [2], and online games [3]. In recent
years, application to the fields of IoT and blockchain is also
expected [4].
On an overlay network where a number of nodes work
autonomously in a decentralized way, the large-scale distributed system requests frequent information exchange withlow latency to achieve high scalability and high reliability.
Therefore, the efficiency of broadcasts has a significant impact
on the performance of the distributed system.
A variety of methods to realize efficient broadcasts havebeen proposed [5]. In particular, while tree-based methods
using a spanning tree built on the network produce a small
number of messages, the routing path lengths are prone to
be larger than those of flooding and gossip-based methods.
Moreover, when multiple nodes issue broadcasts on a single
spanning tree, inefficient broadcasts often occur because theappropriate topology of the tree differs for each node.
To address this problem, we propose a novel protocol inwhich a source node selects an efficient tree from multiple
spanning trees when broadcasting. This method reduces thefrequency of inefficient broadcasts for multiple source nodes,
even if most participating nodes can be source nodes. It
thereby shortens routing path lengths while maintaining theadvantage of tree-based methods, which is producing a small
number of messages. We adopt Plumtree [6] as the spanning
tree construction protocol.
The remainder of this paper is organized as follows. Section II presents the related work on broadcasts using spanning
trees. Section III defines notations used in this paper. Sec-tion IV presents the proposed method. Section V presents theevaluation results. Finally, Section VI presents the conclusion.
II. R ELATED W ORK
A. Plumtree
Leitao et al. proposed a broadcast method called
Plumtree [6], which combines a gossip protocol and a treebased protocol. This achieves both a small number of messages
and high reliability. In addition, the routing path lengths ofeach broadcast are relatively small for multiple source nodes
due to the optimization process of the tree topology. However,as with other tree-based broadcasts, the lengths are still prone
to be larger than those of flooding because broadcast messages
are sent only on a single spanning tree topology.
B. Methods Using Multiple Spanning Trees
SplitStream [7] and Chunkyspread [8] are multicast methods
that construct multiple spanning trees on a network. Because
the purpose is streaming, the content is divided into some strips
and they are sent with all trees simultaneously; the load isthereby balanced for each tree. On the other hand, the proposed
method selects an appropriate tree instead of multiple trees
and shortens the routing paths. SplitStream also differs fromthe proposed method in that it constructs spanning trees ona structured overlay Pastry [9], rather than an unstructured
overlay.
Thicket [10] is a multicast method that constructs andmanages multiple spanning trees on an unstructured overlay.
As with other existing methods, the purpose of using multiple
spanning trees is load balancing. On the other hand, theproposed method selects one tree from multiple spanning trees
when broadcasting to shorten the routing paths. It is possible
to partially apply the proposed method to Thicket because theidea for the tree selection is simple.
III. N OTATIONThis section defines notations used in this paper.
An undirected graph G is represented by a pair (V, E),
where V denotes a set of vertices and E denotes a set ofedges. We define the following for G = (V, E):V• adjG : V 3 v 7→ (the set of all neighbors of v) ∈ 2• degG : V 3 v 7→ |adjG (v)| ∈ N• distG : V × V 3 (u, v) 7→(the distance between u and v) ∈ N ∪ {∞}– Especially, ∀ v ∈ V, distG (v, v) = 0.
An undirected rooted tree T is represented by a triple (V, F, r);where V denotes a set of vertices, F denotes a set of edges,
and r denotes the root node. It can also be regarded simply
as an undirected graph T = (V, F ). We define the following
for T = (V, F, r):Proc. 36th Int'l Conf. on Information Networking(ICOIN 2022), January 2022

TreeFig. 1. An example of tree selection from multiple spanning trees for a source node s.

parentT : V − { r } 3 v 7→ (the parent of v) ∈ V
childrenT : V 3 v 7→
(the set of all children of v) ∈ 2V
• subtreeT : V 3 v 7→ (the rooted subtree induced by v)• heightT := max { distT (r, v) | v ∈ V } ∈ N••

IV. P ROPOSED M ETHOD

Algorithm 1:
vcurrent

Fields and Initialization in a Nodedata structure Tree
field eagerPushPeers : SethNodei
3field lazyPushPeers : SethNodei
4field distFor : MaphNode, Inti
5field parent : Node1

2

upon receiving hI NITi thenpeers ← getPeers()
8
trees ← new MaphInt, Treei
9
receivedMsgs ← new MaphInt, Messagei
10
missing ← ∅6

In the proposed method, multiple spanning trees are constructed on an overlay network (Section IV-A), and a source
node selects an appropriate tree from them (Section IV-B) andissues a broadcast (Section IV-C).
Each spanning tree is embedded in an unstructured overlay
network managed by a peer sampling service [11], [12].
A spanning tree is maintained along the Plumtree protocol [6]. In Plumtree, a node has two types of neighbors ineagerPushPeers and lazyPushPeers sets. EagerPushPeers
include neighbors along tree edges and lazyPushPeers include
other neighbors. A broadcast is basically performed over a tree,that is, forwarding to eagerPushPeers. A node sometimes forwards a notification of arrival of a message to lazyPushPeers.
The notified node starts repairing a tree if it has not received
the message along the tree. Tree construction is as follows.
A node has all its neighbors in its eagerPushPeers at thestart of the construction. The initial tree is lengthy and there
are multiple paths to a single node. If a node receives thesame message from multiple neighbors, the node replies a
PRUNE message to the sender and both the sending andreceiving nodes move each other from eagerPushPeers to
lazyPushPeers.
Since messages for each broadcast are sent on a single tree,
the number of messages is approximately Θ(n) for a stable
overlay network where n denotes the number of participating
nodes.
Moreover, our aim is to minimize the maximum path lengthfrom the source node to each node for each broadcast by thefollowing process:1) Suppose that a finite number of spanning trees
T1 = (V, F1 ), T2 = (V, F2 ), . . . , Tk = (V, Fk ) are managed on a graph G = (V, E)1 of the network topology.
2) A source node s ∈ V selects the tree Tλ(λ ∈ { 1, 2, . . . , k }) that minimizes
height(V,Fλ ,s) = max { distTλ (s, v) | v ∈ V } ,(1)

1 Strictly speaking, an overlay network with a peer sampling service forms a

topology of a directed graph. However, for simplicity, the network topology isregarded as an undirected graph in this paper because each managed spanning
tree behaves like an undirected graph.

7

which is the maximum path length of each simple pathwhose one end is the node s on Tλ .
Fig. 1 shows an example of tree selection. In this example,
the network manages three spanning trees T1 , T2 , and T3 ,the source node is a node s, and then height(V,F1 ,s) = 3,height(V,F2 ,s) = 4, and height(V,F3 ,s) = 4. Since T1 minimizes (1), the source node s selects T1 from them.
Note that, however, since each node does not have global
information on the network, it selects a tree based on a value
estimated only from information it knows rather than the exact
value of (1).
A. Construction of spanning trees
The proposed method constructs multiple spanning trees on
the network at the beginning of the protocol. The number oftrees, a positive integer k, is a system parameter determined
before running the protocol. We randomly select k start nodes
from the network2 and construct a spanning tree for each startnode based on the delivery tree by flooding.
Algorithm. 1 and Algorithm. 2 are pseudocodes on initialization and spanning tree construction, respectively. For
simplicity, the latter pseudocode assumes that no messages
are lost and no nodes join or leave during the construction ofa spanning tree. In practice, it is necessary to address suchsituations by using timeout timers.
Each start node vstart constructs a new spanning tree by
issuing an event hConstructTree, treeId new i to itself vstart .
Herein, we generate treeId new , the ID corresponding to thetree to be constructed, e.g., by a pseudorandom number toavoid duplicate IDs.
2 For example, we can sample some start nodes by doing a random walkfrom a node and selecting nodes on every certain number of hops. However,
because sampling with a simple random walk is biased by the degree of eachnode, if it is preferred to sample nodes with a uniform distribution, e.g., weshould use a random walk using Metropolis-Hastings algorithm [13].

Proc. 36th Int'l Conf. on Information Networking(ICOIN 2022), January 2022

Algorithm 2: Tree Construction in a Node vcurrent
upon receiving hC ONSTRUCT T REE, treeIdi from vsender thenif treeId ∈/ trees.keys() then3t ← new Tree4
trees[treeId] ← t
5t.eagerPushPeers ← peers
6t.parent ← vsender7for vadj ∈ t.eagerPushPeers do
8
if vadj = vsender then9
continue

1

2

send hC ONSTRUCT T REE, treeIdi to vadj

10
11
12

else
send hU PDATE D IST T OWARD ROOT, treeId, ∞i to vsender

upon receiving
hU PDATE D IST T OWARD ROOT, treeId, distForSender i fromvsender then14t ← trees[treeId]15
if distForSender < ∞ then16t.distFor [vsender ] ← distForSender
17
else
18
t.eagerPushPeers ← t.eagerPushPeers − {vsender }19t.lazyPushPeers ← t.lazyPushPeers ∪ {vsender }event for the treeId . The sender that receives it excludes
vcurrent from t.eagerPushPeers. Through these processes,
if each node is considered to have an edge with each nodein t.eagerPushPeers, a spanning tree forms on the network
where the start node vstart is the root node.
A node that sent an event hConstructTree, treeId i
to its neighbor nodes, after receiving an event
hU PDATE D IST T OWARD ROOT, treeId , distForSender i
from
each
of
them,
sends
an
event
hU PDATE D IST T OWARD ROOT, treeId , maxDist + 1itothe parent node t.parent where maxDist is

13

20
21
22
23
24
25

if t.eagerPushPeers − { t.parent } = t.distFor .keys() thenif t.parent = vcurrent then// when vcurrent is the root node of t
send hU PDATE D IST T OWARD L EAVES, treeId, 0i to
vcurrent
else
maxDist ←getMaxDistExceptOne(t.distFor , t.parent)
send
hU PDATE D IST T OWARD ROOT, treeId, maxDist + 1i
to t.parent

upon receiving
hU PDATE D IST T OWARD L EAVES, treeId, distForSender i fromvsender then27t ← trees[treeId]28
if vsender 6= vcurrent then29t.distFor [t.sender ] ← distForSender

26

30
31
32
33
34

for vadj ∈ t.eagerPushPeers do
if vadj = vsender thencontinue
maxDist ← getMaxDistExceptOne(t.distFor , vadj )send
hU PDATE D IST T OWARD L EAVES, treeId, maxDist + 1i
to vadjfunction getMaxDistExceptOne(distFor , vexcepted )maxDist ← 0
37
for (vadj , d) ∈ distFor do
38
if vadj = vexcepted then39
continue

35

maxDist{ 0 }∪()
= max  t.distFor [v] |.
v ∈ t.eagerPushPeers − { t.parent }(2)
In general, the following holds for any node v ∈ V of a rooted
tree T = (V, F, vstart ):heightsubtreeT (v)!
{ 0 }∪o .
= max nheightsubtreeT (u) + 1 u ∈ childrenT (v)(3)
Thus, this process means computing the height of the tree
by dynamic programming through the propagation of “distance” information into the root node vstart . Therefore, Eacht.distFor [vadj ] represents (heightsubtreeT (vadj ) + 1).
After completing the propagation of “distance” information
into the root node, “distance” information propagates
into leaf nodes such that each node sends an event
hU PDATE D IST T OWARD L EAVES, treeId , distForSender i toeach of the children. In general, the following holds for anyu ∈ V and any internal node v ∈ V − { vstart } of a rooted
tree T = (V, F, vstart ):

36

40
41

maxDist ← max{maxDist, d}return maxDist

When each node vcurrent
receives an event
hConstructTree, treeId i, if it does not have thecorresponding tree data, then it generates a new tree t
and initializes t.eagerPushPeers with its neighbor nodes
and sends the same event hConstructTree, treeId i to eachof the nodes. If it has the corresponding tree data, then it
sends an event hU PDATE D IST T OWARD ROOT, treeId , ∞i tothe sender to indicate that vcurrent has already received theheightsubtree(V,F,v) (u)() !
heightsubtree(V,F,v) (w) + 1 |= max { 0 } ∪w ∈ children(V,F,v) (u){ 0 }∪()
= max  heightsubtree(V,F,v) (w) + 1 |w ∈ adjT (u) − {parent(V,F,v) (u)}(4)

subtree(V,F,v) (u) = subtreeT (u),

(5)

If

Proc. 36th Int'l Conf. on Information Networking(ICOIN 2022), January 2022

If t represents a rooted tree (V, F, vcurrent ), distFor [vadj ] represents (heightsubtree(V,F,v(vadj ) +1). Thus, (9) represents
current )() !
heightsubtree(V,F,v
+1|
(v)
)
current
max { 0 } ∪v ∈ adj(V,F,vcurrent ) (vcurrent )Algorithm 3: A Broadcast with Tree Selection in a
Node vcurrent
upon receiving hB ROADCAST, msgi from vsender thenmsgId ← hash(msg k vcurrent )3
treeId ← selectTree()4
send hG OSSIP, msg, msgId, treeId, 0, 0i to vcurrent

1

2=height(V,F,vcurrent ) .

function selectTree()minTreeId ← ∞7minDist ← ∞8for (treeId, t) ∈ trees do
9
distToEnd ← max ({ 0 } ∪ t.distFor .values())
10
if distToEnd < minDist then11
minDist ← distToEnd
12
minTreeId ← treeId
5(10)This is equivalent to (1) where vcurrent = s. Therefore, thisprocess intuitively means tree selection minimizing the maximum path length for the broadcast.
In practice, tree selection does not always minimize themaximum path length because the selection is based on local
information and the network topology is dynamic. How thevalues t.distFor are updated is important for improving theaccuracy of the tree selection.

6

return minTreeId

13

C. Message propagation and value updatethenheightsubtree(V,F,v) (u)()
heightsubtreeT (w) + 1 |= max { 0 } ∪w ∈ adjT (u) − { parentT (u) }!

!
{ 0 }∪
noheightsubtreeT (w) + 1 w ∈ childrenT (u)= max=heightsubtreeT (u) .

(6)Moreover,parent(V,F,v) (u) ∈ childrenT (u)(7)

is a necessary condition for
u 6= v ∧ subtree(V,F,v) (u) 6= subtreeT (u).

(8)

Thus, when completing the propagation into leaf nodes, eacht.distFor (vadj ) represents (heightsubtree(V,F,v(vadj ) + 1).
current )Through the above processes, a spanning tree is constructedon the overlay network. In a one-and-a-half round-trip broadcast by the start node vstart , every t.distFor is computedby dynamic programming with piggyback of the “distance”
information.
B. Tree selection
A source node vcurrent broadcasts by issuing an event
hB ROADCAST, msgi for a message body msg to itself
vcurrent . Here, it selects a tree from trees and makes eachnode send messages on the tree.
Algorithm. 3 is a pseudocode on the tree selection. A
function selectTree returns the ID of the tree t in trees
such that (9) is minimum.
max ({ 0 } ∪ { distFor [vadj ] | vadj ∈ t.eagerPushPeers })(9)

Message propagation and topology management during abroadcast mostly follow the Plumtree protocol for a tree
determined by the tree selection algorithm. For message
propagation, a node provides a function receiving a Gossip
message, a function receiving a Prune message. For topology
management and optimization, a node provides a function
receiving Ihave message, a function receiving a Timeup
message, a function receiving Graft message. Pseudocode forthem can be derived intuitively from the Plumtree protocol. An
extended version of this paper will provide the pseudocode.
To support dynamics of the network for tree selection, eachnode updates the values of t.distFor (line 4 in Algorithm 1)
through the message propagation with piggybacked “distance”
information. Since the data size of the piggyback is very small,the additional cost of the communication is insignificant.
The more frequent broadcasts are, the faster the values of
distFor follow the exact values for the dynamic network,and the more accurate tree selection becomes. On the other
hand, the more the network changes, the more there is a delay
in following the values, and the less accurate tree selection
becomes.
Finally, for joining and leaving of nodes, a node provides a function receiving NeighborDown, a function receiving NeighborUp, and a function receiving DistUpdate.
NeighborUp and NeighborDown are events issued by a peer
sampling service and update information for neighbor nodes.
Moreover, the protocol also locally computes the values oft.distFor . An extended version of this paper will provide a
pseudocode.
V. E VALUATION
We conducted experiments by simulating broadcasts onan overlay network, and measured the path lengths and thenumber of messages. We developed the simulator by ourselves.
A. Experiment settings
The simulating procedure for a combination of a method
and an overlay network is as follows:
1) We generate an overlay network G = (V, E), on whichspanning trees are built.

Proc. 36th Int'l Conf. on Information Networking(ICOIN 2022), January 2022

2) We construct spanning trees if a method requires them.
3) Let the following procedure be 1 cycle, and we execute1000 cycles.
a) We determine a source node vstart ∈ V randomly.
b) We issue a broadcast on the source node vstart .
c) We measure the path lengths and the number ofmessages.
d) In Plumtree and the proposed method, we updatetree topologies by following each method.
We use the following graphs as the overlay network, on
which spanning trees are built. The number of nodes for eachgraph is |V | = 10000.
Random Graph
A random graph generated by Erdös-Rényi
model [14]. In this experiment, we generate agraph of Γ10000,50000 where |V | = 10000 and|E| = 50000. Γn,N is a graph generation model
whose N edges are randomly selected from n2node pairs for the fixed number of nodes n.
BA Model Graph
A graph generated by Barabási-Albert model [15].
The model generates a scale-free graph. In thisexperiment, |V | = 10000, and the number of edges
added at each step of the generation is 5. Thus,|E| ≈ 50000.
We use the following broadcast methods for comparison.
Plumtreeproposed
The proposed method. The number of trees is 10.
ideal proposed
A broadcast method where every tree selection forthe proposed method is ideal. This means that asource node always selects a tree minimizing the
maximum path length. The number of trees is 10.
multiple Plumtrees
A method that manages 10 Plumtrees and broadcasts
to all of them. The path length is the minimum path
length among all the trees. The number of messages
is approximately 10 times larger than Plumtree.
flooding
Since we assume that there are multiple source nodes forbroadcasts, we set the value threshold used in the topology
optimization of Plumtree protocol to 7.
B. Experiment result
Fig. 2 and Fig. 3 show the transitions of the maximum path
lengths and the average path lengths of broadcasts for Random
Graph, respectively. The translucent lines represent the measured values, and the opaque lines represent the moving
average value for 50 cycles. The same representation is usedin the following figures showing the transition of path lengths.
We use moving averages to facilitate comparison of the relativevalues for each broadcast method. As a result of Fig. 2,
the proposed method proposed reduces the maximum path
length by approximately 28% compared with Plumtree.

TABLE IR EDUCTION RATIO OF MAXIMUM PATH LENGTH BY PROPOSED METHODCOMPARED TO P LUMTREE .
Overlay network
Random Graph
BA Model Graph

Reduction ratio
28%
7%However, it is not as short as that of ideal proposed,
which suggests that the update of values distFor does not
sufficiently follow the topology changes by Plumtree protocol.
In addition, the maximum path length of ideal proposedis almost the same as that of multiple Plumtrees. Thissuggests that the proposed method can potentially achieve thesame length as the maximum path length when using multiple
Plumtrees despite the number of messages on using a single
Plumtree if the values distFor follows the topology changes.
Furthermore, as a result of Fig. 3, the magnitude relationshipof the average path length of each broadcast method tends tobe almost the same as that of the maximum path length.
Fig. 4 shows the relation between the maximum path lengthand the number of messages for Random Graph. We plotted
the results for 901–1000 simulation cycles. As a result, thenumbers of messages of Plumtree, proposed, and ideal
proposed are approximately 10000 (≈ |V |), which aremuch smaller than those of flooding and multiple
Plumtrees, and especially, are approximately 11% of thatof flooding. This is because, in the former, most messages
are sent on a single spanning tree and there are few duplicate
messages, while in the latter, many duplicate messages occur
due to the property of the methods. Therefore, the experimental results for Random Graph show that the proposed
method shortens path lengths compared to Plumtree while
maintaining the small number of messages.
Fig. 5 and Fig. 6 show the transitions of the maximum
path lengths and the average path lengths of broadcasts for
BA Model Graph, respectively. As a result of Fig. 5, theproposed method proposed reduces the maximum path
length by approximately 7% compared to Plumtree. In
addition, it achieves almost the same maximum path length asthat of ideal proposed, which suggests that the updateof values distFor significantly follows the topology changes
by Plumtree protocol for BA Model Graph.
Fig. 7 shows the relation between the maximum path lengthand the number of messages for BA Model Graph. We
plotted the results for 901–1000 simulation cycles. It presents
a similar result to Fig. 4 on the number of messages.
Table I summarizes the reduction ratio of maximum path
length by the proposed method compared to Plumtree. Contribution of the proposed method could be much on a randomgraph, and moderate on a scale-free network generated by a
BA model, that is natively efficient for broadcasting due to its
small diameter.
VI. C ONCLUSION
In this paper, we proposed a novel broadcast method. It
constructs multiple spanning trees on the overlay network,and a source node selects an appropriate tree from themProc. 36th Int'l Conf. on Information Networking(ICOIN 2022), January 2022

12.5
10.0
7.5
5.0

10
8
6

Plumtreeproposedideal proposed
multiple Plumtrees
flooding

4
2

2.5
0

200

400

600

Simulation cycle

800

0

1000

0

200

400

600

Simulation cycle

800

1000

Fig. 2. Maximum path length for Random Graph. Fig. 3. Average path length for Random Graph.

Average path length

Maximum path length

4

Plumtreeproposedideal proposed
multiple Plumtrees
flooding

200Fig. 5.
Graph.

200

400

5
4
3

Plumtreeproposedideal proposed
multiple Plumtrees
flooding

2
1

600

Simulation cycle

800

1000

Maximum path length for BA Model

0

60000
40000

0
0.0

2.5

5.0

7.5

10.0

12.5

15.0

Maximum path length

17.5

20.0

1000006
6

80000

Fig. 4. Relation between the maximum path lengthand the number of messages for Random Graph.

78100000

20000

0

200

400

600

800

Number of messages

0.0

Number of messages

15.0

Plumtreeproposedideal proposed
multiple Plumtrees
flooding

12000012

Average path length

Maximum path length

17.5

14000014

Plumtreeproposedideal proposed
multiple Plumtrees
flooding

20.0

80000

60000

40000

Plumtreeproposedideal proposed
multiple Plumtrees
flooding

20000

0

0

1000

2

4

6

Maximum path length

8

Simulation cycle
Fig. 7. Relation between the maximum path
Fig. 6. Average path length for BA Model Graph. length and the number of messages for BA Model
Graph.

when broadcasting. This reduces the frequency of inefficient
broadcasts for multiple source nodes. It thereby achieves
shortening routing path lengths while maintaining a small
number of messages.
The evaluation experiments show that the effect of the
proposed method on the path lengths is dependent on the
topology of the overlay network. For graphs that closely
resemble realistic network topologies, the paths tend to be
shortened, especially for a random graph, with a reduction
ratio of approximately 28% compared to Plumtree. Moreover,the number of messages was almost the same as the numberof nodes. This shows that the proposed method shortens path
lengths while maintaining the small number of messages.
ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Number JP21H04872.
R EFERENCES[1] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman,
A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo:
Amazon’s Highly Available Key-value Store,” in Proceedings of TwentyFirst ACM SIGOPS Symposium on Operating Systems Principles, ser.
SOSP ’07. New York, NY, USA: ACM, 2007, pp. 205–220.
[2] N. Ramzan, H. Park, and E. Izquierdo, “Video streaming over P2P
networks: Challenges and opportunities,” Signal Processing: Image
Communication, vol. 27, no. 5, pp. 401–411, May 2012.
[3] A. Yahyavi and B. Kemme, “Peer-to-peer Architectures for Massively
Multiplayer Online Games: A Survey,” ACM Comput. Surv., vol. 46,
no. 1, pp. 9:1–9:51, Jul. 2013.
[4] A. Dorri, S. S. Kanhere, and R. Jurdak, “Towards an Optimized
BlockChain for IoT,” in Proceedings of the Second IEEE/ACM International Conference on Internet-of-Things Design and Implementation,
ser. IoTDI ’17. New York, NY, USA: ACM, 2017, pp. 173–178.

[5] P. Ruiz and P. Bouvry, “Survey on Broadcast Algorithms for Mobile Ad
Hoc Networks,” ACM Computing Surveys (CSUR), vol. 48, no. 1, pp.
8:1–8:35, Jul. 2015.
[6] J. Leitao, J. Pereira, and L. Rodrigues, “Epidemic Broadcast Trees,”in 2007 26th IEEE International Symposium on Reliable Distributed
Systems (SRDS 2007), Oct. 2007, pp. 301–310.
[7] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron,and A. Singh, “SplitStream: High-bandwidth multicast in cooperativeenvironments,” ACM SIGOPS Operating Systems Review, vol. 37, no. 5,
pp. 298–313, Oct. 2003.
[8] V. Venkataraman, K. Yoshida, and P. Francis, “Chunkyspread: Heterogeneous Unstructured Tree-Based Peer-to-Peer Multicast,” in Proceedingsof the 2006 IEEE International Conference on Network Protocols, Nov.
2006, pp. 2–11.
[9] A. Rowstron and P. Druschel, “Pastry: Scalable, Decentralized Object
Location, and Routing for Large-Scale Peer-to-Peer Systems,” in Middleware 2001, ser. Lecture Notes in Computer Science, R. Guerraoui,
Ed. Springer Berlin Heidelberg, 2001, pp. 329–350.
[10] M. Ferreira, J. Leitão, and L. Rodrigues, “Thicket: A Protocol for
Building and Maintaining Multiple Trees in a P2P Overlay,” in 2010
29th IEEE Symposium on Reliable Distributed Systems, Oct. 2010, pp.
293–302.
[11] M. Jelasity, S. Voulgaris, R. Guerraoui, A.-M. Kermarrec, and M. van
Steen, “Gossip-based peer sampling,” ACM Transactions on Computer
Systems, vol. 25, no. 3, pp. 8–es, Aug. 2007.
[12] J. Leitao, J. Pereira, and L. Rodrigues, “HyParView: A Membership Protocol for Reliable Gossip-Based Broadcast,” in 37th Annual
IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’07), Jun. 2007, pp. 419–429.
[13] M. Al Hasan, “Methods and Applications of Network Sampling,” inOptimization Challenges in Complex, Networked and Risky Systems, ser.
INFORMS TutORials in Operations Research. INFORMS, Oct. 2016,ch. 5, pp. 115–139.
[14] P. Erdös and A. Rényi, “On random graphs I.” Publicationes mathematicae, vol. 6, no. 26, pp. 290–297, 1959.
[15] A.-L. Barabási and R. Albert, “Emergence of Scaling in Random
Networks,” Science, vol. 286, no. 5439, pp. 509–512, Oct. 1999.

Proc. 36th Int'l Conf. on Information Networking(ICOIN 2022), January 2022