Algorithmic Foundations of P2P and Wireless Networks: Scheduling Complexity, Selfishness, and Evil Attacks

Many of today’s most exciting distributed systems are large-scale and highly decentralized networks, such as peer-to-peer networks, wireless ad hoc networks, or the Internet. In this talk, I will present several recent theoretical results with practical implications in peer-to-peer and wireless networks.

Scheduling being one of the most crucial tasks in multi-hop wireless networks, it is not surprising that a multiplicity of MAC layer and scheduling protocols have been proposed. In contrast, little is known about the fundamental possibilities and limitations of scheduling. In my talk, I will introduce the ‘scheduling complexity’ as a measure for quantifying the achievable efficiency of scheduling protocols. Intuitively, the scheduling complexity captures the amount of time required to schedule a set of requests. As it turns out, all intuitive and currently employed scheduling protocols in multi-hop radio networks perform very sub-optimally even for simple request sequences when studied in realistic network models. On the other hand, a careful assignment of time slots and power levels to nodes can guarantee in every network that complicated requests are scheduled quickly. Moreover, this result implies that even in worst-case networks, there is no dramatic scaling problem when it comes to scheduling.

In the second part of my talk, I will address problems related to peer-to-peer networks in which nodes may be selfish, trying to optimize their own utility. Using a game theoretic approach, I quantify the degradation of unstructured P2P network topologies due to the peer’s selfishness. In particular, strategic behavior can create inefficiency and instability even in the absence of churn or mobility. In addition to selfishness, however, modern networks must also be able to cope with malicious Byzantine adversaries who cannot be considered rational and selfish. Instead, these adversaries seek to degrade the utility of the entire system or to attack its correctness. So far, selfishness and maliciousness have typically been studied separately. In my talk, I will present exact bounds on the impact of malicious attacks on a system consisting of selfish agents (i.e., the Price of Malice), and I will analytically capture how the ‘fear-factor’ resulting from the existence of malicious attackers among selfish agents may actually increase the system’s overall performance.