Analyzing the Implications of Network Structure in Global Optimization and Peer-to-Peer Trust

In this dissertation, we study how network structure plays an important role in two separate fields: global optimization and trust dynamics in peer-to-peer networks.
In global optimization, we consider the class of model-based search methods. Roughly speaking, these are methods in which random search is implemented according to a probability distribution or ``model" which is updated at each iteration depending upon the quality of solutions identified. We show that search for the global minimum is equivalent to search in a designated network and that the complexity of the problem can be described in terms of network structure.
By focusing on the best solutions identified, most model-based algorithms emphasize ``exploitation" over ``exploration".
Depending upon the structure of the problem, this emphasis in ``exploitation" may end up significantly slowing down the identification of the global minimum. We propose a new algorithmic design for model-based search based on multiple interacting
threads. In this design, each thread implements a model-based search and they interact through a simple acceptance-rejection rule preventing duplication of search efforts. We show that the speed of convergence (both in the worst case and on average) increases exponentially in the number of threads. Thus, in the proposed algorithmic design, exploration is a complement rather than a substitute to exploitation.
The second part of the dissertation aims to characterize the dynamics of trust in unreliable peer-to-peer networks. Distributed trust or reputation systems have naturally evolved as a potential scalable solution to ensuring data exchange in peer-to-peer networks is reliable. In a trust-based system each node maintains and updates the trust (or reputation) score of neighboring nodes. These trust coefficients are modified depending upon locally verified outcomes. For example, in a peer-to-peer file sharing system a node's trust will be decreased if neighboring nodes verify that the last file uploaded or forwarded by that node was corrupted. In this dissertation we consider the implications on network structure in distributed trust dynamics of peer-to peer networks of agents. We characterize the performance of a general class of trust-based schemes as a function of the underlying network structure. We conclude with an application to cyber security of large scale wind power system.