{'fraction_non_alphanumeric': 0.04217196819085487, 'fraction_numerical': 0.012276341948310138, 'mean_word_length': 4.046526210183095, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tree dynamics for peer-to-peer streaming

This paper presents an asynchronous distributed algorithm to manage multiple trees for peer-to-peer streaming in a flow level model. It is assumed that videos are cut into substreams, with or without source coding, to be distributed to all nodes. The algorithm guarantees that each node receives sufficiently many substreams within delay logarithmic in the number of peers. The algorithm works by constantly updating the topology so that each substream is distributed through trees to as many nodes as possible without interference. Competition among trees for limited upload capacity is managed so that both coverage and balance are achieved. The algorithm is robust in that it efficiently eliminates cycles and maintains tree structures in a distributed way. The algorithm favors nodes with higher degree, so it not only works for live streaming and video on demand, but also in the case a few nodes with large degree act as servers and other nodes act as clients. A proof of convergence of the algorithm is given assuming instantaneous update of depth information, and for the case of a single tree it is shown that the convergence time is stochastically tightly bounded by a small constant times the log of the number of nodes. These theoretical results are complemented by simulations showing that the algorithm works well even when most assumptions for the theoretical tractability do not hold.


I. INTRODUCTION
Peer-to-peer communication, when applied to streaming, is attractive because it enables the total bandwidth for service to scale with demand [1], [2]. Scheduling algorithms need to be designed so that upload capacity provided by nodes can be utilized efficiently to serve the demand, and each node can download streams, providing playback continuity with small delay. The system needs to be robust enough to tolerate peer churn, link failures, and congestion.
Many designs have been proposed for P2P streaming. Unstructured topologies with nodes constantly sampling new targets for new pieces are considered in [3], [4]. Data dissemination algorithms based on mesh topologies are given in [5], [6]. In [7], random Hamiltonian cycles are constructed and tangled and pieces are broadcasted around the union of the cycles. Fixed underlying topologies are considered in [8], [9] and flows are scheduled between neighbors. Algorithms to manage multiple distribution trees to disseminate different substreams of a video or audio are discussed in [10]- [13], but those papers do not concentrate on distributed algorithms.
Unstructured streaming systems are simple to manage and scale well, but playback continuity is sacrificed because constantly building and removing links requires prohibitive overhead. Tree structures can provide good playback continuity with small startup delay, but can be difficult to manage, especially in a distributed way. In this paper we study how to manage trees for P2P streaming as in [10]- [12], but with a focus on distributed algorithms.
Consider a complete underlying network for control information, so arbitrary node to node contact is allowed. To model the bandwidth constraint for control information, we only allow each node to randomly contact a target from other nodes periodically at a certain constant rate. This setting, which is more suitable for P2P systems, is different from settings in [14]- [18], which discuss how to build multicast trees satisfying certain metrics under a fixed underlying topology. Most problems formulated in [14], [16]- [18] are shown to be NP hard and approximation algorithms are designed. In this paper we avoid NP completeness with a homogeneous and complete underlying topology.
The streaming network is built on top of the underlying network, through the cooperation of nodes. Besides the bandwidth constraint on exchanging control information, nodes have heterogeneous upload capacity so each of them has a maximum fan-out degree for streaming. Nodes have a small buffer to store information about their parents and children in the streaming network. They can exchange messages with their parents and children, at the same time they can also exchange messages with their sampled targets at the sampling times. As in [10]- [12], we assume the video is cut into substreams, source coding like multiple description coding (MDC [19]) is applied to provide redundancy in data. Multiple diverse distribution trees, which constitute the streaming network, are constructed and managed, each for one substream.
In [10] it is mentioned that a good tree management algorithm should maintain 1) short trees, i.e., trees have small depths so as to minimize the probability of disruption due to peer transience or congestion; 2) tree diversity, i.e., the set of ancestors of a node in each tree are as disjoint as possible so as to increase the effectiveness of the MDC-based distribution scheme; 3) quick processing of node joins and leaves, and; 4) scalability. Centralized solutions in [10]- [12] are proposed to achieve those goals. In this paper, an asynchronous distributed algorithm is designed to manage multiple trees, with the following properties: 1) Each node can receive enough substreams. the roots of the trees. 7) Heterogeneous upload capacity is supported, even in the case a few nodes with large degree act as servers and other nodes act as clients. 8) Convergence is insured even when the ratio of total demand to total upload capacity, ρ, is one, and it converges more quickly as ρ decreases from one. Analyzing the complexity for message exchange for the algorithm is quite challenging. We show that the convergence time is stochastically tightly bounded by O(log N ) where N is the number of nodes, both by theoretical analysis in the case of a single tree and by simulation. During a sampling interval O(N ) messages are exchanged. So we conjecture that with high probability, only O(N log N ) messages need to be exchanged before the algorithm converges.
Other related work for P2P message transmission includes [20]- [28], which focus on modeling the performance of file sharing networks.
The paper is organized as follows. The model is introduced in Section II. The main algorithm and the proof of convergence are provided in Section III. Bounds on the convergence time are covered in Section IV. Simulations are provided in Section V which show that the algorithm works well even when most assumptions imposed in Section III for theoretical tractability do not hold.

