On Matrix Factorization and Scheduling for Finite-Time Average-Consensus Citation Ko, Chih-Kai (2010) On Matrix Factorization and Scheduling for Finite-Time Average-Consensus. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/GCT7-5Y66. https://resolver.caltech.edu/CaltechTHESIS:05022010-193157687 Abstract We study the problem of communication scheduling for finite-time average-consensus in arbitrary connected networks. Viewing this consensus problem as a factorization of 1/n 11 T by network-admissible families of matrices, we prove the existence of finite factorizations, provide scheduling algorithms for finite-time average consensus, and derive almost tight lower bounds on the size of the minimal factorization. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Finite-time average-consensus, matrix factorization, resource allocation, scheduling, algorithm Degree Grantor: California Institute of Technology Division: Engineering and Applied Science Major Option: Electrical Engineering Thesis Availability: Public (worldwide access) Research Advisor(s): Schulman, Leonard J. Thesis Committee: Schulman, Leonard J. (chair) Doyle, John Comstock Ho, Tracey C. Low, Steven H. Umans, Christopher M. Defense Date: 5 January 2010 Record Number: CaltechTHESIS:05022010-193157687 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:05022010-193157687 DOI: 10.7907/GCT7-5Y66 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 5763 Collection: CaltechTHESIS Deposited By: Chih-Kai Ko Deposited On: 21 May 2010 15:55 Last Modified: 07 Jun 2023 17:29 Thesis Files Preview PDF - Final Version See Usage Policy. 1MB Repository Staff Only: item control page

