Wireless Random-Access Networks: Fairness, Delay and Stability
Backlog-based wireless access schemes are relatively simple and inherently distributed, yet provide a striking capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. Unfortunately, the specific type of activation rules for which throughput optimality has been established, may result in excessive backlogs and delays. The use of more aggressive/persistent access schemes can improve the delay performance, but does not offer any universal maximum-stability guarantees.
In order to gain qualitative insights and examine stability properties, we investigate fluid limits where the system dynamics are scaled in space and time. Several distinct types of fluid limits can arise, ranging from ones with smooth deterministic features, to others which exhibit random oscillatory characteristics, depending on the topology of the network, in conjunction with the form of the activation rules. As we will show, these qualitatively different regimes are closely related to short-term fairness properties and mixing times for random-access mechanisms with fixed activation rates. It turns out that more aggressive access schemes continue to provide maximum stability in some networks, e.g. complete interference graphs. In other topologies however such schemes can drive the system into inefficient states and thus cause instability.
Note: based on joint work with Niek Bouman (TU/e), Javad Ghaderi (UIUC), Johan van Leeuwaarden (TU/e), Alexandre Proutiere (KTH), Peter van de Ven (IBM), Phil Whiting (Alcatel-Lucent Bell Labs), Alessandro Zocca (TU/e)
Prof. Laurent Massoulié,
The Price of Privacy in Untrusted Recommendation
Online privacy concerns prompt the following question: can a recommendation engine be accurate if end-users do not entrust it with their private data? To provide an answer, we study the problem of learning user ratings for items under so-called local differential privacy, a formal notion of data privacy. We obtain lower bounds on learning complexity based on mutual information. These results highlight the role played by the amount of ratings performed by each user. In the information-rich regime (where each user rates at least a constant fraction of items), a spectral clustering approach is shown to achieve optimal sample complexity, as it matches our information-theoretic lower bounds. In contrast, the information-scarce regime (where each user only rates a vanishing fraction of the total item set) is found to require a different approach. We thus propose the so-called MaxSense algorithm, which achieves optimal sample complexity in the information-scarce regime.
This is based on joint work with Nidhi Hegde (Technicolor) and Siddhartha Banerjee (UT Austin).
Prof. Asu Ozdaglar,
Network Security and Contagion
This work develops a theoretical model of investments in security in a network of interconnected agents. The network connections introduce the possibility of cascading failures depending on exogenous or endogenous attacks and the profile of security investments by the agents. The general presumption in the literature, based on intuitive arguments or analysis of symmetric networks, is that because security investments create positive externalities on other agents, there will be underinvestment in security. We show that this reasoning is incomplete because of a first-order economic force: security investments are also strategic substitutes. In a general (non-symmetric) network, this implies that underinvestment by some agents will encourage overinvestment by others. We demonstrate by means of examples that not only there will be overinvestment by some agents but also aggregate probabilities of infection can be lower in equilibrium than in the social optimum. We then provide sufficient conditions for underinvestment. This requires both sufficiently convex cost functions (just convexity is not enough) and networks that are either symmetric or locally tree-like (i.e., either trees or in the case of stochastic networks, without local cycles with high probability). We also characterize the impact of network structure on equilibrium and optimal investments. Finally, we show that when the attack location is endogenized (by assuming that the attacker chooses a probability distribution over the location of the attack in order to maximize damage), there is another reason for overinvestment: greater investment by an agent shifts the attack to other parts of the network.
This is joint work with Daron Acemoglu and Azarakhsh Malekian.