II. PROBLEM SETUP
Consider a network containing one server and N users (nodes), labeled as 1, 2, ...N . One video to be broadcast from the server to all nodes is cut into M substreams. Each substream is transmitted through a directed broadcast tree. We consider the problem of how to build broadcast trees, so as to avoid interference, achieve coverage and reduce delay.
In this paper we consider a flow level model. Let V denote the set of N nodes. As illustrated in Figure 1, assume there are M root nodes (or roots, M << N ) in V , each of which always has an incoming link from the server, and always receives a distinct substream via such link. Each root works as an "agent" of the server to further distribute its received substream. Let R denote the set of roots. For convenience, assume the root nodes are nodes 1 through M , and label each substream by the label of the root receiving the stream from the server.
Assume nodes in V can randomly contact each other and build directed links among themselves. Let E denote the set of all such links. Through each link one and only one substream can be transmitted from the tail to the head of the link. Assume that at the time a link is built, the substream to be transmitted That is, V i is the set of nodes which can receive substream i. Assume that to recover the video, a node u must receive at least K ≤ M substreams: |{i ∈ R : u ∈ V i }| ≥ K. It is possible that K < M , corresponding to the use of source coding. Assume each node has a constraint on upload capacity (outdegree): node u can build at mostd u outgoing links, whatever their colors are. Figure 1 contains examples of (V, E) for M = K = 2 and N = 4, 5, 6, where roots have outdegree one and other nodes have outdegree two. In Figure 1, for each root i, (V, E i ) is a spanning tree with the minimum depth under out degree constraint, with the tree depth defined as the maximum number of hops over all root-leaf paths.
Five types of link updates are considered in this paper, as shown in Figure 2. Each link update can be executed locally because at most four nodes are involved. Notice that link updates in Figure 2 are just combinations of building a link and removing a link. Any node on the left side of a link update in Figure 2 can initiate that update, by exchanging messages with other nodes involved.
Assume each node maintains a Poisson clock which ticks at rate µ = 1, independently of Poisson clocks of other nodes. Whenever the clock of a node ticks, the node samples a target from other nodes uniformly at random, and decides whether to execute link updates in Figure 2 or not. In this paper, we assume link updates happen instantaneously, but at most one update can be executed at each sampling. It makes the problem tractable and is also a reasonable relaxation because one link update consists of building at most two links and removing at most two links. In this paper we normalize the time so µ = 1.
In Figure 1, the spanning tree for each substream has log N depth. In the next section, we show our algorithm, under which E is repeatedly updated until no more updates are possible, insures that all substreams can be broadcasted through distinct trees with log N depth and each node can receive enough substreams for the video. For convenience, notations are listed: L i (u) = +∞ if no path exists from i to u in (V, E i ). • l u i : the depth to i buffered by u, which keeps updating.
be the total number of outgoing links of u. • available: Node u is available if u has an incoming link and d(u) <d u . • mixed node: A node is mixed if it has outgoing links with at least two colors.

III. ALGORITHM
Our main algorithm is summarized in Section III-E as Procedure CombinedUpdate, which is a topology update procedure ran after nodes randomly contact each other. In the following we introduce CombinedUpdate by parts. Notice that by assumption in Section II running of CombinedUpdate is instantaneous. Assume each node knows its parents, children, and colors of its incoming and outgoing links. Each node buffers its depths to all roots. To begin, we assume at time 0 (V, E) satisfies Assumption 1.

Assumption 1 (Tree Initially).
At time 0, (V, E) satisfies the following: 1) Each node u has at most K incoming links, has at most one incoming i-link for each i ∈ R, and at mostd u outgoing links, which implies that, 2) (V i , E i ) is a directed tree rooted at i for each i ∈ R.
Notice that 1) implies 2) in Assumption 1. And notice that cycles may appear in (V \ V i , E i ) even if (V i , E i ) is a tree, as shown in Figure 4. Assumption 1 can be easily satisfied by requiring all nodes to remove extra incoming or outgoing links at time 0. We will show that the properties in Assumption 1 are preserved by the update procedures we shall define. In the following the procedure for depth update is discussed first.