On Matrix Factorization and Scheduling for Finite-time Average-consensus Thesis by Chih-Kai Ko In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 2010 (Defended January 5, 2010) ii c 2010 Chih-Kai Ko All Rights Reserved iii Acknowledgements First and foremost, I would like to thank my advisor, Professor Leonard J. Schulman. This thesis would never have existed without his support, inspiration, guidance, and patience. To him, I offer my most sincere gratitude. In addition, I am grateful to my thesis committee members: Professors John Doyle, Tracy Ho, Steven Low, and Chris Umans for their helpful inputs and suggestions. I am particularly indebted to my whole family: my dad, Jin-Wen Ko, my mom, Chu-Chih Li, and my sister, Mon-Lin Ko, for their love and encouragement; especially my parents, who have always been there to offer their guidance and support. I owe a lot to my dear wife, Xiaojie Gao, who has helped me in countless ways and provided constructive criticism and suggestions in research. I feel very fortunate to have met her at Caltech. I would also like to acknowledge my 2.5 week old1 daughter, Kailin, whose arrival brought much joy and chaos into our lives2 . I also want to acknowledge Sidharth Jaggi, my first year roommate at the Braun Graduate House in Caltech. As a more senior graduate student, Sidharth helped me tremendously in getting adjusted to the rigors of Caltech. He is a great friend, roommate, and mentor. His research guidance played a crucial role in my National Science Foundation Graduate Fellowship award. I would also like to acknowledge the National Science Foundation for providing me with financial support to pursue my graduate studies. Their support helped me continue with my Ph.D. studies. I would like to thank my colleagues and friends whom I met at JPL, especially Scott Darden, Clement Lee, Andrew Gray, and Winston Kwong. They are truly 1 Kailin was 2.5 weeks old at the time of the thesis defense. I am very glad that I listened to my wise advisor when he warned me against scheduling my thesis defense one week after my daughter’s due date. 2 iv wonderful friends, and spending time with them helped relieve the stresses of Caltech life. I am happy to say that I now have a more definite response to their most frequent question: “Hey man, when are you going to graduate?” I would also like to thank my JPL supervisors, Clayton Okino and Norm Lay, for the opportunity and privilege to work at JPL. At JPL, I learned many new technologies and more importantly, I gained some great friends. Lastly, I would like to give thanks to God. It is by the grace of God that I am able to pursue my graduate education at such a prestigious institution. I feel challenged and humbled everyday working with and learning from people who are much smarter than I am. I thank Him for the many blessings throughout the years and I give Him credit for my accomplishments. v Abstract We study the problem of communication scheduling for finite-time average-consensus in arbitrary connected networks. Viewing this consensus problem as a factorization of n1 11T by network-admissible families of matrices, we prove the existence of finite factorizations, provide scheduling algorithms for finite-time average consensus, and derive almost tight lower bounds on the size of the minimal factorization. vi Contents Acknowledgements iii Abstract v 1 Introduction 1 1.1 Consensus Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 An Example with Milk and Cookies . . . . . . . . . . . . . . . . . . . 2 1.3 Averaging in Wireless Sensor Networks . . . . . . . . . . . . . . . . . 3 1.4 Basic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.6 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Related Work 12 3 G-admissible Factorization 14 4 5 3.1 Pairwise Exchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 G-admissible Factorization . . . . . . . . . . . . . . . . . . . . . . . . . 17 Factorization under Additional Constraints - Pair-wise Averages 20 4.1 Information Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 Necessary Condition for Finite-time Consensus . . . . . . . . . . . . . 23 4.3 Consensus on the Boolean Hypercube . . . . . . . . . . . . . . . . . . 24 Factorization under Additional Constraints: Pair-wise Symmetric Weighted vii Averages 5.1 Matrix Insights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2 Consensus Algorithms for Trees . . . . . . . . . . . . . . . . . . . . . . 30 5.3 Lower bound on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.4 Consensus Time on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5 General Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.5.1 5.6 6 27 Graph Lower bound . . . . . . . . . . . . . . . . . . . . . . . . 42 Metric Space Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . 44 Factorization under Additional Constraints - Parallel Symmetric Weighted Averages 7 47 6.1 ∗ = O(n) . . . . . . . . . . . . . . . . . . . . . . . . 48 Upper bound: TG∩S 6.2 ∗ = Ω(n) . . . . . . . . . . . . . . . . . . . . . . . . 56 Lower bound: TG∩S Discussion and Extensions Bibliography 58 60 1 Chapter 1 Introduction 1.1 Consensus Problems In a consensus problem, a group of agents (or network nodes) try to reach agreement on a certain quantity of interest that depends on their states [29]. Consensus problems arise in diverse areas such as oscillator synchronization [32, 31], flocking behavior of swarms [42], rendezvous problems [2, 18, 26], multi-sensor data fusion [35], multi-vehicle formation control [16], satellite alignment [3, 28], distributed computation [25], and many more. When the objective is to agree upon the average, it is an average-consensus problem. A motivating example (from [5]) is a network of temperature sensors needing to average their readings to combat fluctuations in ambient temperature and sensor variations. Many efficient algorithms exist under various settings, e.g., [13, 9, 5, 7, 22]. Although the majority of the proposed algorithms offer rapid convergence, in general, many cannot guarantee consensus in finite time. In this thesis, we study algorithms that achieve average-consensus in finite time for arbitrarily connected networks under various constraints. We view the network consensus problem as a network commodity redistribution problem. To make these ideas concrete, we begin with an example. 2 1.2 An Example with Milk and Cookies Consider n children going to school, each equipped with a backpack of unit capacity. The children fill their backpacks with a combination of milk and cookies. If a child brings x units of milk (0 ≤ x ≤ 1), then the backpack also contains 1 − x units of cookies. At school, they sit in an assigned seating arrangement. Once seated, the children begin to exchange milk and cookies amongst themselves in hopes that everyone has the same share of milk and cookies at the end of the exchange process. The exchange process is subject to the following constraints: • (Proximity Communication) Because we don’t want children wandering in the classroom, each child can only exchange with someone seated in close proximity. • (Serial Communication) Because we want to maintain order, at most one pair of children can exchange their goods at any given time. • (Proportional Fairness) Because we want to maintain fairness, the exchanges must be proportionally fair. That is, if Alice gives Bob 10% of everything she has, then Bob must give Alice 10% of what he has. Our role as the teacher is to devise a sequence of pairwise exchanges (i.e., a schedule) so that at some finite time, say T , all the children have equal shares of milk and cookies. Furthermore, we require that our schedule achieve even distribution regardless of initial conditions. That is, our schedule can only depend on the seating configuration and not on the initial quantities of milk and cookies brought by the children. Using symbols, we now make this problem more precise. Let xi (t) denote the amount of cookies possessed by child i at time t. Initially, at time t = 0, each i-th child brings xi (0) units of cookies and 1 − xi (0) units of milk in his/her backpack where 0 ≤ xi (0) ≤ 1. 3 We assume that the total quantity of milk and the total quantity of cookies are non-zero. That is, someone has brought some cookies to school and someone has brought some milk to school: 0< n X xi (0) < n. i=1 After following our schedule, we desire that at some finite time T ≥ 0, we have for all i, n 1X xi (T ) = xj (0) n j=1 for all initial values of xj (0). That is, our schedule must lead to finite-time averageconsensus regardless of what quantity of goods each child has brought to school. The seating arrangement is represented by a connected undirected graph G = (V, E) with n nodes where V = {1, 2, . . . , n}. The i-th child is seated at node i. If (i, j) ∈ E, then we say that i and j are neighbors in G. The proximity constraint dictates that each child can only exchange goods directly with his/her neighbor in the graph. The fairness constraint requires that if neighbors i and j exchange their goods at time t then xi (t + 1) = λt xi (t) + (1 − λt ) xj (t), xj (t + 1) = (1 − λt ) xi (t) + λt xj (t). Here, λt (0 ≤ λt ≤ 1) represents the proportion of goods exchanged at time t. It shall be useful to view the exchange process as a weighted-averaging operation between two students. 1.3 Averaging in Wireless Sensor Networks At this point, we can draw an analogy with wireless sensor networks. Instead of children and snacks, imagine a deployment of n wireless temperature sensors in 4 an area. These sensors measure the local temperature, establish a communication network, then run an averaging protocol to average their readings so that at some time T , we can query any sensor to get the exact global average temperature. In this setting, we run into similar constraints: • (Proximity Communication) Sensors are typically power-constrained, so they can only communicate with other sensors in close proximity. • (Serial Communication) To minimize communication interference, we may only want one pair of sensors to communicate at any given time. The proportional fairness constraint from our classroom example does not have an exact analogy here. In a typical sensor network, the quantity that is exchanged is information. We can do much more with information than we can with a physical commodity: we can use source coding to decrease redundancy, channel coding to increase robustness, and network coding to increase throughput. In a commodity distribution network, we cannot do such coding operations on physical goods. We are often limited by local capacity constraints (e.g., unit-capacity backpacks in the children example). 1.4 Basic Notation Although most of the material in this thesis is self-contained, we will make use of elementary knowledge of graph theory, linear algebra, and algorithms. We refer readers unfamiliar with these areas to [14], [36], [10], as basic references to graph theory, linear algebra, and algorithms, respectively. Before we venture into the problem formulation in its full generality, we need to establish some basic notations: • G = (V, E) denotes a connected undirected graph on n vertices with vertex set V and edge set E ⊆ V × V . For convenience, we sometimes write v ∈ G to denote a vertex v from the vertex set V of graph G. 5 • Given a graph G and two vertices u, v ∈ G, we write ∆(u, v) to denote the distance between nodes u and v. That is, ∆(u, v) is the length of the shortest simple path between u and v. • Given a graph G, we define its diameter, DG , as DG = max ∆(u, v), u,v total its pairwise total distance, DG , as total DG = 1 XX ∆(u, v), 2 u∈G v∈G its pairwise average distance, D̄G , as D̄G = total DG
, n 2 and its median, µG , as µG = arg min u∈G X ∆(u, v). v∈G When the underlying graph is clear from the context, we omit the subscript G and simply write D, Dtotal , D̄, and µ to refer to its diameter, total distance, average distance, and median, respectively. • A tree is a graph without cycles. That is, any two vertices in the tree are connected by exactly one simple path. • A spanning tree T of G is a subgraph that is a tree and contains all vertices of G. • R ,Q, and N denote the set of real, rational, and natural numbers, respectively. • Given functions f and g, we write f (n) = O(g(n)) if there exist positive constants c and n0 such that 0 ≤ f (n) ≤ c g(n) for all n ≥ n0 . 6 • Given functions f and g, we write f (n) = Ω(g(n)) if there exist positive constants c and n0 such that 0 ≤ c g(n) ≤ f (n) for all n ≥ n0 . • Given functions f and g, we write f (n) = Θ(g(n)) if f (n) = O(g(n)) and f (n) = Ω(g(n)). • Boldface 1 ∈ Rn denotes a column vector of all 1’s. • I ∈ Rn×n denotes the n × n identity matrix. • ei ∈ Rn is an unit vector with 1 in the i-th coordinate and 0’s in other coordinates. • Given a matrix M , M T denotes its matrix transpose. • For a sequence of T square matrices {W (0), W (1), W (2), · · · , W (T − 1)} , where W (t) ∈ Rn×n for 0 ≤ t < T , we write T −1 Y QT −1 t=0 W (t) to denote the product W (t) = W (T − 1) · W (T − 2) · · · W (0). t=0 We will also need the notion of G-admissible matrices: Definition 1.1. Given a graph G = (V, E), we say a matrix W ∈ Rn×n is G-admissible if 1. (Conservation) W is column stochastic: Wij ≥ 0 for all i, j; 1T W = 1T ; and 2. (Connectivity) For i 6= j, Wij = 0 if (i, j) ∈ / E. With slight abuse of notation, we write W ∈ G if W is G-admissible; and S ⊆ G to denote that S is a subset of G-admissible matrices. Loosely speaking, a G-admissible matrix performs averaging according to the topology specified by G. Notice that the proximity communication constraint is implicit in the definition. 7 1.5 Problem Statement Given a connected undirected graph G = (V, E), imagine vertices V as nodes in a network connected according to E. For each node i ∈ V , let xi (t) denote the value of node i at time step t. Define x(t) = [x1 (t), x2 (t) · · · , xn (t)]T . Given any set of initial values x(0), we are interested in a finite sequence of weighted-averaging operations, W (t) ∈ G, that allows all nodes to reach average-consensus in finite time T , i.e., x(T ) = n1 11T x(0). Expressed as a linear dynamical system, the values in our network evolve as (1.1) x(t + 1) = W (t) x(t) with W (t) ∈ G. The G-admissibility requirement limits our averaging operations to those that are consistent with the network topology. Ultimately, we desire a finite sequence of G-admissible matrices W (0), · · · , W (T − 1) such that x(T ) = T −1 Y W (t) x(0) = t=0 1 T 11 x(0) n for all x(0) ∈ Rn . The requirement that the sequence of G-admissible matrices results in average-consensus for all x(0) ∈ Rn suggests a matrix factorization perspective to finite-time average-consensus. This is made precise by the following lemma: Lemma 1.2. Let W (0), W (1), · · · , W (T − 1) ∈ Rn×n be a finite sequence of T matrices, then W (T − 1)W (T − 2) · · · W (0) = n1 11T iff W (T − 1)W (T − 2) · · · W (0) x(0) = 1 T 11 x(0) n (1.2) for all x(0) ∈ Rn . Proof. The “only if ” direction is clear, so we show the “if ” direction. Let ei denote an unit-vector in Rn with 1 in the i-th coordinate. If we take x(0) = ei , then equation 8 (1.2) becomes 1 1 = W (T − 1)W (T − 2) · · · W (0) ei . n So the i-th column of the product W (T − 1)W (T − 2) · · · W (0) must be n1 1 for any i and the lemma follows. To characterize the fastest consensus time (i.e., minimal factorization) we define the following: Definition 1.3. Given a set of matrices S ⊆ Rn×n , define ( T −1 Y 1 W (t) = 11T TS∗ , min T : ∃W (t) ∈ S with n t=0 ) when it exists. When such a finite factorization does not exist, we define TS∗ = ∞. For convenience, we write TG∗ when S is the set of G-admissible matrices. Thus, TG∗ is the minimum consensus time. In this thesis, we shall address the following problems: • (Existence) Given G, does there exist a sequence of W (t)’s such that TG∗ is finite? • (Algorithm) How can we find a G-admissible factorization, if it exists? • (Minimality) If it exists, what is the minimal of such factorization? As it turns out, the set of G-admissible matrices may be too general in the context of network consensus problems. Some scenarios, such as the classroom example in Section 1.2, require additional constraints that further restrict the factors to certain subsets of G-admissible matrices. In addition to connectivity and conservation constraints imposed by G-admissibility, networked nodes may act synchronously or asynchronously, nodes may be power-constrained, and nodes may have different levels of knowledge or computation power. Each of these restrictions further constrain the factors of n1 11T to specific subsets of G-admissible matrices in the context of consensus problems. 9 Definition 1.4. Given a graph G on n vertices and a set S ⊆ Rn×n of matrices, we define  S ∩ G = W ∈ Rn×n : W ∈ S and W ∈ G . Many existing consensus algorithms correspond to factoring n1 11T using S ∩ G with differing S. For example, it may be desirable to factor n1 11T using doubly stochastic matrices: W (t) ∈ {W : W 1 = 1 and W ∈ G} so the average is a fixed point of iteration (1.1); i.e., n1 11T x(0) = W (t) · n1 11T x(0) for all t. In this thesis, we shall explore the following specific subsets of G-admissible matrices: • (Pairwise Exchanges) Factorization using W (t) ∈ G ∩ P1 where P1 , {W : |{i : Wii 6= 1}| ≤ 2} . That is, we restrict each averaging step to a pair of nodes in G. This is similar to the one-child-at-a-time serial communication constraint of Section 1.2. • (Pairwise 50%-50% Exchanges) Factorization using W (t) ∈ G ∩ S10 where S10 ,   (ei − ej )(ei − ej )T : 0 ≤ i, j < n . I− 2 In addition to the proximity and serial communication constraints of Section 1.2, we enforce a 50%-50% exchange where each time two nodes average their values. This restriction also corresponds to the gossip-based asynchronous algorithms, c.f. [5]. • (Pairwise Symmetric Weighted Exchanges) As we will discover shortly, the set G ∩ S10 often fails to admit finite-time average-consensus (i.e., TG∩S10 = ∞ for many graphs G) and we must look beyond G ∩ S10 if we desire a finite factorization of n1 11T . Therefore, we consider the following generalization of 10 S10 :  S1 ,  (ei − ej )(ei − ej )T I− : 1 ≤ m ∈ Q; 0 ≤ i, j < n . m The set S1 allows pair-wise weighted-averages and notice that S10 ⊂ S1 . • (Symmetric Exchanges) Lastly, we consider  S , W ∈ Qn×n : W = W T . Note that the matrices in S are doubly stochastic (i.e., 1T W = 1T and W 1 = 1). The set S allows distribution of mass by symmetric weighted averages; yet disallows aggregation steps such as those matrices in the G-admissible set. Such operations are often impossible under typical network node assumptions (i.e., topology awareness, computational limitations, distributed behavior... etc.) or capacity constraints. 1.6 Contributions Our main contributions are as follows: • We show that any connected graph admits a finite G-admissible factorization of n1 11T and TG∗ = Θ(D), where D is the diameter of the graph. • In the context of gossip-based asynchronous algorithms (e.g., [5]), we provide ∗ necessary conditions for the finiteness of TG∩S 0 . We derive a lower bound on 1 ∗ TG∩S 0 1 = Ω(n log n) and show that it can be achieved when G is the boolean hypercube. • When we are restricted to proportionally fair serial averaging (i.e., one pair of nodes at a time), we exhibit a tree-based algorithm proving
∗ TG∩S = O n log n + n · D̄G . 1 11 • When G is a tree, our algorithm is provably optimal. That is,
∗ TG∩S = Ω n log n + n · D̄ . G 1 • More surprisingly, when G is a general graph, our tree-based algorithm is off by, at most, a polylog factor:
∗ TG∩S = Ω n log n + n log−2 (n) · D̄G . 1 Interestingly, this result implies that using the entire network for averaging can yield, at most, a modest increase in performance. It is an open question whether this O(log 2 n) gap can be eliminated. Since our results are of a centralized nature, our consensus algorithm runtime lower bounds the runtime of any distributed finite-time average-consensus algorithm. 1.7 Organization The rest of the thesis is organized as follows: In Chapter 2, we review the relevant existing literature. In Chapter 3, we show that a G-admissible factorization of n1 11T always exists and that TG∗ = Θ(D), where D is the diameter of G. In Chapters 4, 5, and 6, we study factorization by subsets of G-admissible matrices, G ∩ S10 , G ∩ S1 , and G ∩ S respectively. Finally, we close with potential research directions and concluding remarks in Chapter 7. 12 Chapter 2 Related Work We introduced the finite-time average-consensus problem as a matrix factorization problem to emphasize that we require an exact average in finite time. Much of Q the existing work analyzes asymptotic properties of t W (t) as t → ∞; see, for example, [5, 29, 16]. If we relax our exactness requirement and allow a randomized choice of product matrices, one can define the -average time of distribution D [5] as     kx(t) − n1 11T k Tave (, D) , sup inf PD ≥ ≤ , kx(0)k x(0) where  > 0 and D is a probability distribution on the set of G-admissible matrices, and W (t) are drawn independently from D. The choice of D reflects the behavior of different distributed consensus algorithms. For a trivial D, e.g., pick a W ∈ G with W 1 = 1 and let W (t) = W for all t; the -average time is governed by the second largest eigenvalue of W [29, 16]. Optimization of Tave (, W ) over W can be written as a semidefinite program (SDP) [43], hence solved efficiently numerically. Tight bounds on Tave (, D), when D corresponds to synchronous and asynchronous distributed gossip algorithms, can be found in [5]. For a more comprehensive and detailed overview of convergence behavior of consensus-type problems, we refer the reader to [5, 29, 16] and the references within. Although exponentially-fast convergence is sufficient in many cases, it is sometimes desirable to achieve exact convergence in finite-time. A number of authors have studied finite-time consensus in the framework of continuous-time systems: 13 Cortés [11] employed nonsmooth gradient flows to design gradient-based coordination algorithms that achieve average-consensus in finite-time. Using finite-time semi-stability theory, Hui et al [17] designed finite-time consensus algorithms for a class of thermodynamically motivated dynamic network. Wang and Xiao [41] used finite-time Lyapunov functions to derive finite-time guarantees of specific coordination protocols. In the discrete-time setting, Sundaram and Hadjicostis [38, 37] studied the finitetime consensus problem for discrete-time systems. By allowing sufficient computation power and memory for the network nodes, [38] showed that nodes in certain linear time-invariant systems can compute their averages after a finite number of linear iterations. The basic idea is that of observability from control theory. Given enough time, the nodes will have observed enough to reconstruct the initial state of the system. At which time, they can compute the correct average. Kingston and Beard [20] studied average-consensus problems in networks with switching topologies. Using a special consensus protocol, they showed that if the topology switches to a fully connected graph, then finite-time average-consensus is possible. As consensus problems have and continue to receive wide interest, researchers have considered many model variations. Some popular variations include: quantization [4, 19, 23, 24, 8, 6], switched topologies [30, 27, 40, 44], time delay [30, 33, 39, 45], and routing and node mobility [15, 34, 45]. Our work is most closely related to [22] and [21]. In [22], Ko and Shi examined link scheduling on the complete graph to achieve finite-time average-consensus. They provided necessary and sufficient conditions for finite-time consensus and computed the minimum consensus time on the boolean hypercube. In [21], Ko and Gao introduced the matrix factorization perspective to consensus problems. They provided algorithms for finite-time average consensus and showed worst case graph examples which matched the algorithm runtime. This thesis provides several tight bounds for general graphs and thus subsumes [22] and [21]. 14 Chapter 3 G-admissible Factorization 3.1 Pairwise Exchanges We begin our study with factorization by (G ∩ P1 ) matrices, instead of the Gadmissible factorization, because (G ∩ P1 ) factorization is more easily understood and its algorithm is more straightforward. Since (G ∩ P1 ) ⊆ G, the existence of a (G ∩ P1 ) implies the existence of a G-admissible factorization. Recall the definition of the set P1 : P1 , {W : 1 ≤ |{i : Wii 6= 1}| ≤ 2} . The set G ∩ P1 restricts our averaging operation to one pair of nodes at any given time. This is similar to the one-child-at-a-time serial communication constraint of Section 1.2. To prove the existence of a finite (G ∩ P1 )-admissible factorization of n1 11T , consider Algorithm 3.1. The basic idea of this algorithm is simple: nodes pass all their goods to one fixed “aggregator” node. The aggregator node then propagates the appropriate amount of goods back into the network so that everyone has an equal amount at the end. More specifically, we start with a spanning tree of G and arbitrarily designate a node as the root. After designating the root, we keep track of the number of descendants of each node (including itself) in the n-dimensional vector d. Starting from the leaves of the spanning tree, the algorithm traverses up 15 towards the root. Along the way, each node gives all its goods onto its parent and then removes itself. This process terminates when a only single vertex remains. At this point, the remaining node contains the sum of all initial node values. The second part of the algorithm (Algorithm 3.2) traverses back down the tree while re-distributing the values to achieve average-consensus at termination. The vector d allows us to propagate an appropriate amount of goods to each child node in order to achieve consensus. Algorithm 3.1: G ATHER -P ROPAGATE Input: Graph G, initial values x Output: x ← n1 11T x d ← vector of 1’s indexed by V (G) 2 T ← a spanning tree of G 3 while T is not a single vertex do 4 Pick a leaf v ∈ V (T ) 5 Let e = (u,  v) be   the edge attaching v to T  1 1 xu xu ← 6 xv 0 0 xv 7 du ← du + dv 8 T ← (V \{v}, E\{e}) 9 end 10 Let u ← remaining vertex of T 11 P ROPAGATE (T, u, d) // See Algorithm 3.2 1 Algorithm 3.2: P ROPAGATE Input: T , u, d Output: x ← n1 11T x foreach   neighbor  v of u do xu d − dv ← d1u u xu xv 2 dv 3 E ← E\{(u, v)} 4 P ROPAGATE(T, v, d) 5 du = du − dv 6 end 1 To translate Algorithm 3.1 into a (G ∩ P1 )-admissible factorization, notice that 16 line 6 corresponds to a (G ∩ P1 )-admissible matrix W with     1    Wij = 1      0 if i = j 6= v, if i = u and j = v, (3.1) otherwise. Similarly, line 2 of Algorithm 3.2 corresponds to a (G ∩ P1 )-admissible matrix W with Wij =    (du − dv )/du       dv /du if i = j = u, if i = v and j = u, (3.2) if i = j 6= u,    1      0 otherwise. Thus, one can construct a finite factorization of n1 11T using 2(n − 1) (G ∩ P1 )admissible matrices: n − 1 matrices of type (3.1) followed by n − 1 matrices of type (3.2). Summarizing into a theorem: Theorem 3.1. For any connected graph G = (V, E) on n vertices, there exists a finite ∗ (G ∩ P1 )-admissible factorization of n1 11T . Furthermore, TG∩P ≤ 2(n − 1) and Algorithm 1 3.1 exhibits such a factorization. To see that our upper bound is tight (up to constants), we consider a connected graph on n vertices: let G = (V, E) with V = {0, · · · , n − 1}. Fix the initial values x(0) as xi (0) =   1 if i = 0  0 otherwise. Since all of the mass is contained in node-0, we require at least n − 1 averaging operations to distribute mass to other nodes, because each operation (i.e., multiplication by a matrix in (G ∩ P1 )) can only propagate goods by one additional node. ∗ Thus, TG∩P = Ω(n). Summarizing into a theorem: 1 17 Theorem 3.2. ∗ TG∩P = Θ(n) 1 3.2 G-admissible Factorization The existence of a finite G-admissible factorization of n1 11T is implied by the existence of a finite (G ∩ P1 ) factorization (see Theorem 3.1). Unlike a (G ∩ P1 )factorization, a G-admissible factorization allows one to use several edges at each consensus step. We can rewrite Algorithm 3.1, as in Algorithm 3.3, and combine several G ∩ P1 matrices into a G-admissible matrix to reduce the complexity of the factorization. Algorithm 3.3: G ATHER -P ROPAGATE Input: Graph G, initial values x Output: x ← n1 11T x d ← vector of 1’s indexed by V (G) 2 T ← a spanning tree of G with root r arbitrarily picked 3 foreach v ∈ V (T ) do 4 lv ← ∆(r, v) i.e., the distance from r to v 5 end 6 for α ← maxv lv to 1 do 7 foreach v such that lv = α do      xu 1 1 xu v gives all its value onto its parent u, i.e., , ← 8 xv 0 0 xv 9 du ← du + dv 10 end 11 end 12 for α ← 0 to maxv lv − 1 do 13 foreach u such that lu = α do 14 {v1 , ·· · , vβ }  ← set of children of u   du − dv1 − dv2 − · · · − dvβ xu  xv    dv1  1     xv   dv2  2  ← d1u   xu  ..    ..  .    . xv β dv β 15 16 end 17 end 1 18 Algorithm 3.3 starts from vertices farthest from the root of a spanning tree of G and traverses upwards to give all goods to the root. The second part of the algorithm traverses back down the tree while re-distributing the values to achieve average-consensus at termination. The main difference from Algorithm 3.1 is that all nodes at each level simultaneously transfer their goods to their parents. In the propagation stage, a node propagates the appropriate value to all its children at once. To translate Algorithm 3.3 into a G-admissible factorization, notice that the computations of x updates in each for loop (line 6) can be translated into a single G-admissible matrix, W , with     1 if i = j ∈ / Vα ,    Wij = 1 if j ∈ Vα and i is j’s parent,      0 otherwise, (3.3) where Vα = {v : lv = α}. Similarly, updates in each for loop of line 15 corresponds to a G-admissible matrix W with Wij =  P   (d −  j v: v is a child of j dv )/dj      di /dj    1      0 if i = j ∈ Vα , if j ∈ Vα and i is a child of j, (3.4) if i = j ∈ / Vα , otherwise, where Vα = {v : lv = α}. The number of for iterations at line 6 needed for root r to gather all initial node values is maxv∈V ∆(r, v). The number of for iterations at line 12 needed for re-distributing the values is also maxv∈V ∆(r, v). It is straight forward to construct a finite factorization of n1 11T using 2 maxv∈V ∆(r, v) G-admissible matrices: maxv∈V ∆(r, v) matrices of type (3.3) followed by maxv∈V ∆(r, v) matrices of type 19 (3.4). Summarizing into a theorem: Theorem 3.3. For any connected graph G = (V, E) on n vertices with diameter D, there exists a finite G-admissible factorization of n1 11T . Furthermore, TG∗ ≤ 2D and Algorithm 3.3 exhibit such a factorization. Proof. This follows from the above discussion and the fact that diameter D = max{∆(i, j) : i, j ∈ V }. To see that our upper bound is tight (up to constants), we consider a connected graph G = (V, E) on n vertices with diameter D. Assume that the vertex pair (i, j) has maximal distance, i.e., ∆(i, j) = D. Fix the initial values x(0) as xv (0) =   1 if v = i  0 otherwise. Since all of the mass is contained in node-i, we require at least D averaging operations to distribute mass to other nodes, because each operation (i.e., multiplication by a G-admissible matrix) can only propagate goods by distance 1. Thus, TG∗ = Ω(D) and Theorem 3.4. For any connected graph G = (V, E) with diameter D, there exists a finite G-admissible factorization of n1 11T . Furthermore, TG∗ = Θ(D). 20 Chapter 4 Factorization under Additional Constraints - Pair-wise Averages In terms of network consensus, allowing factorization by G-admissible matrices may be too strong of a requirement. Often times, communication constraints inherent in the network may restrict the types of G-admissible matrices that we are allowed to use. For example, gossip-based asynchronous consensus algorithms [5] correspond to factorization using W (t)’s from G ∩ S10 where S10 ,   (ei − ej )(ei − ej )T I− : 0 ≤ i, j < n . 2 Each matrix in G ∩ S10 corresponds to the averaging of two neighboring node values. Boyd et al [5] studies the -average time of system (1.1) when the W (t)’s are drawn independently and uniformly at random from G ∩ S10 . In terms of finite∗ time consensus, we will show that TG∩S 0 ≥ (n log n)/2 using a potential function 1 argument. But first, we require a brief information theory interlude. 4.1 Information Theory Let p = (p1 , p2 , . . . , pn ) and q = (q1 , q2 , . . . , qn ) be n-dimensional probability vectors. P Let H(p) = − i pi log pi denote the binary entropy function. Unless otherwise specified, all log’s are base-2 and we adopt the convention that 0 log 0 = 0. 21 Because H(·) is concave (see Theorem 2.7.3 in [12]), for 0 ≤ λ ≤ 1, H (λ p + (1 − λ) q) ≥ λ H(p) + (1 − λ) H(q) by Jensen’s Inequality. Therefore if we replace both p and q by their average, the total entropy does not decrease: ∆H , H(λ p + (1 − λ) q) + H((1 − λ)p + λq) − H(p) − H(q) ≥ 0. Let D(p k q) = P i pi log(pi /qi ) denote the Kullback-Leibler divergence between p and q. We have Lemma 4.1. D(p || λ p + (1 − λ) q) ≤ − log λ. Proof. D(p || λ p + (1 − λ) q) = X = X = X ≤ X pi log pi λ pi + (1 − λ) qi pi log λ−1 λ pi λ pi + (1 − λ) qi i i  pi log λ−1 + log i pi log λ−1 λ pi λ pi + (1 − λ) qi  (4.1) i = − log λ, λ pi where the inequality (4.1) is because λ pi ≤ λ pi +(1−λ) qi so log λ pi +(1−λ) ≤ 0. qi 22 Now, we can upper bound the increase in entropy due to averaging: ∆H = H(λ p + (1 − λ) q) + H((1 − λ)p + λq) − H(p) − H(q) = H(λ p + (1 − λ) q) − (λH(p) + (1 − λ)H(q)) + H((1 − λ)p + λq) − ((1 − λ)H(p) + λH(q)) = λ D(p||λ p + (1 − λ) q) + (1 − λ) D(q||λ p + (1 − λ) q) + (1 − λ) D(p||(1 − λ) p + λ q) + λ D(q||(1 − λ) p + λ q) ≤ 2 [−λ log λ − (1 − λ) log(1 − λ)] (4.2) = 2 H(λ) ≤ 2, (4.3) where inequality (4.2) is due to Lemma 4.1 and inequality (4.3) is because the binary entropy function is upper bounded by 1 [12]. Stated as a lemma: Lemma 4.2. The change in total entropy, ∆H, due to the averaging of two probability vectors is bounded by 0 ≤ ∆H ≤ 2. We remark that when λ = 1/2,     p+q p+q ∆H = 2 · JS(p, q) = D p +D q , 2 2 where JS(p, q) is the Jensen-Shannon divergence, a symmetrized version of the Kullbeck-Leibler divergence. With an upper bound on the entropy change, we can derive a lower bound on the necessary consensus time for any graph. ∗ Lemma 4.3. For any connected graph G with n vertices, TG∩S 0 ≥ (n log n)/2. 1 Proof. Recall that x(t) = [x0 (t) x1 (t) · · · xn−1 (t)]T ∈ Rn denotes the node values at time t. For each node i, we can express its value at time t as xi (t) = pi (t)T x(0), 23 where pi (t) is a n-dimensional probability vector. Intuitively, pi (t) represents the weighted contributions of x(0). Initially, for all i, xi (0) = pi (0)T x(0) = eTi x(0), where ei is the i-th column of the n × n identity matrix. When consensus is reached at some time, say T , xi (T ) = pi (T )T x(0) = for all i. Define φi (t) , H(pi (t)) and φ(t) , 1 T 1 x(0) n Pn i=1 φi (t) so that
φ(T ) = n H n−1 1 = n log n. Note that φi (0) = 0. Since each averaging operation increases the total entropy by at most 2 (Lemma 4.2), we need at least (n log n)/2 such operations to reach φ(T ). ∗ Therefore, TG∩S 0 ≥ (n log n)/2. 1 4.2 Necessary Condition for Finite-time Consensus Now that we’ve established a lower bound on consensus time, the question regarding the existence of a finite factorization still remains. As it turns out, restricting the nodes to pairwise averaging prevents the possibility of finite-time consensus in many graphs. Lemma 4.4. If the number of vertices n is not a power of 2, then one cannot achieve finite time consensus with G ∩ S10 . Proof. By contradiction, suppose that finite time consensus is possible. Consider initial node values: xi (0) =   n if i = 0  0 otherwise. At any time t > 0, the values of each node is in the form of n a/2b for some a, b ∈ Z+ ∪ {0}. At consensus time T , we have xi (T ) = 1 so n a/2b = 1 for some a, b ∈ 24 Z+ ∪ {0}. This means n a = 2b which implies that n is a power of 2, a contradiction. 4.3 Consensus on the Boolean Hypercube It is natural to wonder whether there are graphs that achieve the lower bound of Lemma 4.3. As it turns out, the boolean hypercube is optimal for finite-time average-consensus. A boolean hypercube is a graph on n = 2m vertices for some m ∈ N. Its vertex set is the set of 2m binary strings of length m. An edge exists between two vertices if the Hamming distance between the vertices is one (i.e., if the two m-bit strings differ by only one bit). It is not difficult to see that performing pairwise averaging along every edge of the hypercube leads to finite time consensus. Since a hypercube with 2m vertices has m2m−1 edges, the lower bound of Lemma 4.3 is achieved. For a more formal presentation, consider Algorithm 4.1. The “⊕” in the algorithm denotes bit-wise XOR. The overall consensus time of this strategy is (n log n)/2 = m 2m−1 as the outer for loop executes log n times, the inner loop executes n/2 times, and the set of operations in the inner loop corresponds to a single matrix in (G ∩ S10 ). The correctness of Algorithm 4.1 follows from recognizing that it is essentially a divide and conquer algorithm: dividing a size-n hypercube into two size-n/2 hypercubes, performing consensus on both halves, and then averaging between them. Summarizing everything: 25 Theorem 4.5. Given a connected graph G on n vertices, finite factorization of n1 11T with G ∩ S10 is possible only if n = 2m for some m ∈ N. Furthermore, ∗ m−1 TG∩S 0 ≥ m2 1 and equality is achieved when G is the boolean m-hypercube. Algorithm 4.1: S INGLE E DGE C ONSENSUS Input: {x1 , x2 , . . . , xn } P Output: For all i, xi = n−1 nj=1 xj for i = 0 to log n − 1 do 2 foreach a, b ∈ {0, 1, . . . , n − 1} such that a ⊕ b = 2i do 3 M = (xa + xb )/2 4 xa = M 5 xb = M 6 end 7 end 1 The boolean hypercube is one of a few graphs that allow for finite-time averageconsensus with G ∩ S10 . Furthermore, the lower bound of Lemma 4.3 shows that the hypercube structure is optimal in terms of average-consensus time. Given the negative result of Lemma and the fact that a boolean hypercube has 2m vertices, it is natural to wonder whether all graphs of size n = 2m admit finitetime average-consensus. This turns out to be false when we examine a path of length n = 2m . If we initialize the “left-most” node with 1 and the rest of the nodes with 0, i.e., x(0) = [1, 0, . . . , 0]T , then it’s easy to see that if xi−1 (t) 6= 0, xi (t) 6= 0, and xi+1 (t) 6= 0 then either xi−1 (t) ≤ xi (t) < xi+1 (t), or xi−1 (t) < xi (t) ≤ xi+1 (t) since all masses must flow from “left” to “right.” Therefore, there’s no way to 26 achieve an even distribution in finite time on the path with pairwise 50%-50% averages. 27 Chapter 5 Factorization under Additional Constraints: Pair-wise Symmetric Weighted Averages We saw the previous section, i.e., Lemma 4.3, that for arbitrary G, the set G ∩ S10 is too restricting for finite-time consensus. Therefore, we must look beyond G ∩ S10 if we desire a finite factorization of n1 11T . Consider the following generalization of S10 :   (ei − ej )(ei − ej )T S1 , I − : 1 ≤ m ∈ Q; 0 ≤ i, j < n . m Notice that S10 ⊂ S1 and that the matrices in set S1 allow pair-wise weightedaverages. To show that finite-time average-consensus is possible using only pair∗ wise weighted averages at each step (i.e., TG∩S < ∞), we present Algorithm 5.1. 1 The algorithm first constructs a spanning tree T of G. After picking an arbitrary leaf node, say v, as the tree’s root, the algorithm performs reverse depth-first traversal of T (c.f. Algorithm 5.2) while propagating the appropriate amount of goods upward toward v. When the process is complete, v contains the average amount of goods of all nodes in the tree and can thus be removed from future consideration. At this point, another leaf node is designated as the root and the process repeats until all vertices have been examined. At which time, all nodes will have reached average-consensus. 28 It is straight forward to construct a sequence of (G ∩ S1 ) matrices from Line 6 of Algorithm 5.2. Its runtime is O(n2 ) since depth-first traversal takes time O(n) (see §22.3 of [10]) and we perform n − 1 such traversals. Algorithm 5.1: C ONSENSUS Input: Graph G, initial values x Output: x ← n1 11T x T ← a spanning tree of G 2 d ← vector indexed by V (T ) 3 while T is not a single vertex do 4 Initialize d to all 1’s 5 Pick a node v ∈ V (T ) such that degree(v)=1 6 Designate v as the root of T 7 DFS(T , v, x, d) // See Algorithm 5.2 8 T ← T \{v} 9 end 1 Algorithm 5.2: DFS Input: Tree T , vertexPv,vectors x, d Output: xv ← |T |−1 u∈T xu if v has no children then 2 return 3 else 4 foreach child u of v do 5 DFS(T , u, x, d)    dv   du xv xv dv +du u ← dvd+d dv u x x 6 u u dv +du dv +du 7 dv ← dv + du 8 end 9 end 1 To better understand Algorithm 5.2, we illustrate its steps on a complete binary tree in Figure 5.1. The letters inside the nodes of the figure denote their initial values. The blue arrows and weights denote the flow of values. For example, in Figure 5.1(c), the orange node is giving the yellow node 1/3 of its value. Colored nodes denote the active nodes in the algorithm. A yellow coloring means that the node value is the average of its subtree: that it contains the average of itself and all Exmample: Binary Tree29 Exmample: Binary Tree its descendants. d 1 1 2c + 2a c f 1/2 Exmample: Binarya Tree g e Exmample: Binary Tree (a) Picking a leaf node as root (b) Averaging1 toward the root d + 3 a+b+c b root 4 4 3 3/4 2 a+c 1 3 2 + 3b 1/3 Exmample: Binary Tree Exmample: Binary Tree (c) Averaging toward the root (d) Averaging toward the root 4/5 1 4 a+b+c+d 5f + 5 4 5 a+b+c+d+f 6 5 + 16 e Exmample: Binary Tree (e) Averaging toward the root 1/6 (f) Averaging toward the root 6/7 1 6 a+b+c+d+e+f + 7 node has (g)7 gRoot the global average 6 Figure 5.1: Sample execution the Algorithm 5.2. ∗ Algorithm 5.1 serves as a simple proof that TG∩S < ∞. However, it produces 1 a length O(n2 ) factorization from (G ∩ S1 ), which we know is not always optimal. The hypercube example from Section 4.3 demonstrated that some graphs admit a factorization of n1 11T using only O(n log n) matrices from (G ∩ S1 ). This motivates us to develop a better algorithm. But first, let’s explore what basic matrix theory can tell us about consensus algorithms. 30 5.1 Matrix Insights Many of our finite factorization results have been derived constructively from consensus algorithms. We now examine what basic matrix theory can tell us about the algorithmic structure. Let us consider factorization of n1 11T with W (t) ∈ S1 ∩ G. Except for matrices in S10 ∩ S1 , all of the matrices in S1 are non-singular. Thus, for det T −1 Y 1 W (t) = det 11T n t=0 we must have W (t) ∈ S10 for at least one t. In fact, Theorem 5.1. If a finite sequence of T matrices W (0), · · · , W (T − 1) satisfy T −1 Y t=0 W (t) = 1 T 11 n with W (t) ∈ S1 ∩G, then, there exists a sequence of n−1 indices I = {t1 , t2 , · · · , tn−1 } ⊆ {0, 1, · · · , T − 1} such that W (ti ) ∈ S10 ∩ G for all ti ∈ I. Proof. First notice that rank A = n − 1 for A ∈ S10 , rank B = n for B ∈ S1 \S10 , and rank 11T = 1. Since multiplication by a rank-(n − 1) matrix can decrease the rank of a matrix by at most one, we need n − 1 such matrices to reach a rank of one. ∗ Corollary 5.2. For any connected graph G with n vertices, TG∩S = Ω (n). 1 Compared with the Ω(n log n) bound derived using information theory, this lower bound based on elementary matrix theory is very loose. Nevertheless, it is interesting to note its ramifications on the structure of consensus algorithms. 5.2 Consensus Algorithms for Trees The hypercube example of Section 4.3 taught us that certain graph structures allow for fast consensus. This is a good motivation for a fast consensus algorithm. That is, given a graph G, we shall look for certain subgraphs that allow for fast 31 finite-time average-consensus. Since the matrices in (G ∩ S1 ) allow for “swaps” (i.e., two neighbors in G can completely exchange their values), we will use swap operations to transfer the values to the “fast” parts of the graph for fast averaging. Let us first restrict our attention to graphs that are trees: for the remainder of this section, all graphs will be trees and G denotes a tree. For clarity and conciseness of presentation, we shall also assume that |V (G)| = n = 2k . Given a graph G with n = 2k vertices, define a sequence of k − 1 graphs as follows: Gi = Gi+1 ∪ G0i+1 , G0 , G, i )| where Gi+1 is a connected subgraph of Gi with |V (Gi+1 )| = |V (G and Gi ∩ G0i = ∅. 2 Notice that |V (Gi )| = 2k−i . Along with each partition, we define a bijection gi : V (Gi ) → V (G0i ). For suitably chosen partitions and bijections, a consensus algorithm on G can be described recursively as follows: Algorithm 5.3: T REE -C ONSENSUS Input: Tree Gi−1 , bijection gi Output: Finite-time average-consensus is achieved on Gi−1 if Gi−1 has only 2 nodes then 2 Perform pairwise averaging 3 return 4 else 5 T REE -C ONSENSUS(Gi ) // Perform averaging on Gi 0 6 Swap values in Gi and P Gi // This takes v∈Gi ∆(v, gi (v)) operations. 7 T REE -C ONSENSUS(Gi ) // Perform averaging on Gi with swapped values 8 Swap values again P while simultaneously averaging. // This takes v∈Gi ∆(v, gi (v)) operations. 9 end 1 An illustration of the recursive partitioning process is shown in Figure 5.2. 32 μ μ G1 (a) A sample tree, G, with median µ. μ (b) G partitioned into G1 and G01 . G1 highlighted in yellow. μ G3 G2 (c) G1 partitioned into G2 and G02 . G2 highlighted in blue. G1 G2 (d) G2 partitioned into G3 and G03 . G3 highlighted in green. Figure 5.2: Recursive partitioning process of Algorithm 5.3 G1 33 The total number of operations in Algorithm 5.3 is: k−1 n X iX ∆(v, gi (v)). + 2 2 i=1 v∈G i The double summation only counts the number of swap operations (this includes the simultaneous swap-out and average). The n/2 term comes from the averaging operations on Gk−1 for the n/2 pair of vertices that get swapped in. With suitable partitioning and bijections, we can get a desirable runtime (i.e., a short factorization of n1 11T ). Before proceeding, we need a couple definitions: Definition 5.3. For a, b ∈ G, let a b denote the path from a to b in G. For c ∈ G, define ∆(a That is ∆(a b, c) = min ∆(x, c). x∈a b b, c) is the distance of node c to the path a Lemma 5.4. If ∆(µ b. v, u) ≤ 1 for all u ∈ V (Gi ) and v = gi (u), then k−1 X 2i i=1 X ∆(v, gi (v)) = O(n(D̄G + log n)). v∈Gi Proof. For u ∈ V (Gi ), ∆(µ gi (u), u) ≤ 1 implies ∆(u, gi (u)) ≤ ∆(µ, gi (u)) − ∆(µ, u) + 2. Now we take the summation over Gi X ∆(u, gi (u)) ≤ u∈Gi X (∆(µ, gi (u)) − ∆(µ, u) + 2) u∈Gi = X (∆(µ, gi (u)) + ∆(µ, u) − 2∆(µ, u) + 2) u∈Gi = X ∆(µ, v) − 2 v∈Gi−1 = X v∈Gi−1 X ∆(µ, u) + 2 |V (Gi )| u∈Gi ∆(µ, v) − 2 X ∆(µ, u) + 2k−i+1 u∈Gi = Di−1 (µ) − 2Di (µ) + 2k−i+1 , 34 where Di (µ) = k−1 X i=1 i 2 P X u∈Gi ∆(µ, u). Now, ∆(u, gi (v)) ≤ k−1 X 2i Di−1 (µ) − 2Di (µ) + 2k−i+1
i=1 u∈Gi = = k−1 X i=1 k−2 X 2i Di−1 (µ) − 2i+1 Di (µ) + 2k+1 i+1 2 Di (µ) − i=0 k−1 X
2i+1 Di (µ) + (k − 1)2k+1 i=1 k = 2D0 (µ) − 2 Dk−1 (µ) + (k − 1)2k+1 = O(n · D̄G ) − O(n) + O(n log n). To see that D0 (µ) = O(n · D̄G ), observe that 1 XX ∆(u, v) 2 u∈G v∈G 1 XX ≥ ∆(µ, v) 2 u∈G v∈G nX n = ∆(µ, v) = D0 (µ). 2 v∈G 2 total DG = Now just look at the definition of average distance: D̄G = total DG D0 (x) D (µ)
≥ 0 ≥ . n n−1 n 2 Using Algorithm 5.4, we show how to partition and pair the Gi -G0i vertices to satisfy the condition in Lemma 5.4. As an illustration, we demonstrate the pairing process on a sample tree in Figure 5.3. Since each node is paired with its sibling or its parent, the output of Algorithm 5.4 easily satisfies Lemma 5.4 condition. Even though the pairings produced by Algorithm 5.4 promote efficient G1 -G01 exchange, they cannot be used directly be- 35 Partitioning and pairing attempt Partitioning and pairing attempt ∈ G1 ∈ G10 Partitioning and attempt Partitioning and (a) A sample tree,pairing G. (b) A node paired with pairing its parent. attempt ∈ G1 ∈ G10 ∈ G1 ∈ G10 (c) A node paired with its sibling. (d) Complete pairing. Figure 5.3: Pair assignment process of Algorithm 5.4. 36 Algorithm 5.4: I NITIAL PAIRING Input: Tree G rooted at x Output: A partition G1 ∪ G01 = G and mapping g : G1 → G01 satisfying Lemma 5.4 if |G| is odd then Get rid of a leaf by DFS-like averaging. 3 end 4 i ← deepest level (descendants farthest from root x) repeat 5 foreach unpaired node v at level i do 6 if v has an unpaired sibling, say u then 7 Pair (u, v) together. 8 The vertex closest to x is assigned to Gi and the other to G0i 9 else if v has no unpaired sibling then 10 u ← Parent of v 11 Pair (u, v) together. 12 u is assigned to Gi and v to G0i 13 end 14 end 15 Decrease level: i ← i − 1 16 until i = 0 or all nodes are paired 1 2 cause G1 might be disconnected and averaging on G1 may take a long time. We need to fix the pairings with Algorithm 5.5: An illustration of the fixing process is shown in Figure 5.4. To see the correctness of Algorithm 5.5, first note that: Lemma 5.5. Each node’s membership in G1 or G01 is modified by the algorithm at most once. Proof. It is clear that each G01 node on level i is enters the foreach loop exactly once: the algorithm changes the pairing so that v belongs in G1 . Now we consider a node in the tree that played the role of w (line 5) at some iteration of the algorithm. Line 7 of the algorithm would have changed w so it now belongs to G01 . This means that w and all its descendants are in G01 (since w was chosen as the farthest G1 node before the membership change). So w will never enter the foreach loop again. In terms of problematic pairings addressed by Line 3 of Algorithm 5.5, there are only 4 cases to consider: 37 Algorithm 5.5: F IX PAIRING Input: Tree G rooted at x with |G|=even Output: A partition G1 ∪ G01 = G and mapping g : G1 → G01 satisfying Lemma 5.4 where G1 is connected subgraph of G i ← 1 (start with nodes in G01 that are closest to x) 2 repeat 3 foreach node v ∈ G01 on level i that has a descendent w ∈ G1 do 4 u ← g −1 (v) 5 w ← farthest descendent ∈ G1 . 6 z ← g(w) 7 Pair u with w, put w in G01 (Remove w from G1 ). 8 Pair v with z, put v in G1 (Remove v from G01 ). 9 end 10 Increase level: i ← i + 1 11 until (i = depth of G) or (G1 is connected) 1 Fixing the pairings Fixing the pairings u u v v w w z z Fixing the pairings (a) Problem pairs (u, v) and (w, z) z (b) Reassignment Fixing the pairings u u v v w (c) Problem pairs (u, v) and (w, z) z w (d) Fixing complete. Blue nodes (i.e., nodes in G1 ) are now connected. Figure 5.4: Pair fixing process of Algorithm 5.5. 38 • u-v, w-z (see Figure 5.5(a)) • u-v, w ∧ z (see Figure 5.5(b)) • u ∧ v, w-z (see Figure 5.5(c)) • u ∧ v, w ∧ z (see Figure 5.5(d)), where u-v denotes that nodes u and v are neighbors (more precisely, they have a parent-child relationship); u ∧ v denotes that nodes u and v are siblings that share the same parent node. These cases are illustrated in Figure 5.5. It is easy to see that each of these four cases are correctly handled by lines 7 and 8 of Algorithm 5.5 thus: ∗ Theorem 5.6 (Upper bound). For any connected graph G with n vertices, TG∩S = 1 O(n(D̄G + log n)). Configuration 1 Configuration 2 u u v v w w u u v v z z Configuration 3 w z w 4 z Configuration (b) u-v, w ∧ z (a) u-v, w-z v u u v u w v u v w z z w (c) u ∧ v, w-z z w (d) u ∧ v, w ∧ z Figure 5.5: Four problematic pairing configurations and their fixes. z 39 5.3 Lower bound on Trees To see that the algorithms presented in the previous section are optimal, we now derive lower bounds on the consensus time. Definition 5.7. Given a tree G and an edge e = (l, r) in G, define m(e) , min{|Le |, |Re |}, where Le , {v ∈ G : ∆(v, l) < ∆(v, r)}, Re , {v ∈ G : ∆(v, l) > ∆(v, r)}. In other words, m(e) is the minimum number of nodes on the “left” and “right” side of edge e. Lemma 5.8. For any tree G on n vertices,  ∗ TG∩S = Ω 1  X m(e) . e∈E(G) Proof. Given an edge e = (l, r) in G, consider the initial condition xi (0) =   0 if i ∈ Le }  1 if i ∈ Re }. The total mass is |Re | and average-consensus is achieved when x(T ) = |Rne | 1 for some T . In this proof, it is useful to view each matrix in G ∩ S1 as a “use” of a particular edge in E(G). Using a mass-balancing flow argument, we show that m(e)/2 is a lower bound on the number of times edge e must be used. In aggregate, the nodes in Le require |Le |/n fraction of the total mass. Since the total mass is |Re | and each use of an edge carries at most 1 unit of mass, we know that edge e must be used at least   |Le ||Re | |Le ||Re | m(e)(n − m(e)) m(e) ≥ = ≥ n n n 2 40 times. Since a consensus algorithm must achieve average-consensus for all initial distributions, we must have X m(e) 2 ∗ ≥ TG∩S 1 e∈E(G) as a lower bound on its consensus time. To see that each edge can carry a flow of at most 1, observe that matrices in S1 correspond to a convex combination of a pair of node values. Since initial values are xi (0) ∈ {0, 1}, any sequence of convex combinations must keep the values in the closed interval [0, 1], i.e., 0 ≤ xi (t) ≤ 1 for all t. One can relate this lower bound to the graph average distance by Lemma 5.9. X m(e) ≤ D̄G · (n − 1) ≤ 2 e∈E(G) X m(e). e∈E(G) Proof. total DG = X X ∆(i, j) i∈V j∈V,j6=i = X = X |Le | · |Re | e∈E m(e) · (n − m(e)). e∈E For the “≤”, notice that X m(e) · (n − m(e)) = n e∈E X e∈E m(e) − X m2 (e) ≤ n X e∈E e∈E Since total distance is just average distance times n , we have 2
X n(n − 1) ≤ n m(e) 2 e∈E X (n − 1) ≤ m(e). D̄G · 2 e∈E D̄G · m(e). 41 For the “≥”, we note that m(e) ≤ n/2 so that n − m(e) ≥ n/2. X m(e) · (n − m(e)) ≥ e∈E nX m(e) 2 e∈E which means n(n − 1) nX ≥ m(e) 2 2 e∈E X D̄G · (n − 1) ≥ m(e). D̄G · e∈E Thus, we can restate Lemma as, ∗ Lemma 5.10. For any connected graph G with n vertices, TG∩S = Ω (n · avg dist). 1 This lower bound is based on the structure of the underlying graph. We can use the same argument as in Lemma 4.3 to obtain an information-theoretic lower bound: ∗ Lemma 5.11. For any connected graph G with n vertices, TG∩S = Ω (n log n). 1 Combining Lemma 5.10 and Lemma 5.11, we have ∗ Theorem 5.12 (Lower bound). For any connected graph G with n vertices, TG∩S = 1
Ω n(D̄G + log n) . 5.4 Consensus Time on Trees The lower bound of Theorem 5.12 matches the complexity of the recursive finitetime average-consensus algorithm developed in Section 5.2 so the problem of scheduling for finite-time average-consensus on trees subject to the constraints of S1 is solved: Theorem 5.13.
∗ TG∩S = Θ n( D̄ + log n) G 1 42 5.5 General Graphs For general graphs that are not trees, the upper bound from Section 5.2 still holds. That is, given a graph G, we can always construct a spanning tree and run the treebased algorithm of Section 5.2. The question remains on how much do we lose by considering only a spanning tree and not the entire graph. In general, graphs can have very rich structure and high connectivity compared to its spanning tree. Surprisingly, we only lose a log2 n factor when considering only the spanning tree. As a caveat, one needs to be careful when choosing the spanning tree as certain trees (such as the path on n vertices) do not admit fast consensus. We need to choose a spanning tree that preserves the average distance (up to a constant). 5.5.1 Graph Lower bound Recall the lower bound technique for trees used in Lemma 5.3 of Section 5.3 where we picked edges e from the graph G and argued that each edge must support of flow of m(e) units. In trees, edges are precisely the bottlenecks because removing an edge disconnects the tree into two trees. In graphs, however, there may be many paths between a given pair of nodes. Removing an edge may not be enough to disconnect the graph so if we want to proceed with the same mass flow argument, we need to consider graph cuts. Definition 5.14. A cut C = (S, T ) of a graph G = (V, E) is a partition of the vertex set V where S ∪ T = V, S ∩ T = ∅. The cut-set of a cut C is the set {(u, v) ∈ E : u ∈ S, v ∈ T. We say two cuts are edge-disjoint if their cut-sets do not share any edges. 43 Given a cut C = (S, T ), we can define m(C) = min{|S|, |T |} to refer to the smaller side of the cut. That is, the side with the fewest vertices. If we have a sequence C1 , C2 , · · · , Ck of edge-disjoint cuts, then a lower bound on ∗ TG∩S is 1 ∗ TG∩S =Ω 1 k X ! m(Ci ) i=1 by using a similar mass flow argument as in Lemma 5.3. It is clear that if we can find a suitable set of edge disjoint cuts, then we have a good lower bound. The trouble is that collections of good (i.e., maximal) edgedisjoint cuts are hard to find. If we are careful in accounting the amount of goods that flow across each edge, then we don’t need edge-disjoint cuts and we can use the solution to the following integer program as a lowerbound: minimize s.t. 1T x Ax ≥ m 0 ≤ xe < n, ∀e ∈ E xe ∈ Z, ∀e ∈ E. Here, x ∈ R|E| is a vector indexed by the edges of the graph. For e ∈ E, xe indicates how many times edge e is used in the consensus protocol. The matrix A is a cut-edge incidence matrix of G. It is a “tall” matrix of size O(2n ) × |E|. The rows of A are indexed by cuts of G and columns of A are indexed by edges of G. Given a cut C of G and an edge e ∈ E, AC,e = 1 if e is in the cut-set of C and 0 otherwise. The vector m is a vector indexed by the cuts of G; it is of size O(2n ). Given a cut C, mC = m(C). The program solves for the minimum number of edge uses across all edges subject to a mass flow constraint. 44 Although the solution to the program is a valid upper bound, integer programs are generally hard to solve. Even if we relax the integer constraint and turn it into a linear program, we still have to deal with the exponential number of constraints in the program. This motivates us to seek alternative methods of lower bounding the consensus-time on general graphs. 5.6 Metric Space Embeddings The key idea in our lower bound techniques was our search for graph cuts which are representative of the bottlenecks in the graph. If we can find a maximal set of edge-disjoint paths, then we can get a “good” lower bound. As maximal edgedisjoint paths can be hard to find, we use some tools from metric space embedding to map our graph into a different space where the edge-disjoint cuts are easier to find. This allows us to find a “good-enough” collection of edge-disjoint cuts that provide a “good-enough” lower bound. To be more precise, we need to introduce some tools from metric space embedding: Theorem 5.15. [Abraham, Bartal, Neiman [1]] For any 1 ≤ p ≤ ∞, every n-point metric space embeds in Lp with distortion O(log n) in dimension O(log n). The theorem implies that there exists a mapping f : V (G) → RO(log n) with distortion ∆(u, v) ≤ kf (u) − f (v)k ≤ O(log n) · ∆(u, v), where kf (u)k = ∀u, v ∈ G, (5.1) P j |fj (u)| denotes the L1 -norm. Let i denote the “heaviest” coor- dinate in terms of total pairwise distance: X i = arg max j |fj (u) − fj (v)|. u,v∈G:u6=v This means that X kf (u) − f (v)k u6=v O(log n) ≤ X u6=v |fi (u) − fi (v)| (5.2) 45 because X kf (u) − f (v)k = u6=v XX u6=v |fj (u) − fj (v)| ≤ O(log n) j X |fi (u) − fi (v)|. u6=v We also know that |fi (u) − fi (v)| ≤ kf (u) − f (v)k, ∀u, v ∈ G. (5.3) Combining the first inequality of (5.1) with (5.2), we see that X ∆(u, v) u6=v O(log n) ≤ X |fi (u) − fi (v)|. (5.4) u6=v Combining the second inequality of (5.1) with (5.3), we see that |fi (u) − fi (v)| ≤ O(log n) ∆(u, v), ∀u, v ∈ G. (5.5) Thus, on average, edges in G are “stretched” by at most O(log n) under fi . This property allows us to use fi to embed the graph G onto R and look for edge-disjoint cuts on the embedded line. Starting from the left-most point (i.e., minu fi (u)), consider partitioning the embedded points on R using a sequence of cuts spaced O(log n) apart. These partitions correspond to a sequence of edge-disjoint cuts {Ck } in G: if not, then some edge in G must have been stretched longer than O(log n) by fi which contradicts (5.5). 46 Pick a point x that has n/2 points to its left: |{v : fi (v) ≤ fi (x)}| = n/2. We have X m(Ck ) ≥ X  |fi (v) − fi (x)|  v∈G k ≥ X  |fi (v) − fi (x)| v∈G = X v∈G (5.6) O(log n) O(log n) |fi (v) − fi (x)| O(log n)  −1  −n X  |fi (u) − fi (v)|  −n n O(log n) u6=v X  ∆(u, v)  ≥ −n 2 n) n O(log u6=v   n · D̄G = Ω , log2 n ≥ (5.7) (5.8) (5.9) where inequality (5.6) is because in the summation, each point v contributes its distance to x divided by O(log n); inequality (5.7) is because X |fi (u) − fi (v)| ≤ X |fi (u) − fi (x)| + |fi (v) − fi (x)| = 2(n − 1) |fi (v) − fi (x)|; v∈G u6=v u6=v X inequality (5.8) is because of (5.4). The final inequality follows from the definition of D̄G . P ∗ Since TG∩S = Ω( k m(Ck )) for any sequence {Ck } of edge disjoint cuts and the 1 information-theoretic lower bound of Ω(n log n) remains valid for all graphs, we conclude that Theorem 5.16. For any graph G, ∗ TG∩S =Ω 1    D̄G n + log n . log2 n Interpreting this result in light of the tree-based consensus algorithm in Section 5.2, we see that taking into account all edges of the graph offer at most an O(log2 n) speedup over our spanning tree-based algorithm. This is quite surprising as the number of edges between a graph and its spanning tree can differ by as much as a factor O(n). 47 Chapter 6 Factorization under Additional Constraints - Parallel Symmetric Weighted Averages Instead of allowing only one pair of neighbors to exchange values at any given time, we now explore the possibility of parallel communications. Consider the set  S , W ∈ Qn×n : W = W T . Note that the matrices in S are doubly stochastic (i.e., 1T W = 1T and W 1 = 1). The motivation for S is to allow parallel distribution of mass by symmetric weighted averages; yet disallow drastic aggregation steps such as line 6 of Algorithm 3.1 where nodes transfer all their mass to another. Such operations are often undesirable due to trust considerations: why should one node send everything to another node in hopes of getting his/her fair share in the future. Furthermore, node capacity constraints often disallow such aggregation by any individual node. In the example of Section 1.2, each child has a backpack of unit capacity. Therefore, they are unable to store goods in excess of one unit. We want to consider the possibility of parallel communications to investigate the speed up between parallel communication and serial communication in the context of finite-time average-consensus problems. We will see shortly that by using G ∩ S instead of G ∩ S1 , the consensus time is improved to Θ(n). 48 6.1 ∗ = O(n) Upper bound: TG∩S As S1 ⊂ S, we can still use Algorithm 5.1 to achieve consensus. But instead using the reverse depth-first traversal in Algorithm 5.2, we modify it slightly (see Algorithm 6.1) to use fewer matrices (i.e., Algorithm 5.1 using the improved DFS of Algorithm 6.1 is faster than Algorithm 5.1 using the DFS of Algorithm 5.2). Algorithm 5.1 with improved DFS (Algorithm 6.1) can be further improved by using a pipelined architecture to yield Algorithm 6.2 which allows factoring using only O(n) matrices. Algorithm 6.1: DFS-I MPROVED Input: Tree T , vertexPv,vectors x, d Output: xv ← |T |−1 u∈T xu if v has no children then return 3 else 4 foreach child u of v do 5 DFS-I MPROVED(T, u, x, d) 6 end 7 {u1 , · · · , u` } ← set of children of v P̀ D ← dv + duj 8 j=1 d du1 du2 v   ··· D D D xv d D−d u1 u1  0 ··· D D xu1   du2 xu2  D−du2 0  ←D D  .  ..  .. .. .  .. . . 1 2 9 xu` du` D 0 ··· 0 du` D    xv  0  xu1  ..  x  .   u2    ..  . 0  D−du` D xu ` dv ← D 11 end 10 Intuitively speaking, Algorithm 6.2 implements a pipelined version of Algorithm 5.1. We employ parallel consensus steps when they do not interfere with each other. For clarity, we use a simple example to illustrate the pipelined algorithm. Consider G as the path with V = {1, 2, 3, 4, 5} and E = {a, b, c, d} as shown in Figure 6.1. First, let us run Algorithm 5.1 on our simple example. Suppose that line 5 of 49 1k a 2k b 3k c 4k d 5k Figure 6.1: A line graph. Algorithm 5.1 examines nodes 5, 4, 3, 2, 1 in that order, then the sequence of pairwise weighted averages corresponds to the following sequence of edges: 5 a b c d 4 a b c 3 a b a 1&2 Time: 1 2 3 4 5 6 7 8 9 10 Here, time runs left-to-right and each time column enumerates all edges used during that time slot. With Algorithm 5.1, each time slot only utilizes one edge and we need 10 edges. The right-most annotation indicates that the sequence of edges allowed a node to obtain the correct average. For example, after the edge sequence a, b, c, d in time steps 1-4, node 5 will have the correct global average. Since edges a and c are vertex-disjoint, the averaging on a will not effect the values of nodes in edge c. We can thus perform some averages in parallel and implement a pipelined architecture: 5 a b c d 4 a b c 3 a b a 1&2 Time: 1 2 3 4 5 6 7 Pipelining allows us to use multiple edges per time step (e.g., At time 4, edges b and d are used in parallel. At time 5, edges c and a are used in parallel). The parallel edges can be incorporated into a single matrix leading to savings in terms of the number of matrices used. Once again, the right-most labels annotate the epochs 50 dedicated to each node obtaining the global average (e.g., after edge sequence a, b, c in time 3-5, node 4 obtains the global average). This pipelined architecture is the key innovation of Algorithm 6.2. Algorithm 6.2: C ONSENSUS Input: Graph G, initial values x Output: x ← n1 11T x T ← a spanning tree of G 2 r1 , r2 , · · · , rn ← a postordering of V (T ) by depth-first search 3 d ← vector of 1’s indexed by V (T ) 4 φ ← vector of 0’s indexed by V (T ) 5 foreach v ∈ V (T ) do 6 if degree(v)=1 then φv = 1 7 end 8 i ←1 9 Let ri be the root of T 10 φri = 0 11 while |V (T )| > 1 do 12 Consensus-While Loop (Algorithm 6.3) 13 if φri = 1 then 14 let ri ∼ u1 ∼ · · · ∼ um ∼ ri+1 be the path from ri to ri+1 in T 15 foreach 0 < j ≤ m do 16 duj ← 1 17 φuj ← 0 18 end 19 if degree(u1 )=2 then φu1 ← 1 20 21 end 22 T ← T \{ri } 23 i←i+1 24 Let ri be the root of T 25 φri = 0 26 end 27 end 1 Now we examine the inner workings of Algorithm 6.2. We begin by establishing a postordering (r1 , r2 , · · · , rn ) of vertices by a depth-first search from an arbitrary vertex. During the execution process, we keep track of φ, an indicator of 51 Algorithm 6.3: C ONSENSUS -W HILE L OOP d0 ← d; 0 2 φ ← φ; 3 foreach v ∈ V (T ) do 4 if (φv = 0) and (∀ child u ofv, φu = 1) then 5 {u1 , · · · , u` } ← children of v; P̀ D ← dv + duj ; 6 j=1  dv du`   du1    1 7 xv D  dDu1 xu1   ..  ←   ... . du` xu` D D D−du1 D 0 d0v ← D; 9 φ0v ← 1; 10 foreach child u of v do 11 if du 6= 1 then 12 d0u ← 1; 13 φ0u ← 0; 14 end 15 end 16 end 17 end 0 18 d ← d ; 0 19 φ ← φ ; 8 ··· .. D xv 0  xu1    . ;  .. D−du` D xu` . 52 whether a vertex’s value is the average of its descendants: φv =   1  1 if xv = |decedents(v)|+1 ! xv + P xu u∈decedents(v)   0 otherwise. The computations of x-updates in each while loop (line 11 of Algorithm 6.2) can be translated into a single matrix in G ∩ S as each vertex appears at most once in line 7 of Algorithm 6.3 for each iteration of the while loop (i.e., all operations inside line 3’s foreach loop of Algorithm 6.3 can be combined into one matrix). The number of while iterations needed for r1 to achieve the average is at most n−1. After ri reaches the average, the number of while loops needed for ri+1 to achieve the average is at most the length of the path from ri to ri+1 . Since the sequence r1 , r2 , · · · , rn is a postordering of V (T ) by depth-first search, n−1 X (length of path from ri to ri+1 ) ≤ 2n. i=1 Therefore, the number of matrices in this factorization is O(n). For a rigorous argument of the correctness and consensus time of Algorithm 6.2, we rewrite it as more abstract pseudo code in Algorithm 6.4. To prove the correctness of Algorithm 6.4, we need definitions of “ready” nodes and “progress” nodes: Definition 6.1. Node v is a progress node if it is ready (i.e., φv = 1) and the path from root to v contains no other ready nodes. We will show, through a series of arguments, that there is a wave of progress nodes moving toward each root node and that the total time for all waves to complete is O(n). Lemma 6.2. Let δi denote the maximal distance from root ri to a farthest progress node. After the ”foreach” loop, δi decreases by 1. Proof. We shall proceed inductively. Initially, before the first execution of the loop, all progress nodes are leaves. Let S denote the set of leaf-nodes whose distances 53 Algorithm 6.4: P IPELINED r1 , r2 , · · · , rn is a postodering by depth-first search. 2 Start with r1 as the root 3 repeat 4 foreach node v whose children are ready do 5 Average v with its children 6 Set φv = 1 (v is ready) 7 (book-keeping) reset all non-leaf children to not ready 8 end 9 (*) 10 if Root ri is ready (i.e., φri = 1) then 11 Reset nodes along path ri ri+1 12 Remove old root ri 13 (book-keeping) if node connected to ri becomes leaf then set it to ready 14 Make ri+1 the new root 15 (**) 16 end 17 until no more nodes left 1 from the root are maximal. The parents of nodes in S will become progress nodes after (*). Assume the contrary: that there exists a v ∈ S who has an unready sibling u∈ / S, φu = 0. Since leaves are always ready, u cannot be a leaf. If u is not a leaf, it must have a descendant w that is a leaf and φw = 1. The distance from the root to w is strictly greater than the distance from root to v, contradicting the maximality of v. Thus, no such siblings exist for all nodes in S. Parents of nodes in S will become progress nodes at (*) and δi decreases by 1. Notice that the advancement of progress nodes depends only on other progress nodes. So we can discard all descendants of progress nodes from our consideration. Effectively, all progress nodes can be seen as “leaf-nodes” and the previous argument applies for each iteration. 54 Definition 6.3. A node v is good if 1. v is a leaf, or 2. v is not ready but all its children are ready and good, or 3. v is ready and all its children are good. Lemma 6.4. Once a node becomes good, it will never become non-good. Proof. We will use backward induction on the distance from the root to the node. The base cases are the leaf nodes, which are always good by definition. Assume the claim is true for all nodes at a distance t from the root. Now consider a good node v at distance t − 1 from the root. We show that after the iteration of the algorithm, v remains good. There are three cases to consider: 1. (v is a leaf) A leaf is always good and ready. 2. (v is not ready but all its children are ready and good) After one iteration of the algorithm, v becomes ready and all its children remain good by induction hypothesis. 3. (v is ready and all its children are good) There are two subcases to consider: • (After an iteration, v remains ready) v remains good since all its children remain good by induction hypothesis. • (After an iteration, v becomes not ready) We need to show that v’s children are ready and good. Since v’s children were good by assumption, we shall show that they are ready. Consider the children of v that are not ready (if there are no such children then we are done). These children are good by induction hypothesis and therefore their children (i.e. v’s grandchildren) must be ready. Thus after an iteration, the unready children of v will become ready. 55 Lemma 6.5. At (**), all nodes at distance 1 away from ri ri+1 path are good. Proof. By the time ri becomes ready, all remaining nodes will be good. The bookkeeping resets only affect the nodes on the path ri ri+1 so the nodes attached to this path (at distance 1 away) are good. Lemma 6.6. At (**), δi+1 ≤ ∆(ri , ri+1 ). Proof. First, observe that a good node that is not ready will become ready within one iteration. Thus, within one iteration, all nodes attached to the ri ri+1 will become ready. Let ri → u1 → u2 → · · · um → ri+1 be the path from ri to ri+1 . There are two cases to analyze: • (After removing ri , u1 becomes a leaf) Since u1 became a leaf, it will be set as ready. Let’s consider some possible cases for farthest progress nodes: – (u1 or children of u2 that are not on the ri ri+1 path) Distances from ri+1 to these nodes are strictly less than ∆(ri , ri+1 ). – (grand children of u2 that are not on the ri ri+1 path) Distances from ri+1 to these nodes are equal to ∆(ri , ri+1 ). Since all nodes attached to the ri ri+1 path are good, these are the only candidates for farthest progress nodes. • (After removing ri , u1 is not a leaf) Let’s consider the state of things at (*) when φu1 = 1. The process of making φri ready will have made φu1 = 0. But since u1 remains good, we know that the children of u1 are all ready. With respect to the new root ri+1 , these children u1 are progress nodes at a maximal distance away. This maximal distance is the ∆(ri , ri+1 ). Theorem 6.7. [Upper bound] For any connected graph G with n vertices, ∗ TG∩S = O(n). 56 Proof. The time it takes to complete r1 is at most n. The time it takes to complete ri+1 is δi+1 ≤ ∆(ri , ri+1 ). So time to total completion is at most n+ n X ∆(ri , ri+1 ) ≤ n + 2(n − 1) ≤ 3n. i=2 Because the ri ’s are a postordering by depth-first search, the summation Pn i=2 ∆(ri , ri+1 ) is analogous to tracing an outline around the entire tree. A tree on n vertices has n−1 edges, an outline of the tree traces each edge twice so that’s where the 2(n−1) term comes in. 6.2 ∗ Lower bound: TG∩S = Ω(n) ∗ is Ω(n), we use a similar mass flow argument To show that the lower bound of TG∩S as Lemma 5.3 in Section 5.3. To make the argument, we need to first identify some bottle-neck nodes in our tree: Lemma 6.8. Given a tree T , there exists a node v and corresponding sets A and B such that 1. T \{v} = A ∪ B with A ∩ B = ∅, 2. v ∈ a b for all a ∈ A and b ∈ B, 3. min{|A|, |B|} ≥ bρnc for 0 < ρ < 1/2. Proof. Assume for contradiction that all nodes possess a neighbor whose subtree contains ≥ d(1 − ρ)ne nodes. Pick an arbitrary node u1 and let u2 be the neighbor whose subtree contains ≥ d(1 − ρ)ne nodes. By assumption, u2 must have a neighbor u3 whose subtree contains ≥ d(1 − ρ)ne nodes. Now u3 6= u1 because u2 was picked as the “heavy” neighbor of u1 so there aren’t enough nodes on u1 ’s side. Proceed similarly until we get a sequence of k = d(1 − ρ)ne nodes: u1 , u2 , · · · , uk . By assumption, uk has a neighbor uk+1 6= uk−1 whose subtree contains ≥ d(1 − ρ)ne nodes. But there are ≥ d(1 − ρ)ne nodes not in this subtree (e.g., u1 , u2 , · · · , uk ), leading to a contradiction. 57 Pick a node v such that V \{v} = A ∪ B with min{|A|, |B|} ≥ n/4 as in the above lemma. Initialize all nodes in A with weight 1 and all nodes in B with weight 0 so that the total mass in the system is ≥ n/4. Because all the mass are on the A side of v, we must move a mass of ≥ n/8 across v in order to reach average consensus. Since each use of an edge adjacent to v can move mass at most 1 (matrices in G ∩ S are doubly stochastic), we must use them at least ≥ n/8 = Ω(n) times. Together with the upper bound of Theorem 6.7, we see that Theorem 6.9. For any connected graph G with n vertices, ∗ TG∩S = Θ(n). 58 Chapter 7 Discussion and Extensions We close with some discussions on future research directions: • There is a gap of O(log2 n) between the graph and tree lower bounds. One of the O(log n) factors is due to the distortion in the embedding process when we embed the graph into the L1 space in order to easily find edge-disjoint cuts. The other O(log n) factor is an artifact of our projection after the embedding. The embedding used in Theorem 5.15 due to [1] is tight in general since metric spaces induced by expander graphs require Ω(log n) distortion and Ω(log n) dimension (see Theorem 4 of [1]). It is possible that the O(log2 n) gap is not intrinsic to our consensus problem and there are other approaches to arrive at a graph lower bound which is consistent with the tree lower bound. Alternatively, we can hope for better algorithms that achieve the current lower bound. • All of the algorithms given thus far are of a centralized nature. We assume that the scheduler has access to the graph and is able to construct a schedule ahead of time. It would be very interesting to investigate distributed algorithms that result in finite-time average-consensus under similar node constraints. • In our analysis, we have assumed that network nodes are homogeneous and capable of performing only weighted average operations. If nodes are inhomogeneous (e.g., a network of mobile phones and base stations) then their 59 ability to compute weighted averages may differ. It is interesting to consider the implications of inhomogeneous networks on finite-time averageconsensus. • If nodes communicate wirelessly using directional antennas, then their topology is represented by a directed graph. Also, if we think of a commodity distribution network, it is conceivable that some networks allow unidirectional flow of goods in certain portions of the network. Hence, the analysis of Gadmissible factorizations of n1 11T , when G is a directed graph, is a natural extension. • We studied the case of average-consensus where nodes tend to a n−1 1 distribution. Often times there is a need to arrive at a distribution other than n−1 1. For example, consider the emerging smart grid. Different times and different regions have varying demands on electricity. We would like to rapidly redistribute the resources in the network to match the changing demand profile. Phrased in our problem setting, we would be exploring G-admissible factorizations of general left-stochastic matrices. 60 Bibliography [1] I. Abraham, Y. Bartal, and O. Neiman. Advances in metric embedding theory. In Proceedings of the 38th ACM Symposium on Theory of Computing, 2006. [2] H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita. Distributed memoryless point convergence algorithm for mobile robots with limited visibility. Robotics and Automation, IEEE Transactions on, 15(5):818–828, Oct 1999. [3] T. Arai, E. Pagello, and L. E. Parker. Guest Editorial Advances in Multirobot Systems. IEEE Transactions on Robotics and Automation, 18(5):655 – 661, 2002. [4] T. C. Aysal, M. Coates, and M. Rabbat. Distributed average consensus using probabilistic quantization. In SSP ’07: Proceedings of the 2007 IEEE/SP 14th Workshop on Statistical Signal Processing, pages 640–644, Washington, DC, USA, 2007. IEEE Computer Society. [5] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE/ACM Transactions on Networking, 14(SI):2508–2530, 2006. [6] R. Carli, F. Bullo, and S. Zampieri. Quantized average consensus via dynamic coding/decoding schemes. International Journal of Robust and Nonlinear Control, 20:156–175, 2010. [7] R. Carli, F. Fagnani, A. Speranzon, and S. Zampieri. Communication constraints in coordinated consensus problems. American Control Conference, June 2006. [8] R. Carli, P. Frasca, F. Fagnani, and S. Zampieri. Gossip consensus algorithms via quantized communication. Automatica, 46:70–80, 2010. 61 [9] J.-Y. Chen, G. Pandurangan, and D. Xu. Robust computation of aggregates in wireless sensor networks: distributed randomized algorithms and analysis. Fourth International Conference on Information Processing in Sensor Networks, 2005., pages 348–355, April 2005. [10] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001. [11] J. Cortes. Finite-time convergent gradient flows with applications to network consensus. Automatica, 42(11):1993 – 2000, 2006. [12] T. M. Cover and J. A. Thomas. Elements of information theory. Wiley- Interscience, New York, NY, USA, 1991. [13] A. Dobra D. Kempe and J. Gehrke. Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 03), volume 8, page 482, 2003. [14] R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Heidelberg, third edition, 2005. [15] A.D.G. Dimakis, A.D. Sarwate, and M. Wainwright. Geographic gossip : Efficient averaging for sensor networks. IEEE Transactions on Signal Processing, 56(3):1205–1216, March 2008. [16] J. A. Fax and R. M. Murray. Information Flow and Cooperative Control of Vehicle Formations. IEEE Trans. on Automatic Control, 49(9):1465–1476, September 2004. [17] Q. Hui, W.M. Haddad, and S.P. Bhat. Finite-time semistability theory with applications to consensus protocols in dynamical networks. In Proceedings of the American Control Conference, July 2007. [18] A. S. Morse J. Lin and B. D. O. Anderson. The multi-agent rendezvous problem. 42nd IEEE Conference on Decision and Control, 2003, page 1508, Dec. 2003. 62 [19] A. Kashyap, T. Başar, and R. Srikant. Quantized consensus. Automatica, 43(7):1192–1203, 2007. [20] D. B. Kingston and R. W. Beard. Discrete-time average-consensus under switching network topologies. In Proceedings of the 2006 American Control Conference, 2006. [21] C.-K. Ko and X. Gao. On matrix factorization and finite time average consensus. In Proceedings of the 48th IEEE Conference on Decision and Control, December 2009. [22] C.-K. Ko and L. Shi. Scheduling for finite time consensus. In Proceedings of the American Control Conference, June 2009. [23] J. Lavaei and R. M. Murray. On quantized consensus by means of gossip algorithm: part i: convergence proof. In ACC’09: Proceedings of the 2009 conference on American Control Conference, pages 394–401, Piscataway, NJ, USA, 2009. IEEE Press. [24] J. Lavaei and R. M. Murray. On quantized consensus by means of gossip algorithm: part ii: convergence time. In ACC’09: Proceedings of the 2009 conference on American Control Conference, pages 2958–2965, Piscataway, NJ, USA, 2009. IEEE Press. [25] N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996. [26] S. Martı́nez, J. Cortés, and F. Bullo. Motion coordination with distributed information. IEEE Control Systems Magazine, 27(4):75–88, 2007. [27] L. Moreau. Consensus seeking in multiagent systems using dynamically changing interconnection topologies. IEEE Transactions on Automatic Control, 50(2), 2005. 63 [28] P. Ogren, E. Fiorelli, and N. E. Leonard. Cooperative Control of Mobile Sensor Networks: Adaptive Gradient Climbing in a Distributed Environment. IEEE Trans. on Automatic Control, 49(8):1292–1302, August 2004. [29] R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus and Cooperation in Networked Multi-Agent Systems. Proceedings of the IEEE, Special Issue on Networked Control Systems, 95(1):215–233, 2007. [30] R. Olfati-Saber and R. M. Murray. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control, 43:1520–1533, 2004. [31] A. Papachristodoulou and A. Jadbabaie. Synchronization in oscillator networks: Switching topologies and non-homogeneous delays. Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC ’05. 44th IEEE Conference on, pages 5692–5697, Dec. 2005. [32] V.M. Preciado and G.C. Verghese. Synchronization in generalized erdos-renyi networks of nonlinear oscillators. 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC ’05., pages 4628–4633, Dec. 2005. [33] N. N. Sadeghzadeh and A. Afshar. New approaches for distributed sensor networks consensus in the presence of communication time delay. In CCDC’09: Proceedings of the 21st annual international conference on Chinese control and decision conference, pages 3675–3680, Piscataway, NJ, USA, 2009. IEEE Press. [34] A. D. Sarwate and A. G. Dimakis. The impact of mobility on gossip algorithms. In Proceedings of the 28th Annual International Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, April 2009. [35] D. P. Spanos, R. Olfati-Saber, and R. M. Murray. Distributed Sensor Fusion Using Dynamic Consensus. In IFAC World Congress, 2005. 64 [36] G. Strang. Linear algebra and its applications. Harcourt Brace Jovanovich College Publishers, third edition, 1988. [37] S. Sundaram and C. N. Hadjicostis. Distributed consensus and linear functional calculation in networks: an observability perspective. In The 6th International Conference on Information Processing in Sensor Networks, 2007. [38] S. Sundaram and C. N. Hadjicostis. Finite-Time Distributed Consensus in Graphs with Time-Invariant Topologies. In The 26th American Control Conference, New York, NY, 2007. [39] Y.-P. Tian and C.-L. Liu. Robust consensus of multi-agent systems with diverse input delays and asymmetric interconnection perturbations. Automatica, 45(5):1347–1353, 2009. [40] S. Vanka, V. Gupta, and M. Haenggi. On consensus over stochastically switching directed topologies. In ACC’09: Proceedings of the 2009 conference on American Control Conference, pages 4531–4536, Piscataway, NJ, USA, 2009. IEEE Press. [41] L. Wang and F. Xiao. Finite-time consensus problems for networks of dynamic agents. http://arxiv.org/pdf/math/0701724. [42] W. Xi, X. Tan, and J. S. Baras. A Stochastic Algorithm for Self-Organization of Autonomous Swarms. In IEEE Conference on Decision and Control, 2005. [43] L. Xiao and S. Boyd. Fast Linear Iterations for Distributed Averaging. Systems and Control Letters, 53(1):65–78, September 2004. [44] G. Xie, H. Liu, L. Wang, and Y. Jia. Consensus in networked multi-agent systems via sampled control: switching topology case. In ACC’09: Proceedings of the 2009 conference on American Control Conference, pages 4525–4530, Piscataway, NJ, USA, 2009. IEEE Press. 65 [45] H.-Y. Yang and S.-Y. Zhang. Consensus of multi-agent moving systems with heterogeneous communication delays. Int. J. Syst., Control Commun., 1(4):426– 436, 2009.