dc.contributor.advisor Mitzenmacher, Michael D. dc.contributor.author Liu, Zhenming dc.date.accessioned 2012-10-16T20:46:11Z dc.date.issued 2012-10-16 dc.date.submitted 2012 dc.identifier.citation Liu, Zhenming. 2012. Probabilistic Algorithms for Information and Technology Flows in the Networks. Doctoral dissertation, Harvard University. en_US dc.identifier.other http://dissertations.umi.com/gsas.harvard:10553 en dc.identifier.uri http://nrs.harvard.edu/urn-3:HUL.InstRepos:9754141 dc.description.abstract This thesis studies several probabilistic algorithms for information and technology ﬂow in the networks. Information ﬂow refers to the circulation of information in social or communication networks for the purpose of disseminating or aggregating knowledge. Technology ﬂow refers to the process in the network in which nodes incrementally adopt a certain type of technological product such as networking protocols. In this thesis, we study the following problems. First, we consider the scenario where information ﬂow acts as media to disseminate messages. The information ﬂow here is considered as a mechanism of replicating a piece of information from one node to another in a network with a goal to “broadcast” the knowledge to everyone. Our studies focus on a broadcasting algorithm called the ﬂooding algorithm. We give a tight characterization on the completion time of the ﬂooding algorithm when we make natural stochastic assumptions on the evolution of the network. Second, we consider the problem that information ﬂow acts as a device to aggregate statistics. We interpret information ﬂow here as artifacts produced by algorithmic procedures that serve as statistical estimators for the networks. The goal is to maintain accurate estimators with minimal information ﬂow overhead. We study these two problems: ﬁrst, we consider the continual count tracking problem in a distributed environment where the input is an aggregate stream originating from $k$ distinct sites and the updates are allowed to be non-monotonic. We develop an optimal algorithm in communication cost that can continually track the count for a family of stochastic streams. Second, we study the eﬀectiveness of using random walks to estimate the statistical properties of networks. Speciﬁcally, we give the ﬁrst deviation bounds for random walks over ﬁnite state Markov chains based on mixing time properties of the chain. Finally, we study the problem where technology ﬂow acts as a key to unlock innovative technology diﬀusion. Here, the technology ﬂow shall be interpreted as a way to specify the circumstance, in which a node in the network will decide to adopt a new technology. Our studies focus on ﬁnding the most cost eﬀective way to deploy networking protocols such as SecureBGP or IPv6 in the Internet. Our result is a near optimal strategy that leverages the patterns of technology ﬂows to facilitate the new technology deployments. en_US dc.description.sponsorship Engineering and Applied Sciences en_US dc.language.iso en_US en_US dash.license LAA dc.subject computer science en_US dc.title Probabilistic Algorithms for Information and Technology Flows in the Networks en_US dc.type Thesis or Dissertation en_US dc.date.available 2012-10-16T20:46:11Z thesis.degree.date 2012 en_US thesis.degree.discipline Computer Science en_US thesis.degree.grantor Harvard University en_US thesis.degree.level doctoral en_US thesis.degree.name Ph.D. en_US dc.contributor.committeeMember Vadhan, Salil en_US dc.contributor.committeeMember Valiant, Leslie en_US
﻿