A. Distributed depth update
Each node buffers its depths to each root i ∈ R. Notice l u i denotes the depth to i buffered by node u.
Procedure DepthUpdate (Node u, Color i) If node u is root i, u sets l u i to 0; otherwise, • if u has no incoming i-links, u sets l u i to +∞; • if u has incoming i-links, let l be the minimum depth to i buffered by all i-parents of u, u sets l u i to l + 1. We think ∞ + 1 = ∞ in DepthUpdate. Root i sets its depth to i as 0, and any other node updates its depth to i as l +1 if it finds that the minimum depth to i buffered by its i-parents is l. Each node u periodically runs DepthUpdate so as to insure its buffered depths are close approximations to the real depths L i (u), i ∈ R. We will show that each node maintains just one incoming i-link over all time, so a node needs to contact just one i-parent when DepthUpdate is running.
We do not require nodes update depths much more frequenctly than they sample targets. Assume node u updates depths for three types of events: • after u builds a new incoming i-link, immediately u runs DepthUpdate(u,i). • after u samples a target, u runs DepthUpdate(u,j) for all j ∈ R immediately. • after u is sampled as a target, u runs DepthUpdate(u,j) for all j ∈ R immediately. Thus, nodes update depths about twice as fast as their Poisson clocks tick.

B. Distributed greedy covering
In this section a greedy procedure is proposed to insure that each node has at least K incoming links with distinct colors. Notice that nodes are randomly sampling others. Assume a node u runs Procedure GreedyTreeCover after it samples node u p as a target: Procedure GreedyTreeCover (Node u, Node u p ) Output: return true if (V, E) changes, return false otherwise. Tie broken: arbitrarily If u has less than K incoming links and there exists i such that u has no incoming i-link but u p has an incoming i-link, GreedyTreeCover does not use depth information. It has several properties: if Assumption 1 is valid, as nodes sample targets and run GreedyTreeCover, 1) statements in Assumption 1 remain valid; 2) for each i ∈ R, |V i | is nondecreasing, but the depth of tree (V i , E i ) is also nondecreasing. 3) for each i ∈ R and each node u, both d i (u) and the number of incoming i-links of u are nondecreasing. In the following we state several additional assumptions under which running GreedyTreeCover after nodes sample targets can lead all nodes to be covered by K trees.
First, nodes have to provide enough fan-out degrees to meet the demands of incoming links, so Assumption 2 is assumed.
Second, notice that for i ∈ R, if at time 0 root i is not available and root i does not have outgoing i-links, it is not possible for any node to ever build incoming i-links from i. That is, V i = {i} over all time. To avoid that, we assume root i has at least one i-child at time 0: Assumption 3 (Root Child Guarentee). For each i ∈ R, d i ≥ 1 and at time 0 root i has at least one i-child.
Third, GreedyTreeCover does not generate new cycles, but it cannot eliminate original cycles. As shown in Figure 4, (V \ V i , E i ) may contain cycles at time 0, which cannot be eliminated by GreedyTreeCover. In this section we pause discussions on cycles by assuming Assumption 4 is valid, in the next section we will show how cycles are eliminated.

Assumption 4 implies that no cycle exists in
for each i ∈ R at time 0. By running GreedyTreeCover no i-links will be built beween nodes in V \ V i and so no cycle ever appears. The following two indicate the convergence of running GreedyTreeCover.
Lemma III.1. If Assumptions 1 to 4 are valid, then at time 0, GreedyTreeCover(u,v) returns false for all u, v ∈ V if and only if |{i ∈ R : u ∈ V i }| = K for each node u, that is, if and only if each node is covered by K trees.
Proof. If a node has K incoming links with distinct labels, GreedyTreeCover returns false whichever target the node samples. So the if part follows.
Suppose there exists u ∈ V, |{i ∈ R : u ∈ V i }| < K. We prove the only if part by showing that GreedyTreeCover returns true when two specific nodes meet. Node u has fewer than K incoming links. Assumption 1 implies that each node has at most K incoming links.
if v has K incoming links, GreedyTreeCover(u,v) returns true because "Add" can happen; b) if v has fewer than K incoming links, GreedyTreeCover(v,i) returns true if v ∈ V i because "Insert" can happen.
Proposition III.2. Under Assumptions 1 to 4, if GreedyTreeCover(u,v) runs whenever u samples v for any u, v ∈ V , then |{i ∈ R : w ∈ V i }| = K for all w ∈ V in finite time. GreedyTreeCover can achieve coverage, but it has two main drawbacks: first, the depth of the tree (V i , E i ) for i ∈ R can be large; second, it cannot detect and eliminate cycles. In the next section we show how to solve these two problems by adding balance algorithms as complements.

