Candidate
Arpan Mukhopadhyay
Title
Mean Field Interactions in Heterogeneous Networks
Supervisor
Ravi Mazumdar
Abstract
In the context of complex networks, we often encounter systems in which the constituent entities interact with each other as they evolve randomly with time. The random evolution of the constituent entities and the system as a whole can often be described by Markov processes, constructed on suitable state spaces. For many systems (e.g. server farms, cloud data centers, social networks), analyzing these processes becomes intractable due to the complex interactions between the constituent entities of the system. However, if the `strength' of these interactions converges to a constant as the size of the system is increased, then in the large system limit the Markov process describing the time evolution of the system converges to a deterministic process, known as the mean field limit of the corresponding system. Thus, the mean field limit provides a deterministic approximation of the randomly evolving system. Such approximations are accurate for large system sizes.
Most prior works on mean field techniques have analyzed systems in which the constituent entities are identical or homogeneous. In this dissertation, we use mean field techniques to analyze large complex systems composed of heterogeneous entities.
First, we consider a class of large multi-server systems, which arise in the context of web-server farms and cloud data centers. In such systems, servers with heterogeneous capacities work in parallel to process incoming jobs or requests. We study schemes to assign incoming jobs to servers with the goal of achieving optimal performance in terms of certain metrics of interest while requiring the state information of only a small number of servers in the system. To this end, we consider randomized dynamic job assignment schemes which sample a small random subset of servers at every job arrival instant and assign the incoming job to one of the sampled servers based on their instantaneous states. We show that, for heterogeneous systems, naively sampling servers may result in instability of the system. We propose schemes which maintain stability by suitably sampling servers. The performances of these schemes are studied via the corresponding mean field limits, that are shown to exist. The existence and uniqueness of a globally attractive equilibrium point of the mean filed is established in every case. Furthermore, it is shown that, in the large system limit, the servers become independent of each other and the stationary distribution of occupancy of each server can be obtained from the unique equilibrium point of the mean field. The stationary tail distribution of server occupancies is shown to have a fast decay rate which suggests significantly improved performance for the appropriate metrics relevant to the application. Numerical studies are presented which show that the proposed randomized dynamic schemes significantly outperform randomized static schemes where job assignments are made independently of the server states. In certain scenarios, the randomized dynamic schemes are observed to be nearly optimal in terms of their performances.
Next, using mean field techniques, we study a different class of models that arise in the context of social networks. More specifically, we study the impact of social interactions on the dynamics of opinion formation in a social network, consisting of a large number of interacting social agents. The agents are assumed to be mobile and hence do not have any fixed set of neighbors. Opinion of each agent is treated as a binary random variable, taking values in the set {0,1}. This represents scenarios, where the agents have to choose from two available options. The interactions between the agents are modeled by the so called `voter' rules and `majority' based rules. Under each rule, we consider two scenarios: (1) where the agents are biased towards a specific opinion and (2) where the agents have different propensities to change their opinions. For each of these scenarios, we characterize the equilibrium distribution of opinions in the network and the convergence rate to the equilibrium by analyzing the corresponding mean field limit. Our results show that presence of biased agents can significantly reduce the convergence rate to the equilibrium. It is also observed that, under the majority rule dynamics, the presence of `stubborn’ agents (those who do not update their opinions) in the network may lead to metastability, where the opinions of the non-stubborn agents fluctuate between stable configurations.