Show simple item record

dc.contributor.advisorMitzenmacher, Michael D.
dc.contributor.authorLiu, Zhenming
dc.date.accessioned2012-10-16T20:46:11Z
dc.date.issued2012-10-16
dc.date.submitted2012
dc.identifier.citationLiu, Zhenming. 2012. Probabilistic Algorithms for Information and Technology Flows in the Networks. Doctoral dissertation, Harvard University.en_US
dc.identifier.otherhttp://dissertations.umi.com/gsas.harvard:10553en
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:9754141
dc.description.abstractThis thesis studies several probabilistic algorithms for information and technology flow in the networks. Information flow refers to the circulation of information in social or communication networks for the purpose of disseminating or aggregating knowledge. Technology flow 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 flow acts as media to disseminate messages. The information flow 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 flooding algorithm. We give a tight characterization on the completion time of the flooding algorithm when we make natural stochastic assumptions on the evolution of the network. Second, we consider the problem that information flow acts as a device to aggregate statistics. We interpret information flow 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 flow overhead. We study these two problems: first, 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 effectiveness of using random walks to estimate the statistical properties of networks. Specifically, we give the first deviation bounds for random walks over finite state Markov chains based on mixing time properties of the chain. Finally, we study the problem where technology flow acts as a key to unlock innovative technology diffusion. Here, the technology flow 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 finding the most cost effective 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 flows to facilitate the new technology deployments.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dash.licenseLAA
dc.subjectcomputer scienceen_US
dc.titleProbabilistic Algorithms for Information and Technology Flows in the Networksen_US
dc.typeThesis or Dissertationen_US
dc.date.available2012-10-16T20:46:11Z
thesis.degree.date2012en_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.grantorHarvard Universityen_US
thesis.degree.leveldoctoralen_US
thesis.degree.namePh.D.en_US
dc.contributor.committeeMemberVadhan, Salilen_US
dc.contributor.committeeMemberValiant, Leslieen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record