C. Achieve balance inside trees
One way of decreasing the tree depth is to balance the tree. Here we provide a procedure under which trees can achieve balance and cycles can be eliminated. Suppose SingleTreeAdjust(u,v) runs whenever node u samples node v as a target.
Procedure SingleTreeAdjust (Node u, Node v) Output: return true if (V, E) changes, return false otherwise. Tie broken: arbitrarily If there exists i such that u, v both have incoming i-links, Procedure SingleTreeAdjust applies the information of buffered depths, which is updated periodically but may have estimation errors. Analyzing SingleTreeAdjust under depth updating is quite challenging. To focus on properties of SingleTreeAdjust, let us temporarily assume Assumption 5 holds. Discussion under the case wihout Assumption 5 will be covered by simulation in Section V. The following lemma shows that SingleTreeAdjust can return true unless all trees achieve balance.
SingleTreeAdjust(u,v) returns true. Thus, depths of any two i-leaves differ by at most one.
3) If u is an i-internal node, it cannot be an i-leaf because of 2), and it cannot be available otherwise SingleTreeAdjust(v,u) returns true where v is the i-leaf with the largest depth to i.
Intuitively running GreedyTreeCover and SingleTreeAdjust together can achieve both coverage and balance, as well as eliminate cycles. However, balance in a tree does not garantee the tree has small depth. As shown in Figure 7, if there are many nodes with a single outgoing i-link, chains may appear and thereby the depth of tree (V i , E i ) can be large. Fortunately, there exists ways to eliminate conditions like that, as shown in the following.

D. Achieve balance among trees
Nodes with a single child play an important role in increasing the depth of a tree. An unavailable node u with a single i-child for certain i ∈ R either haved u = 1 or is a mixed node. The case thatd u = 1 is less interesting because most nodes can be required to provide at least two outdegrees, especially when the streaming rate of a substream is small comparing to the upload capacity. Suppose Assumption 6 holds for simplicity.
Notice that in Assumption 6 existence of nodes with outdegree zero is allowed. Assumption 6 gets rid of the case in E i , and return true. Otherwise return false. (See Figure 8) MixedNodeAdjust(u c ,v) returns true if after "MixSwap", between u c and one child of v, one can decrease its depth while the other one's depth does not increase, or depths are unchanged but parents with lower ids can get outgoing links with lower colors. We break the tie by assuming parents with lower ids have a preference on links with lower colors, so as to eliminate the case that there are many mixed nodes with exactly the same depths in multiple trees.
Under Assumption 5, for any pair of nodes u, v, after MixedNodeAdjust(u,v) runs, 1) statements in Assumptions 1 to 4 remain valid if they are valid before running. 2) L i (w) is nonincreasing for any node w, 3) no new cycle is generated. Moreover, the following lemma indicates that MixedNodeAdjust can return true unless depth vectors of mixed nodes form a strict chain: Lemma III.4. Under Assumption 5, if MixedNodeAdjust(ū,v) returns false for all pairs of nodesū,v ∈ V , for any i, j ∈ R and any two mixed-i-j-nodes u, v, either (L i (u), L j (u)) < Proof. The lemma follows by noticing that if u, v are both mixed-i-j-nodes, "MixSwap" can happen when either a child of u contacts v or a child of v contacts u, unless (L i (u), L j (u)) and (L i (v), L j (v)) are in a strict order.
Lemma III.4 still does not guarantee that the number of mixed nodes is small. As shown in Figure 7, mixed nodes can form a long chain where the conclusion in Lemma III.4 still holds. However, the appearances of the structure in Figure 7 are quite rare because random sampling is assumed. And intuitively it becomes rarer as N increases. In practice we may safely ignore it, but here for completeness of analysis, we eliminate the possibility of a long chain as in Figure 7 by assuming Assumption 7 holds. We will show later by simulation that ignoring Assumption 7 does not harm performance.
Assumption 7 (Shower head). At time 0, there exists c ∈ Z + such that for each i ∈ R, there are at least M i-leaves in Lemma III.5. Under Assumptions 1 and 5 to 7, if SingleTreeAdjust(u,v) and MixedNodeAdjust(u,v) both return false for all u, v ∈ V , then for each i ∈ R the depth of each tree (V i , E i ) is less than or equal to log 2 (N + 1) + c, where c is defined in Assumption 7.
Proof. Suppose the depth of tree (V i , E i ) isl i . Lemma III.4 tells that for each j = i and for each k ≤l i , there are at most one mixed-i-j-nodes whose depth to i is k. So there are at most M − 1 mixed nodes which have i-child and whose depth to i is k. Lemma III.3 tells that all i-internal nodes must have at least 2 children because they are unavailable and because Assumption 6 holds.
Thus, for each k ≤l i − 2, in the set of nodes whose depth to i is k, at most M − 1 of them can have a single i-child, while each of the other nodes has at least 2 i-children because they are unavailable non-mixed i-internal nodes.
Notice that there are at least M nodes whose depth to i is c. Thus, the number of nodes whose depth to i is in [c,l i −1] is at least 1+2+4+...+2l i−1−c ≤ N , sol i ≤ log 2 (N +1)+c.

