Peer-to-Peer State Exchange: From Medium Access Control to Diffusion in Social Networks

Peer-to-peer state exchange refers to models in which peers in a network repeatedly learn the states of their neighbors and make state transitions accordingly. Its applications to diffusion of desirable behaviors in wireless and social networks are discussed in this dissertation.;In wireless networks, medium access control (MAC) can be incorporated with peer-to-peer state exchange to eliminate collisions, such that an efficient time-division multiple access (TDMA) like schedule is formed in a distributed manner after a sufficiently long time. For regular wireless networks, assuming stations can use a sufficiently large state space, where each state represents a time slot, a simple MAC protocol with peer-to-peer state exchange is proposed, which achieves the optimal throughput and is fair to every station. If only two states are allowed for each station, such that stations can only be idle or transmitting, then MAC protocols with peer-to-peer state exchange can be constructed based on the Ising model in statistical mechanics, which only result in a slight throughput degradation. For wireless networks with arbitrary topologies, multi-resolution MAC protocols are introduced, in which stations with more neighbors have larger state spaces, with each state corresponding to a shorter time slot. A station determines the size of its state space using its local topology information, or dynamically adjusts the size of its state space if necessary. Multi-resolution MAC protocols with peer-to-peer state exchange allow networks to eliminate collisions and achieve approximate proportional fairness, such that two stations with similar number of neighbors have similar rates.;In social networks, peer-to-peer state exchange models the spread of innovations. Two-sided social networks, in which there are two types of players and decisions on whether to adopt an innovation are driven by the adoptions of the opposite type, are considered. Using large-system analysis, the dynamics and equilibrium of the system are characterized, and a phase transition result is established: The innovation will spread to the entire network if and only if the initial proportions of adoptors on both sides are above a function determined by system parameters. Selection of the initial proportions of adoptors is considered in terms of cost minimization and profit maximization.