Modern planetary-scale online services have massive data to transfer over the wide area network (WAN). Due to the tremendous cost of building WANs and the stringent timing requirement of distributed applications, it is critical for network operators to make efficient use of network resources to optimize data transfers. By leveraging software-defined networking (SDN) and reconfigurable optical devices, recent solutions design centralized systems to jointly control the network layer and the optical layer. While these solutions show it is promising to significantly reduce data transfer times by centralized cross-layer control, they do not have any theoretical guarantees on the proposed algorithms. This paper presents approximation algorithms and theoretical analysis for the online transfer scheduling problem over optical WANs. The goal of the scheduling problem is to minimize the makespan (the time to finish all transfers) or the total sum of completion times. We design and analyze various greedy, online scheduling algorithms that can achieve 3-competitive ratio for makespan, 2-competitive ratio for minimum sum completion time for jobs of unit size, and 3α-competitive ratio for jobs of arbitrary transfer size and each node having degree constraint d, where α = 1 when d = 1 and α = 1.86 when d ≥ 2. We also evaluated the performance of these algorithms and compared the performance with prior heuristics.

Social behaviors and choices spread through interactions and may lead to a cascading behavior. Understanding how such social cascades spread in a network is crucial for many applications ranging from viral marketing to political campaigns. The behavior of cascade depends crucially on the model of cascade or social influence and the topological structure of the social network.

Complex contagions describe diffusion of behaviors in a social network in settings where spreading requires influence by two or more neighbors. In a k-complex contagion, a cluster of nodes are initially infected, and additional nodes become infected in the next round if they have at least k already infected neighbors. It has been argued that complex contagions better model behavioral changes such as adoption of new beliefs, fashion trends or expensive technology innovations. This has motivated rigorous understanding of spreading of complex contagions in social networks. Despite simple contagions (k=1) that spread fast in all small world graphs, how complex contagions spread is much less understood. Previous work [11] analyzes complex contagions in Kleinberg's small world model [14] where edges are randomly added according to a spatial distribution (with exponent γ) on top of a two dimensional grid structure. It has been shown in [11] that the speed of complex contagions differs exponentially when γ=0 compared to when γ=2.

We introduce the cache-adaptive model, which generalizes the external-memory model to apply to environments in which the amount of memory available to an algorithm can fluctuate. The cache-adaptive model applies to operating systems, databases, and other systems where the allocation of memory to processes changes over time. We prove that if an optimal cache-oblivious algorithm has a particular recursive structure, then it is also an optimal cache-adaptive algorithm. Cache-oblivious algorithms having this form include Floyd-Warshall all pairs shortest paths, naïve recursive matrix multiplication, matrix transpose, and Gaussian elimination. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have this recursive structure, we prove that it is nonetheless optimally cache-adaptive. We also establish that if a cache-oblivious algorithm is optimal on “square”” (well-behaved) memory profiles then, given resource augmentation it is optimal on all memory profiles. We give paging algorithms for the case where the cache size changes dynamically. We prove that LRU with 4-memory and 4-speed augmentation is competitive with optimal. Moreover, Belady's algorithm remains optimal even when the cache size changes. Cache-obliviousness is distinct from cache-adaptivity. We exhibit a cache-oblivious algorithm that is not cache-adaptive and a cache-adaptive algorithm for a problem having no optimal cache-oblivious solution.

Diseases, information and rumors could spread fast in social networks exhibiting the small world property. In the diffusion of these 'simple contagions', which can spread through a single contact, a small network diameter and the existence of weak ties in the network play important roles. Recent studies by sociologists [Centola and Macy 2007] have also explored 'complex contagions' in which multiple contacts are required for the spread of contagion. [Centola and Macy 2007] and [Romero et al. 2011] have shown that complex contagions exhibit different diffusion patterns than simple ones. In this paper, we study three small world models and provide rigorous analysis on the diffusion speed of a k-complex contagion, in which a node becomes active only when at least k of its neighbors are active. Diffusion of a complex contagion starts from a constant number of initial active nodes. We provide upper and lower bounds on the number of rounds it takes for the entire network to be activated. Our results show that compared to simple contagions, weak ties are not as effective in spreading complex contagions due to the lack of simultaneous active contacts; and the diffusion speed depends heavily on the the way weak ties are distributed in a network.