E. Combine everything together
Here we combine all parts above together. For each pair of nodes u, v, run CombinedUpdate(u,v) when u samples v.
Procedure CombinedUpdate (Node u, Node v) Output: return true if (V, E) changes, return false otherwise. Tie broken: arbitrarily Nodes u, v update their buffered depth by running DepthUpdate for each i ∈ R respectively return GreedyTreeCover(u, v) or SingleTreeAdjust(u, v) or MixedNodeAdjust(u, v) Just like that in C or C++, in CombinedUpdate, if operation "A" returns true, operation "A or B" immediately returns and operation "B" does not run.
Notice that buffered depths are also updated whenever new links are built, as assumed in Section III-A. And Notice that under Assumption 5, for any pair of nodes u, v, after CombinedUpdate(u,v) runs, statements in Assumptions 1 to 4, 6 and 7 remain valid if they hold before running, respectively.
Lemma III.6 shows that by running CombinedUpdate certain metric changes monotonely. Some additional definitions are necessary before defining the metric. Define L i (u) = min{L i (u), N }, i.e., L i (u) is the same as L i (u) except that Proof. Notice that statements in Assumptions 1 to 3, 6 and 7 are valid over all time. Lemma III.6 and the boundness of |E|, Y and S tell that in finite time CombinedUpdate will return false whenever any two nodes meet. Lemma III.1 tells that (a) is valid while Lemma III.5 tells that (b) is valid.

F. Comment on distributed depth update
Under Assumption 5, no new cycles can appear by running CombinedUpdate, which is not the case when depths are updated distributedly. Here we argue that cycles are rare and can be eliminated quickly even if Assumption 5 does not hold.
First, a new cycle appears only if a node builds an incoming link from one of its descendants, which happens only if the descendant has a smaller buffered depth. That condition is rare because 1) most nodes just have several descendants; 2) if u is a descendant of v and if the depth of u is larger than the depth of v, by running SingleTreeAdjust and MixedNodeAdjust the depth of u can remain larger than that of v. Usually a node has smaller depth than its ancestors only when many nodes suddenly become ancestors of the node in a short time, which is also a rare event.
Second, even if a new cycle appears, it will disappear in a short time. By DepthUpdate, depths of nodes in a cycle keep updating and can count to a large value, just like the "counting to infinity" problem in network routing. Whenever a node with a large depth meets a leaf node, changes as shown in Figure 6 can happen and thereby the cycle disappears. At least half of the nodes in a tree are leaves, so by random sampling, cycles are eliminated quickly.
In summary, we argue that distributed depth update does not harm performance much compared to that under Assumption 5, which is supported by simulations in Section V.

