On Matrix Factorization and Scheduling for Finite-Time Average-Consensus

Author: Ko, Chih-Kai

Year: 2010

Degree: Dissertation (Ph.D.)

Advisor: Schulman, Leonard J.

Committee Members: Schulman, Leonard J.; Doyle, John Comstock; Ho, Tracey C.; Low, Steven H.; Umans, Christopher M.

Option: Electrical Engineering

DOI: 10.7907/GCT7-5Y66

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.

Files

• consensus.pdf (application/pdf)