IV. RATE OF CONVERGENCE
Analyzing the convergence time of running CombinedUpdate is highly challenging. This section provides a stochastic bound for the convergence time under the case of a single tree, i.e, M = K = 1. We further assume that each node has outdegree at least 2, i.e.,d u ≥ 2 for all u ∈ V . And suppose Assumption 5 holds so that each node knows its depth to the root. For theoretical tractability, instead of running Com-binedUpdate, we simply the algorithm by assuming that only "Add" in GreedyTreeCover and "Jump" in SingleTreeAdjust run when two nodes meet.
The simplified model is summarized as follows: each node knows its depth to the root; whenever a node's Poisson clock ticks, the node samples a target uniformly at random, if the target is available and the depth of the target is less than the depth of the node by at least two, the node removes its current incoming link if there is and builds a new incoming link from the target; otherwise nothing happens. Assume initially each node has at most one incoming link, then convergence time is upper bounded: Proposition IV.1. Let T be the first time for the maximum depth of all nodes to be bounded up by log 2 (N + 1) , then Notice that the maximum depth is +∞ if there is a node to which no path exists from the root. So Proposition IV.1 bounds the time for the tree to cover all nodes and achieve balance. It implies that the model converges in O(log N ) time.
We argue that for the case of multiple trees similar bounds as in Proposition IV.1 can be generated, and by running CombinedUpdate the network can converge in O(log N ) time. Because when targets are unavailable, "LeafSwap" substitutes "Jump" efficiently since half nodes are leaves, and "Insert" substitutes "Add" as well.
The proof of Proposition IV.1 is provided below.
A. proof of Proposition IV.1 We assume nodes sample targets randomly at times of Poisson processes with rate 1. Equivalently, we can assume that each node, node pair maintains a Poisson clock which ticks at rate 1 N . The following definitions are applied for the proof. Define Z i , i ≥ 0 to be the number of nodes with depths ≤ i. Note that Z i (t) is a discrete counting process. Define The model describes a Markov process with state being G = (V, E). We apply G = (V, E) to denote the process as well as the graph. It is not difficult to see that graph G = (V, E) can converge to a balanced tree covering all nodes in finite time, because 1) the depth of each node is nonincreasing, i.e., Z i for each i is nondecreasing, and 2) there exist nodes which can decrease their depths if (V, E) is not balanced or (V, E) does not cover all nodes.
The process is separeted into two phases, illustrated by Lemmas IV.2 and IV.4, respectively. The time for the first phase is described below.
Lemma IV.2. For any α ∈ (0, 1), let T 0 be the first time that Proof. Define an alternative process G = (V , E ) such that it is identical to the original process G when t < T 0 ; when t ≥ T 0 , whenever a node with depth > l α changes its depth, a new node with fan-out degree 2 whose depth is ∞ arrives to G . After T 0 , |V | may increase but we assume the Poisson clock of each (node, node) pair still ticks at rate µ = 1/N . On G , the number of nodes with depths > l α does not change after T 0 , and always ≥ αN . The probability P [t < T 0 ] is identical for processes G or G . In the following, our discussion are on process G . For simplicity, we apply the same notations for G as for G. Let Z = (Z 0 (t), Z 1 (t), ...Z lα (t)).
Notice that the number of available nodes with depths ≤ i is larger or equal to (1 + 2Z i−1 − Z i ) + /2: consider each node labels its outgoing degrees and marks the first two degrees red. Each node has at least 2 red degrees but there are only Z i − 1 nodes to serve. So there are at most (Z i − 1)/2 nodes whose red degrees are both taken. The number of nodes with depths > l α is larger or equal to αN . Thus, if i ≤ l α , the transition rate for Z i to jump is lower bounded by There exists a processZ = (Z 0 (t),Z 1 (t), ...Z lα (t)) in Z lα+1 + on an extended probability space such that each coordinate ofZ has jumps of size one and jump rate forZ i is α(1+2Z i−1 −Z i ) + /2. Notice that simultaneous jumps of different coordinates ofZ are allowed. LetZ(0) = (1, 1, 1, ...1). Initially we have Z(0) ≥Z(0).
Process Z andZ can be coupled so that Z(t) ≥Z(t) with probability one for all t. That is because if Z ≥Z then jump rate of Z i is larger or equal to jump rate ofZ i for all i such that Z i =Z i . So the jumps ofZ can be obtained by generally thinning the jumps of Z, and adding more jumps toZ i 's with Z i >Z i . By induction it is easy to show thatZ i (t) ≤ 2 i+1 − 1 with probability one for all t, because jump rate ofZ i is zero if Let y(t) = (y 0 (t), y 1 (t), ...y l f −1 (t)) to be a motion trajectory defined by the following linear differential equation: By induction it is easy to prove that, Notice that ∆(t) ≥ 0, apply Markov's inequality and Lemma IV.3, The lemma follows.
Lemma IV.3. Let y(t) = (y 0 (t), y 1 (t), ...y k (t)) to be a motion trajectory defined by the following: where β > 0 is a constant, then Proof. Let δ i (t) := 2 i+1 − 1 − y i (t/β) /2 i+1 , we can simplify the equation of y as Notice that by induction we can show that δ i (t) ≤ θ i (t), where Solving the differential equation about θ gives that and so the lemma follows.
The time of the second phase is described below.
Lemma IV.4. For any α ∈ (0, 0.5), given Z lα (0) ≥ (1−α)N , let T 1 be the first time that Z lc+1 = N , then Proof. Let X i be the number of nodes with depths = i, and let Y i be the number of available nodes with depths ≤ i. Consider the jumping rate of Z lc+1 . Notice that Z lα (t) ≥ (1 − α)N , and The last inequalities above is due to the fact that lc+1 k=lα+1 X k ≤ αN . The rate for any node with depth > l c + 1 to jump to join Z lc+1 is at least µY lc ≥ (1−2α)/2. So the lemma follows. Now Lemmas IV.2 and IV.4 are combined to prove Proposition IV.1. Consider Lemma IV.2, apply the Chernoff bound for Poisson variable: Consider Lemma IV.4:

V. SIMULATION
We show that CombinedUpdate works pretty well under Assumptions 1 to 3 and 6, without Assumptions 4, 5 and 7. Let each node sample targets randomly with rate µ = 1 and run CombinedUpdate. Assumption 5 is not invoked so depths update distributedly. Notice that CombinedUpdate runs instantaneously in simulations. In each experiment below, we set N = 1000 fixed; at time 0, we first set E to be empty, then let each root i build an i-child which is randomly selected from V \ R. So at time 0 E contains |R| links and Assumptions 1 and 3 both hold. We let Assumptions 2 and 6 hold too.
Because Assumption 1 holds, during each simulation below (V i , E i ) for each i is always a tree. Tree i is given by Say that a node is covered by tree i if L i (u) < +∞, and say that a node is fully covered if it is covered by at least K trees.
In experiments below, the parameters chosen include K, M and the degree vector (d u ) u∈V . For each selection of parameters K, M, (d u ) u∈V , we repeat running the experiment 500

A. Homogenous degrees and tight capacity constraint
In this series of experiments, we let each root have degree K − 1: ∀i ∈ R,d i = K − 1, and let each non-root node have degree K: ∀u ∈ V \ R,d u = K. The capacity is tight because the equality in Assumption 2 is achieved: u∈Vd u = KN −M . Keep K ≥ 2 so Assumption 6 holds. After repeating an experiment for 500 times, for a = 0.2, 1, 5, 50, 100, we record metrics of the a% worst experiment at each time t. Notice that each line with legend "worst case" correponds to the case a = 0.2, which means that there is no experiment performing worse than the line at any time. (0.2% * 500 = 1).
For example, in Figure 9 we set M = K = 2. A point (t, y) in Figure 9a on the line with legend "5%" means that in 5% of 500 repeated experiments, the fraction of nodes fully covered at time t is no larger than y; a point (t, y) in Figure 9b on the line with legend "1%" means that in 1% of 500 repeated experiments, the max tree depth at time t is no less than y. Figure 9 shows what a specific sample path looks like under CombinedUpdate. In Figure 9a, we can see that the fraction of nodes fully covered increases almost exponentially from 0 to 1, over 90% nodes are fully covered by time 25 under 99% experiments. That is because nodes can gradually increase the number of trees covering them until they get fully covered, as they meet other fully covered nodes. It appears that the fraction of nodes is almost nondecreasing over all time, which validates that cycles generated are rare and are quickly eliminated. As indicated in Figure 9b, the maximum tree depth increases linearly in the beginning, then decreases almost exponentially, and finally converges to below 12. At time 25, in 99% repeated experiments max tree depths are below 20. The rate of convergence follows Proposition IV.1, though Proposition IV.1 is for the case of one tree.
Notice that not only in Figure 9, but also in all our simulations below, the "worst case" lines are quite close to the "1%" lines, but the latters are much more smooth than the former. In the following, we apply "1%" lines instead of "worst case" lines to describe performance. In Figure 10 we test different K's so as to make sure convergence follows in other cases. Notice that typically in practice K is below 10. Set M = K with K varying in {2, 3, 6, 10}. We expect to observe similar images as in Figure 9, with longer convergence time as K increases because each node has to get covered by more trees. For each K, we draw the 1% worst case line in Figure 10. As expected, for each K both the fraction of nodes fully covered and the max tree depth converge, as in Figure 9. In Figure 10a, lines shift right almost linearly with a slow rate as K increases. With K = 10, over 90% nodes are fully covered by time 40. In Figure 10b, lines shift both downwards and right, and converge to lower values as K increases. Because balanced trees have smaller depth if nodes have larger degree: with K = 10, the line converges to 4 in Figure 10b. Whatever K is, the max tree depth is below 20 by time 25.
In Figure 11, we test the case under source coding by drawing the 1% worst case lines when K = 3 and M be in {3, 4, 9}, that is, there are more trees than nodes need. Notice that the capacity is still tight. In Figure 11a, lines shift left as M increases, showing that source coding tends to decrease the convergence time for coverage. In Figure 11b, limits slightly increase as M increases. Because when M is larger there are more types of mixed nodes, which may have single children in a tree and thereby increase the depth. That condition is also implied by Proposition III.7, where the value c is considered to be of O(log M ). Thus, source coding creates a tradeoff between the tree depth limit and the convergence time of coverage. Intuitively and as shown in Figure 11b, the increasing of depth limit is of O(log M ) which is small, so it is worth trying source coding to get a faster convergence.
For all simulations above, we test cases where the capacity is tight, which illustrates Proposition III.7 and supports that convergence is exponential. One common feature of curves  in Figures 9a to 11a is that long tails exist. For example, in Figure 11a, it takes quite long for curves to arrive at 1. That is because near the end of the process only a few nodes are available and a few others are not fully covered, and it takes long for these nodes to meet each other by random sampling. Long tails can be eliminated by broadcasting or adding more capacity. Broadcasting is not discussed in this paper, in the following we show experiments where extra capacity exists.

B. Loose capacity constraint eliminates the long tail
We set the total number of degrees u∈Vd u = (1+α)N K, with a new parameter α. To achieve that, we first let each node have degree K, then add αN K degrees, one by one, to nodes selected uniformly at random. In Figure 12, we set M = K = 2, and let α increase. In Figure 12a, we can see that adding just 10% extra capacity can greatly shorten the tail: all nodes are fully covered by time 25 as shown by the line α = 0.1. The larger α is, the shorter the tail is. When α = 1.0, all nodes get fully covered by time 15. In Figure 12b, as α increases, curves converge faster and limits also decrease.

C. Polarized degrees for the server-client case
In this section, we show that CombinedUpdate works well under the server-client case, where a portion of nodes are server nodes with high degrees and other nodes are client nodes with zero degrees. The algorithm favors nodes with higher degree; they tend to get smaller depths than nodes with lower degrees. We expect to observe similar images as in Figure 9. Notice that the convergence times will increase because it takes more time for nodes to meet server nodes under uniform random sampling. That problem can be solved by adding mechanisms to help nodes find server nodes. In this paper, we stay focused on the uniform sampling assumption despite the small increase in convergence time.
In Figure 13, we let N/r server nodes (include roots) have degree rK and all other nodes have degree 0, then add αN K degrees one by one to server nodes randomly. As expected, in Figure 13a, lines shift right as r increase because there are less server nodes, but still increases exponentially from 0 to 1. In Figure 13b, max tree depth decreases greatly as r increase from 1 to 2, and further decreases as r increase. In Figures 13c  and 13d, r is fixed at 2 with α increases, which shows long tails get eliminated like that in Figure 12.
In Figure 14, we let 1+α r N server nodes (include roots) have degree rK and all other nodes have degree 0. We set r = 2, let α increase, and draw the line at α = 0, r = 1 for comparison. Notice that lines at α = 0 in Figures 13 and 14 are exactly the same. As α increases, there are more server nodes so lines shift left quickly in Figure 14a, and max tree depth decreases quickly in Figure 14b. When α = 0.1, r = 2, lines in Figure 14 are close to lines in Figure 13. As α increases, in Figure 14 lines shift left but in Figure 13 they do not. That suggests that performance is sensitive to the number of server nodes instead of the degree distribution among server nodes.
Above all, our simulations validate Propositions III.7 and IV.1 by showing that fraction of nodes fully covered increases from 0 to 1, and the maximum tree depth decreases to its limit, almost exponentially, under tight or un-tight capacity constraint, homogeneous or heterogeneous capacity distribution, when Assumptions 1 to 3 and 6 hold. The simulations suggest that cycles are eliminated quickly because the fraction of nodes covered is almost increasing over all time; long tails can be eliminated by adding 10% extra capacity; and the algorithm favors nodes with higher degree so it works well under the server-client case too. Convergence times increase with either increasing K or decreasing the chance for nodes to meet server nodes. When parameters change, curves shift with shapes staying similar, revealing robustness of the algorithm.

VI. CONCLUSION
In this paper a distributed algorithm to manage multiple trees for streaming is proposed. The algorithm can achieve coverage, balance, and small delay in a short time. The algorithm works on a complete underlying graph assuming random sampling among peers is enabled. Future work may include extending the algorithm for given incomplete underlying topologies.

VII. ACKNOWLEDGMENTS
This work was supported by the National Science Foundation under Grant NSF CCF 10-16959.