Root cause analysis (RCA) is critical for maintaining the availability and efficiency of cloud computing systems. However, identifying root causes from the large-scale, high-dimensional monitoring data generated by these complex environments is a significant challenge. Current approaches often rely on time-consuming manual analysis to ensure flexibility and reliability, while recent automated methods lack the crucial insights provided by domain experts. To bridge this gap, we propose RCInvestigator, a visual analytics system that facilitates interactive root cause investigation by establishing a tight collaboration between human experts and machine analysis. Our approach addresses three key challenges: a) modeling databases for the root cause investigation, b) inferring root causes from large-scale time series, and c) building comprehensible investigation results. We demonstrate the effectiveness and utility of RCInvestigator through two real-world case studies, which received positive feedback from domain experts.

The advent of abundant image data has catalyzed the advancement of visual control in reinforcement learning (RL) systems, leveraging multiple view- points to capture the same physical states, which could enhance control performance theoretically. However, integrating multi-view data into representation learning remains challenging. In this paper, we introduce SMuCo, an innovative multi-view reinforcement learning algorithm that constructs robust latent representations by optimizing multi- view sequential total correlation. This technique effectively captures task-relevant information and temporal dynamics while filtering out irrelevant data. Our method supports an unlimited number of views and demonstrates superior performance over leading model-free and model-based RL algorithms. Empirical results from the DeepMind Control Suite and the Sapien Basic Manipulation Task confirm SMuCo’s enhanced efficacy, significantly improving task performance across diverse scenarios and views.

Offline reinforcement learning faces a significant challenge of value over-estimation due to the distributional drift between the dataset and the current learned policy, leading to learning failure in practice. The common approach is to incorporate a penalty term to reward or value estimation in the Bellman iterations. Meanwhile, to avoid extrapolation on out-of-distribution (OOD) states and actions, existing methods focus on conservative Q-function estimation. In this paper, we propose Conservative State Value Estimation (CSVE), a new approach that learns conservative V-function via directly imposing penalty on OOD states. Compared to prior work, CSVE allows more effective state value estimation with conservative guarantees and further better policy optimization. Further, we apply CSVE and develop a practical actor-critic algorithm in which the critic does the conservative value estimation by additionally sampling and penalizing the states around the dataset, and the actor applies advantage weighted updates extended with state exploration to improve the policy. We evaluate in classic continual control tasks of D4RL, showing that our method performs better than the conservative Q-function learning methods and is strongly competitive among recent SOTA methods.

This paper investigates a critical resource allocation problem in the first party cloud: scheduling containers to machines. There are tens of services, and each service runs a set of homogeneous containers with dynamic resource usage; containers of a service are scheduled daily in a batch fashion. This problem can be naturally formulated as Stochastic Bin Packing Problem (SBPP). However, traditional SBPP research often focuses on cases of empty machines, whose objective, i.e., to minimize the number of used machines, is not well-defined for the more common reality with nonempty machines. This paper aims to close this gap. First, we define a new objective metric, Used Capacity at Confidence (UCaC), which measures the maximum used resources at a probability and is proved to be consistent for both empty and nonempty machines and reformulate the SBPP under chance constraints. Second, by modeling the container resource usage distribution in a generative approach, we reveal that UCaC can be approximated with Gaussian, which is verified by trace data of real-world applications. Third, we propose an exact solver by solving the equivalent cutting stock variant as well as two heuristics-based solvers -- UCaC best fit, bi-level heuristics. We experimentally evaluate these solvers on both synthetic datasets and real application traces, demonstrating our methodology's advantage over traditional SBPP optimal solver minimizing the number of used machines, with a low rate of resource violations.

Capacity management has always been a great challenge for cloud platforms due to massive, heterogeneous on-demand instances running at different times. To better plan the capacity for the whole platform, a class of cloud computing instances have been released to collect computing demands beforehand. To use such instances, users are allowed to submit jobs to run for a pre-specified uninterrupted duration in a flexible range of time in the future with a discount compared to the normal on-demand instances. Proactively scheduling those pre-collected job requests considering the capacity status over the platform can greatly help balance the computing workloads along time. In this work, we formulate the scheduling problem for these pre-collected job requests under uncertain available capacity as a Prediction + Optimization problem with uncertainty in constraints, and propose an effective algorithm called Controlling under Uncertain Constraints (CUC), where the predicted capacity guides the optimization of job scheduling and job scheduling results are leveraged to improve the prediction of capacity through Bayesian optimization. The proposed formulation and solution are commonly applicable for proactively scheduling problems in cloud computing. Our extensive experiments on three public, industrial datasets shows that CUC has great potential for supporting high reliability in cloud platforms.

For proof-of-work blockchains such as Ethereum, the mining power decentralization is an important discussion point in the community. Previous studies mostly focus on the aggregated power of the mining pools, neglecting the pool participants who are the source of the pools' power. In this paper, we present the first large-scale study of the pool participants in Ethereum's mining pools. Pool participants are not directly observable because they communicate with their pools via private channels. However, they leave "footprints" on chain as they use Ethereum accounts to anonymously receive rewards from mining pools. For this study, we combine several data sources to identify 62,358,646 pool reward transactions sent by 47 pools to their participants over Ethereum's entire near 5-year history. Our analyses about these transactions reveal interesting insights about three aspects of pool participants: the power decentralization at the participant level, their pool-switching behavior, and why they participate in pools. Our results provide a complementary and more balanced view about Ethereum's mining power decentralization at a deeper level.

In cloud systems, an accurate capacity planning is very important for cloud provider to improve service availability. Traditional methods simply predicting "when the available resources is exhausted" are not effective due to customer demand fragmentation and platform allocation constraints. In this paper, we propose a novel prediction approach which proactively predicts the level of resource allocation failures from the perspective of low capacity status. By jointly considering the data from different sources in both time series form and static form, the proposed approach can make accurate LCS predictions in a complex and dynamic cloud environment, and thereby improve the service availability of cloud systems. The proposed approach is evaluated by real-world datasets collected from a large scale public cloud platform, and the results confirm its effectiveness.

The use of containers in microservices has gained popularity as it facilitates agile development, resource governance, and software maintenance. Container reallocation aims to achieve workload balance via reallocating containers over physical machines. It affects the overall performance of microservice-based systems. However, container scheduling and reallocation remain an open issue due to their complexity in real-world scenarios. In this paper, we propose a novel Multi-Phase Local Search (MPLS) algorithm to optimize container reallocation. The experimental results show that our optimization algorithm outperforms state-of-the-art methods. In practice, it has been successfully applied to Microsoft 365 system to mitigate hotspot machines and balance workloads across the entire system.

Despite years of research attention, localization-based indoor navigation has not found wide-spread practical use, largely due to the high burden on deployment and bootstrapping. Lightweight peer-to-peer navigation systems that use a leader-follower model have recently been proposed to alleviate these burdens. However, typical peer-to-peer navigation suffers from poor scalability and flexibility as navigation is only possible over pre-collected leader paths. In this paper, we present FollowUs, an easily-deployable (bootstrap-free) and scalable indoor navigation system. In addition to robust navigation through real-time trace-following, FollowUs integrates cloud services to process and combine traces at large scale. Optionally, it can also leverage floor plans to further enhance navigation efficiency. We design and implement FollowUs, including mobile app and cloud services. Experimental results from a company-internal beta release show that 91% of FollowUs' spatial errors on reaching destinations to be 3m or less, and 95% of navigation instructions are shown to users within a 4-step error margin during navigation.

RDMA is becoming prevalent because of its low latency, high throughput and low CPU overhead. However, in current datacenters, RDMA remains a single path transport which is prone to failures and falls short to utilize the rich parallel network paths. Unlike previous multi-path approaches, which mainly focus on TCP, this paper presents a multi-path transport for RDMA, i.e. MP-RDMA, which efficiently utilizes the rich network paths in datacenters. MP-RDMA employs three novel techniques to address the challenge of limited RDMA NICs on-chip memory size: 1) a multi-path ACK-clocking mechanism to distribute traffic in a congestion-aware manner without incurring per-path states; 2) an out-of-order aware path selection mechanism to control the level of out-of-order delivered packets, thus minimizes the meta data required to them; 3) a synchronise mechanism to ensure in-order memory update whenever needed. With all these techniques, MP-RDMA only adds 66B to each connection state compared to single-path RDMA. Our evaluation with an FPGA-based prototype demonstrates that compared with single-path RDMA, MP-RDMA can significantly improve the robustness under failures ( $2\times \sim 4\times $ higher throughput under 0.5%~10% link loss ratio) and improve the overall network utilization by up to 47%.

Crowdsensing systems collect large-scale sensor data from mobile devices to provide a wide-area view of phenomena including traffic, noise and air pollution. Because such data often exhibits sparse structure, it is natural to apply compressive sensing (CS) for data sampling and recovery. However in practice, crowd participants are often distributed highly unevenly across the sensing area, and thus the numbers of observations collected over different areas may vary wildly - an issue we call density disparity. Density disparity leads to inaccuracy in low density areas, and potentially undermines the recovery performance if conventional compressive sensing is applied directly, which equally treats data from areas of different density.

Bootstrapping efforts and scalability issues hinder large-scale deployment of indoor navigation systems. We present FollowUs, an easily-deployable (bootstrap-free) and scalable indoor navigation system. In addition to robust navigation through real-time trace-following, FollowUs integrates cloud services to process and combine traces at large scale. It can also leverage optional floor plans to further enhance navigation performance. We designed and implemented FollowUs, including a mobile app and cloud services on Azure, and validate its real-world usability.

Modern data analytical tasks often witness very wide tables, from a few hundred columns to a few thousand. While it is commonly agreed that column stores are an appropriate data format for wide tables and analytical workloads, the physical order of columns has not been investigated. Column ordering plays a critical role in I/O performance, because in wide tables accessing the columns in a single horizontal partition may involve multiple disk seeks. An optimal column ordering will incur minimal cumulative disk seek costs for the set of queries applied to the data. In this paper, we aim to find such an optimal column layout to maximize I/O performance. Specifically, we study two problems for column stores on HDFS: column ordering and column duplication. Column ordering seeks an approximately optimal order of columns; column duplication complements column ordering in that some columns may be duplicated multiple times to reduce contention among the queries' diverse requirements on the column order. We consider an actual fine-grained cost model for column accesses and propose algorithms that take a query workload as input and output a column ordering strategy with or without storage redundancy that significantly improves the overall I/O performance. Experimental results over real-life data and production query workloads confirm the effectiveness of the proposed algorithms in diverse settings.

Large-scale public cloud providers invest billions of dollars into their cloud infrastructure and operate hundreds of thousands of servers across the globe. For various reasons, much of this provisioned server capacity runs at low average utilization, and there is tremendous competitive pressure to increase utilization. Conceptually, the way to increase utilization is clear: Run time-insensitive batch-job workloads as secondary background tasks whenever server capacity is underutilized; and evict these workloads when the server's primary task requires more resources. Big data analytic tasks would seem to be an ideal fit to run opportunistically on such transient resources in the cloud. In reality, however, modern distributed data processing systems such as MapReduce or Spark are designed to run as the primary task on dedicated hardware, and they perform badly on transiently available resources because of the excessive cost of cascading re-computations in case of evictions.

Behavior in classroom-based courses is hard to measure at large-scale. In this paper, we propose the EDUM (EDUcation Measurement) system to help characterize educational behavior through data collected from WLANs (WiFi networks) on campuses. EDUM characterizes students' punctuality (attendances, late arrivals, and early departures) for lectures using longitudinal WLAN data, and further characterizes the attractiveness of lectures using mobile phone's interactive states at minute-scale granularity. EDUM is easy to deploy and extensible for new types of data. We deploy EDUM at Tsinghua University where ~700 volunteer students' data are measured during a 9-week period by ~2,800 APs and two popular mobile apps. Our results show that EDUM makes it possible to obtain large-scale observations on punctuality, distraction and study performance, and quantitatively confirm or disprove numerous assumptions about educational behavior.

In this paper, we study information cascades on graphs. In this setting, each node in the graph represents a person. One after another, each person has to take a decision based on a private signal as well as the decisions made by earlier neighboring nodes. Such information cascades commonly occur in practice and have been studied in complete graphs where everyone can overhear the decisions of every other player. It is known that information cascades can be fragile and based on very little information, and that they have a high likelihood of being wrong. Generalizing the problem to arbitrary graphs reveals interesting insights. In particular, we show that in a random graph G(n,q), for the right value of q, the number of nodes making a wrong decision is logarithmic in n. That is, in the limit for large n, the fraction of players that make a wrong decision tends to zero. This is intriguing because it contrasts to the two natural corner cases: empty graph (everyone decides independently based on his private signal) and complete graph (all decisions are heard by all nodes). In both of these cases a constant fraction of nodes make a wrong decision in expectation. Thus, our result shows that while both too little and too much information sharing causes nodes to take wrong decisions, for exactly the right amount of information sharing, asymptotically everyone can be right. We further show that this result in random graphs is asymptotically optimal for any topology, even if nodes follow a globally optimal algorithmic strategy. Based on the analysis of random graphs, we explore how topology impacts global performance and construct an optimal deterministic topology among layer graphs.

In this paper, we develop a new aggregation technique to reduce the cost of surveying. Our method aims to jointly estimate a vector of target quantities such as public opinion or voter intent across time and maintain good estimates when using only a fraction of the data. Inspired by the James-Stein estimator, we resolve this challenge by shrinking the estimates to a global mean which is assumed to have a sparse representation in some known basis. This assumption has lead to two different methods for estimating the global mean: orthogonal matching pursuit and deep learning. Both of which significantly reduce the number of samples needed to achieve good estimates of the true means of the data and, in the case of presidential elections, can estimate the outcome of the 2012 United States elections while saving hundreds of thousands of samples and maintaining accuracy.

WiFi latency is a key factor impacting the user experience of modern mobile applications, but it has not been well studied at large scale. In this paper, we design and deploy WiFiSeer, a framework to measure and characterize WiFi latency at large scale. WiFiSeer comprises a systematic methodology for modeling the complex relationships between WiFi latency and a diverse set of WiFi performance metrics, device characteristics, and environmental factors. WiFiSeer was deployed on Tsinghua campus to conduct a WiFi latency measurement study of unprecedented scale with more than 47,000 unique user devices. We observe that WiFi latency follows a long tail distribution and the 90th (99th) percentile is around 20 ms (250 ms). Furthermore, our measurement results quantitatively confirm some anecdotal perceptions about impacting factors and disapprove others. We deploy three practical solutions for improving WiFi latency in Tsinghua, and the results show significantly improved WiFi latencies. In particular, over 1,000 devices use our AP selection service based on a predictive WiFi latency model for 2.5 months, and 72% of their latencies are reduced by over half after they re-associate to the suggested APs.

As an innovative mobility strategy, public bike-sharing has grown dramatically worldwide. Though providing convenient, low-cost and environmental-friendly transportation, the unique features of bike-sharing systems give rise to problems to both users and operators. The primary issue among these problems is the uneven distribution of bicycles caused by the ever-changing usage and (available) supply. This bicycle imbalance issue necessitates efficient bike re-balancing strategies, which depends highly on bicycle mobility modeling and prediction. In this paper, for the first time, we propose a spatio-temporal bicycle mobility model based on historical bike-sharing data, and devise a traffic prediction mechanism on a per-station basis with sub-hour granularity. We extensively evaluated the performance of our design through a one-year dataset from the world's largest public bike-sharing system (BSS) with more than 2800 stations and over 103 million check in/out records. Evaluation results show an 85 percentile relative error of 0.6 for both check in and check out prediction. We believe this new mobility modeling and prediction approach can advance the bike re-balancing algorithm design and pave the way for the rapid deployment and adoption of bike-sharing systems across the globe.

The question of what can be computed, and how efficiently, is at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a distributed fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first polylogarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition, we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, whereas for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks.

In a basic economic system, each participant receives a (financial) reward according to his own contribution to the system. In this work, we study an alternative approach — Incentive Networks — in which a participant's reward depends not only on his own contribution; but also in part on the contributions made by his social contacts or friends. We show that the key parameter effecting the efficiency of such an Incentive Network-based economic system depends on the participant's degree of directed altruism. Directed altruism is the extent to which someone is willing to work if his work results in a payment to his friend, rather than to himself. Specifically, we characterize the condition under which an Incentive Network-based economy is more efficient than the basic "pay-for-your-contribution" economy. We quantify by how much incentive networks can reduce the total reward that needs to be paid to the participants in order to achieve a certain overall contribution. Finally, we study the impact of the network topology and various exogenous parameters on the efficiency of incentive networks. Our results suggest that in many practical settings, Incentive Network-based reward systems or compensation structures could be more efficient than the ubiquitous 'pay-for-your-contribution' schemes.

Mobile crowdsourcing is a powerful tool for collecting data of various types. The primary bottleneck in such systems is the high burden placed on the user who must manually collect sensor data or respond in-situ to simple queries (e.g., experience sampling studies). In this work, we present Compressive CrowdSensing (CCS) -- a framework that enables compressive sensing techniques to be applied to mobile crowdsourcing scenarios. CCS enables each user to provide significantly reduced amounts of manually collected data, while still maintaining acceptable levels of overall accuracy for the target crowd-based system. Naïve applications of compressive sensing do not work well for common types of crowdsourcing data (e.g., user survey responses) because the necessary correlations that are exploited by a sparsifying base are hidden and non-trivial to identify. CCS comprises a series of novel techniques that enable such challenges to be overcome. We evaluate CCS with four representative large-scale datasets and find that it is able to outperform standard uses of compressive sensing, as well as conventional approaches to lowering the quantity of user data needed by crowd systems.

The popularity of QR code clearly indicates the strong demand of users to acquire (or pull) further information from interested sources (e.g., a poster) in the physical world. However, existing information pulling practices such as a mobile search or QR code scanning incur heavy user involvement to identify the targeted posters. Meanwhile, businesses (e.g., advertisers) are also interested to learn about the behaviors of potential customers such as where, when, and how users show interests in their offerings. Unfortunately, little such context information are provided by existing information pulling systems. In this paper, we present Contextual-Code (C-Code) - an information pulling system that greatly relieves users' efforts in pulling information from targeted posters, and in the meantime provides rich context information of user behavior to businesses. C-Code leverages the rich contextual information captured by the smartphone sensors to automatically disambiguate information sources in different contexts. It assigns simple codes (e.g., a character) to sources whose contexts are not discriminating enough. To pull the information from an interested source, users only need to input the simple code shown on the targeted source. Our experiments demonstrate the effectiveness of C-Code design. Users can effectively and uniquely identify targeted information sources with an average accuracy over 90%.

Compressive Sensing is a technique that can help reduce the sampling rate of sensing tasks. In mobile crowdsensing applications or wireless sensor networks, the resource burden of collecting samples is often a major concern. Therefore, compressive sensing is a promising approach in such scenarios. An implicit assumption underlying compressive sensing -- both in theory and its applications -- is that every sample has the same cost: its goal is to simply reduce the number of samples while achieving a good recovery accuracy. In many networked sensing systems, however, the cost of obtaining a specific sample may depend highly on the location, time, condition of the device, and many other factors of the sample.

Computing outliers and related statistical aggregation functions from large-scale big data sources is a critical operation in many cloud computing scenarios, e.g. service quality assurance, fraud detection, or novelty discovery. Such problems commonly have to be solved in a distributed environment where each node only has a local slice of the entirety of the data. To process a query on the global data, each node must transmit its local slice of data or an aggregated subset thereof to a global aggregator node, which can then compute the desired statistical aggregation function. In this context, reducing the total communication cost is often critical to the overall efficiency.

Different battery chemistries perform better on different axes, such as energy density, cost, peak power, recharge time, longevity, and efficiency. Mobile system designers are constrained by existing technology, and are forced to select a single chemistry that best meets their diverse needs, thereby compromising other desirable features. In this paper, we present a new hardware-software system, called Software Defined Battery (SDB), which allows system designers to integrate batteries of different chemistries. SDB exposes APIs to the operating system which control the amount of charge flowing in and out of each battery, enabling it to dynamically trade one battery property for another depending on Application And/Or User Needs. Using microbenchmarks from our prototype SDB implementation, and through detailed simulations, we demonstrate that it is possible to combine batteries which individually excel along different axes to deliver an enhanced collective performance when compared to traditional battery packs.

Partial aggregation is of great importance in many distributed data-parallel systems. Most notably, it is commonly applied by MapReduce programs to optimize I/O by successively aggregating partially reduced results into a final result, as opposed to aggregating all input records at once. In spite of its importance, programmers currently enable partial aggregation by tediously encoding their reduce functionality into separate reduce and combine functions. This is error prone and often leads to missed optimization opportunities.

Diversity in training data density and environment locality is intrinsic in the real-world deployment of indoor localization systems and has a major impact on the performance of existing localization approaches. In this paper, through micro-benchmarks, we find that fingerprint-based approaches are preferable in scenarios where a dense database is available; while model-based approaches are the method of choice in the case of sparse data. It should be noted, however, that practical situations are complex. A single deployment often features both sparse and dense sampled areas. Furthermore, the internal layout affects the propagation of radio signals and exhibits environmental impacts. A certain number of measurement samples may be sufficient for one part of the building, but entirely insufficient for another. Thus, finding the right indoor localization algorithm for a given large-scale deployment is challenging, if not impossible; there is no one-size-fits-all indoor localization approach.

Data gathering is one of the core algorithmic and theoretic problems in wireless sensor networks. In this paper, we propose a novel approach - Compressed Sparse Functions - to efficiently gather data through the use of highly sophisticated Compressive Sensing techniques. The idea of CSF is to gather a compressed version of a satisfying function (containing all the data) under a suitable function base, and to finally recover the original data. We show through theoretical analysis that our scheme significantly outperforms state-of-the-art methods in terms of efficiency, while matching them in terms of accuracy. For example, in a binary tree-structured network of n nodes, our solution reduces the number of packets from the best-known O(kn log n) to O(k log2n), where k is a parameter depending on the correlation of the underlying sensor data. Finally, we provide simulations showing that our solution can save up to 80% of communication overhead in a 100-node network. Extensive simulations further show that our solution is robust, high-capacity and low-delay.

Email is a key application used on smartphones. Even when the phone is in stand-by mode, users expect the phone to continue syncing with an email server to receive new mes-sages. Each such sync operation wakes up the smartphone for data reception and processing. In this paper, we show that this "cost of email sync" in stand-by mode constitutes a significant source of energy consumption, and thus reduces battery life. We quantify the power performance of different existing email clients on two smartphone platforms, An-droid and Windows Phone, and study the impact of system parameters such as email size, inbox size, and pull vs. push. Our results show that existing email clients do not handle email sync in an energy efficient way. This is because the underlying protocols and architectures are not designed for the specific needs of operating in stand-by mode. Based on our findings, we derive general design principles for energy-efficient event handling on smartphones, and apply these principles to the case of email sync and implement our techniques on commercial smartphones. Experimental results show that our techniques are able to significantly reduce energy cost of email sync by 49.9% on average with our experiment settings.

We study Incentive Tree for motivating the participation of people in crowdsourcing or human tasking systems. In an Incentive Tree, each participant is rewarded for contributing to the system, as well as for soliciting new participants into the system, who then themselves contribute to it and/or themselves solicit new participants. An Incentive Tree mechanism is an algorithm that determines how much reward each individual participant receives based on all the participants' contributions, as well as the structure of the solicitation tree. The sum of rewards paid by the mechanism to all participants is linear in the sum of their total contribution.

Mobile gaming is a big driver of app marketplaces. However, few mobile games deliver truly distinctive gameplay experiences for ad hoc collocated users. As an example of such an experience, consider a sword fight dual between two users facing each other where each user's phone simulates a sword. With phone in hand, the users' thrusts and blocks translate to attacks and counterattacks in the game. Such Phone-to-Phone Mobile Motion Games (MMG) represent interesting and novel gameplay for ad hoc users in the same location. One enabler for an MMG game like sword fight is continuous, accurate distance ranging. Existing ranging schemes cannot meet the stringent requirements of MMG games: speed, accuracy, and noise robustness. In this work, we design FAR, a new ranging scheme that can localize at 12 Hz with 2-cm median error while withstanding up to 0-dB noise, multipath, and Doppler effect issues. Our implementation runs on commodity smartphones and does not require any external infrastructure. Moreover, distance measurement accuracy is comparable to that of Kinect, a fixed-infrastructure motion capture system. Evaluation on users playing two prototype games indicate that FAR can fully support dynamic game motion in real time.

The computation core of many data-intensive applications can be best expressed as matrix computations. The MadLINQ project addresses the following two important research problems: the need for a highly scalable, efficient and fault-tolerant matrix computation system that is also easy to program, and the seamless integration of such specialized execution engines in a general purpose data-parallel computing system.

Mobile gaming is a big driver of app marketplaces. However, few mobile games deliver truly distinctive gameplay experiences for ad hoc collocated users. As an example of such an experience, consider a sword fight dual between two users facing each other where each user's phone simulates a sword. With phone in hand, the users' thrusts and blocks translate to attacks and counterattacks in the game. Such Phone-to-Phone Mobile Motion Games (MMG) represent interesting and novel gameplay for ad hoc users in the same location. One enabler for an MMG game like sword fight is continuous, accurate distance ranging. Existing ranging schemes cannot meet the stringent requirements of MMG games: speed, accuracy and noise robustness. In this work, we design FAR, a new ranging scheme that can localize at 12Hz with 2cm median error while withstanding up to 0dB noise, multipath and Doppler effect issues. Our implementation runs on commodity smartphones and does not require any external infrastructure. Moreover, distance measurement accuracy is comparable to that of Kinect, a fixed-infrastructure motion capture system. Evaluation on users playing two prototype games indicate that FAR can fully support dynamic game motion in real-time.

In the Byzantine agreement problem, a set of n processors, any f of whom may be arbitrarily faulty, must reach agreement on a value proposed by one of the correct processors. It is a celebrated result that unless n > 3f, Byzantine agreement is impossible in a variety of computation and communication models. This is due to the fact that faulty processors can equivocate, that is, say different things to different processors. If this ability is mitigated, for example by assuming a global broadcast channel, then n > 2f is sufficient. With very few exceptions, the literature on Byzantine agreement has been confined to the n > 2f and n > 3f paradigms.

In this paper, we present network-on-chip (NoC) design and contrast it to traditional network design, highlighting similarities and differences between the two. As an initial case study, we examine network congestion in bufferless NoCs. We show that congestion manifests itself differently in a NoC than in traditional networks. Network congestion reduces system throughput in congested workloads for smaller NoCs (16 and 64 nodes), and limits the scalability of larger bufferless NoCs (256 to 4096 nodes) even when traffic has locality (e.g., when an application's required data is mapped nearby to its core in the network). We propose a new source throttling-based congestion control mechanism with application-level awareness that reduces network congestion to improve system performance. Our mechanism improves system performance by up to 28% (15% on average in congested workloads) in smaller NoCs, achieves linear throughput scaling in NoCs up to 4096 cores (attaining similar performance scalability to a NoC with large buffers), and reduces power consumption by up to 20%. Thus, we show an effective application of a network-level concept, congestion control, to a class of networks -- bufferless on-chip networks -- that has not been studied before by the networking community.

The 2010 FCC ruling on white spaces proposes relying on a database of incumbents as the primary means of determining white space availability at any white space device (WSD). While the ruling provides broad guidelines for the database, the specifics of its design, features, implementation, and use are yet to be determined. Furthermore, architecting a network where all WSDs rely on the database raises several systems and networking challenges that have remained unexplored. Also, the ruling treats the database only as a storehouse for incumbents. We believe that the mandated use of the database has an additional opportunity: a means to dynamically manage the RF spectrum. Motivated by this opportunity, in this paper, we present SenseLess, a database-driven white spaces network. As suggested by its very name, in SenseLess, WSDs rely on a database service to determine white spaces availability as opposed to spectrum sensing. The service, using a combination of an up-to-date database of incumbents, sophisticated signal propagation modeling, and an efficient content dissemination mechanism to ensure efficient, scalable, and safe white space network operation. We build, deploy, and evaluate SenseLess and compare our results to ground truth spectrum measurements. We present the unique system design considerations that arise due to operating over the white spaces. We also evaluate its efficiency and scalability. To the best of our knowledge, this is the first paper that identifies and examines the systems and networking challenges that arise from operating a white space network, which is solely dependent on a channel occupancy database.

Energy has become a first-class design constraint in computer systems. Memory is a significant contributor to total system power. This paper introduces Flikker, an application-level technique to reduce refresh power in DRAM memories. Flikker enables developers to specify critical and non-critical data in programs and the runtime system allocates this data in separate parts of memory. The portion of memory containing critical data is refreshed at the regular refresh-rate, while the portion containing non-critical data is refreshed at substantially lower rates. This partitioning saves energy at the cost of a modest increase in data corruption in the non-critical data. Flikker thus exposes and leverages an interesting trade-off between energy consumption and hardware correctness. We show that many applications are naturally tolerant to errors in the non-critical data, and in the vast majority of cases, the errors have little or no impact on the application's final outcome. We also find that Flikker can save between 20-25% of the power consumed by the memory sub-system in a mobile device, with negligible impact on application performance. Flikker is implemented almost entirely in software, and requires only modest changes to the hardware.

TV white spaces offer an exciting opportunity for increasing spectrum availability, but white space devices (WSDs) cannot interfere with primary users, including TV channels and wireless microphones (mics). Mics are particularly challenging because their use is dynamic and it is hard to avoid interference since mic receivers are receive-only devices. For this reason the FCC and other regulatory agencies have made very conservatives rules that require WSDs to vacate any TV channel that is used by a mic. However, our measurements show that mics typically require only 5% of a channel, wasting as much as 95% of the spectrum.

Main memory is a major shared resource among cores in a multicore system. If the interference between different applications' memory requests is not controlled effectively, system performance can degrade significantly. Previous work aimed to mitigate the problem of interference between applications by changing the scheduling policy in the memory controller, i.e., by prioritizing memory requests from applications in a way that benefits system performance.

The memory consistency model is a fundamental system property characterizing a multiprocessor. The relative merits of strict versus relaxed memory models have been widely debated in terms of their impact on performance, hardware complexity and programmability. This paper adds a new dimension to this discussion: the impact of memory models on software reliability. By allowing some instructions to reorder, weak memory models may expand the window between critical memory operations. This can increase the chance of an undesirable thread-interleaving, thus allowing an otherwise-unlikely concurrency bug to manifest. To explore this phenomenon, we define and study a probabilistic model of shared-memory parallel programs that takes into account such reordering. We use this model to formally derive bounds on the vulnerability to concurrency bugs of different memory models. Our results show that for 2 concurrent threads, weaker memory models do indeed have a higher likelihood of allowing bugs. On the other hand, we show that as the number of parallel, buggy threads increases, the gap between the different memory models becomes proportionally insignificant, and thus the importance of using a strict memory model diminishes.

We study the behavior of mutual exclusion algorithms in the presence of unreliable shared memory subject to transient memory faults. It is well-known that classical 2-process mutual exclusion algorithms, such as Dekker and Peterson’s algorithms, are not faulttolerant; in this paper we ask what degree of fault tolerance can be achieved using the same restricted resources as Dekker and Peterson’s algorithms, namely, three binary read/write registers. We show that if one memory fault can occur, it is not possible to guarantee both mutual exclusion and deadlock-freedom using three binary registers; this holds in general when fewer than2f+1 binary registers are used and f may be faulty. Hence we focus on algorithms that guarantee (a) mutual exclusion and starvationfreedom in fault-free executions, and (b) only mutual exclusion in faulty executions. We show that using only three binary registers it is possible to design an 2-process mutual exclusion algorithm which tolerates a single memory fault in this manner. Further, by replacing one read/write register with a test&set register, we can guarantee mutual exclusion in executions where one variable experiences unboundedly many faults. In the more general setting where up tof registers may be faulty, we show that it is not possible to guarantee mutual exclusion using 2f +1 binary read/write registers if each faulty register can exhibit unboundedly many faults. On the positive side, we show that an n-variable single-fault tolerant algorithm satisfying certain conditions can be transformed into an ((n − 1)f + 1)-variable f-fault tolerant algorithm with the same progress guarantee as the original. In combination with our three-variable algorithm, this implies that there is a(2f+1)-variable mutual exclusion algorithm tolerating a single fault in up tof variables without violating mutual exclusion.

High-speed, locational, phone-to-phone (HLPP) games and apps constitute a provocative class of mobile apps that are currently unsupported on commodity mobile devices. This work looks at a key problem for enabling HLPP: a specific variant of the localization problem in which two phones estimate each other's relative positions in 3D space without infrastructure support. Moreover, position estimates should reflect changes due to the phones' possible mobility.

We present a demonstration of a phone-to-phone Sword Fight! game. It utilizes our solution for achieving high speed 3D continuous localization described in the accompanying conference paper [1]. The approach uses acoustic cues based on time-difference of arrival and power level. It assumes at least two microphones and one speaker per phone, which is common on new smartphones. Accelerometers and digital compasses assist in resolving ambiguous acoustic-only localization. Continuous localization is achieved with the aid of a loose time synchronization protocol and a Kalman filter. Lastly, practical gameplay issues are addressed.

DRAM is facing severe scalability challenges in sub-45nm tech- nology nodes due to precise charge placement and sensing hur- dles in deep-submicron geometries. Resistive memories, such as phase-change memory (PCM), already scale well beyond DRAM and are a promising DRAM replacement. Unfortunately, PCM is write-limited, and current approaches to managing writes must de- commission pages of PCM when the first bit fails.

In this paper, we present network-on-chip (NoC) design and contrast it to traditional network design, highlighting core differences between NoCs and traditional networks. As an initial case study, we examine network congestion in bufferless NoCs. We show that congestion manifests itself differently in a NoC than in a traditional network, and with application-level awareness in the network to make proper throttling decisions we improve system performance by up to 28%. It is our hope that the unique and interesting challenges of on-chip network design can be met by novel and effective solutions from the networking community.

In this paper, we study the theory of collaborative upload bandwidth measurement in peer-to-peer environments. A host can use a bandwidth estimation probe to determine the bandwidth between itself and any other host in the system. The problem is that the result of such a measurement may not necessarily be the sender's upload bandwidth, since the most bandwidth restricted link on the path could also be the receiver's download bandwidth. In this paper, we formally define the bandwidth determination problem and devise efficient distributed algorithms. We consider two models, the free-departure and no-departure model, depending on whether hosts keep participating in the algorithm even after their bandwidth has been determined. We present lower bounds on the time-complexity of any collaborative bandwidth measurement algorithm in both models. We then show how, for realistic bandwidth distributions, the lower bounds can be overcome. Specifically, we present O(1) and O(log log n)-time algorithms for the two models. We corroborate these theoretical findings with practical measurements on a implementation on PlanetLab.

Traditional Network-on-Chips (NoCs) employ simple arbitration strategies, such as round-robin or oldest-first, to decide which packets should be prioritized in the network. This is counter-intuitive since different packets can have very different effects on system performance due to, e.g., different level of memory-level parallelism (MLP) of applications. Certain packets may be performance-critical because they cause the processor to stall, whereas others may be delayed for a number of cycles with no effect on application-level performance as their latencies are hidden by other outstanding packets'latencies. In this paper, we define slack as a key measure that characterizes the relative importance of a packet. Specifically, the slack of a packet is the number of cycles the packet can be delayed in the network with no effect on execution time. This paper proposes new router prioritization policies that exploit the available slack of interfering packets in order to accelerate performance-critical packets and thus improve overall system performance. When two packets interfere with each other in a router, the packet with the lower slack value is prioritized. We describe mechanisms to estimate slack, prevent starvation, and combine slack-based prioritization with other recently proposed application-aware prioritization mechanisms.

ThunderDome is a system for collaboratively measuring upload bandwidths in ad-hoc peer-to-peer systems. It works by scheduling bandwidth probes between pairs of hosts, wherein each pairwise exchange reveals the upload constraint of one participant. Using the abstraction of bandwidth tournaments, unresolved hosts are successively paired with each other until every peer knows its upload bandwidth. To recover from measurement errors that corrupt its tournament schedule, ThunderDome aggregates multiple probe results for each host, avoiding pathological bandwidth estimations that would otherwise occur in systems with heterogeneous bandwidth distributions. For scalability, the coordination of probes is distributed across the hosts. Simulations on empirical and analytic bandwidth distributions--validated with wide-area PlanetLab experiments--show that ThunderDome efficiently yields upload bandwidth estimates that are robust to measurement error.

IP multicast applications such as live lecture broadcasts are being increasingly used in enterprise and campus networks. In many cases, end hosts access these multicast streams using Wi-Fi networks. However, multicast over Wi-Fi suffers from several well-known problems such as low data rate, high losses and unfairness vis-a-vis other contending unicast transmissions. In this paper we present DirCast, a system to solve many of these problems. DirCast requires no changes to the 802.11 MAC protocol or the wireless access points. Software changes are required on clients only if they wish to participate in multicast sessions. The aim of DirCast system is to minimize the airtime consumed by the multicast traffic, while simultaneously improving client experience. To meet these goals, the DirCast converts multicast packets to unicast packets targeted to certain selected clients; other clients receive these packets by listening in promiscuous mode. The target clients are carefully selected to minimize loss rate experienced by the non-targeted clients. If necessary, clients are forced to change the AP they are associated with. In addition, DirCast uses proactive adaptive FEC to further reduce the loss rate and implements a novel virtual multicast interface in order to be compatible with the security needs of the enterprise. We demonstrate the effectiveness of DirCast using extensive experiments in a Wi-Fi prototype implementation and through large-scale simulations.

It is well-known that the overall efficiency of a distributed system can suffer if the participating entities seek to maximize their individual performance. Consequently, mechanisms have been designed that force the participants to behave more cooperatively. Most of these game-theoretic solutions rely on payments between participants. Unfortunately, such payments are often cumbersome to implement in practice, especially in dynamic networks and where transaction costs are high. In this paper, we investigate the potential of mechanisms which work without payments. We consider the problem of throughput maximization in multi-channel environments and shed light onto the throughput increase that can be achieved with and without payments. We introduce and analyze two different concepts: the worst-caseleveragewhere we assume that players end up in the worst rational strategy profile, and the average-caseleveragewhere player select a random non-dominated strategy. Our theoretical insights are complemented by simulations.

Buffers in on-chip networks consume significant energy, occupy chip area, and increase design complexity. In this paper, we make a case for a new approach to designing on-chip interconnection networks that eliminates the need for buffers for routing or flow control. We describe new algorithms for routing without using buffers in router input/output ports. We analyze the advantages and disadvantages of bufferless routing and discuss how router latency can be reduced by taking advantage of the fact that input/output buffers do not exist. Our evaluations show that routing without buffers significantly reduces the energy consumption of the on-chip cache/processor-to-cache network, while providing similar performance to that of existing buffered routing algorithms at low network utilization (i.e., on most real applications). We conclude that bufferless routing can be an attractive and energy-efficient design option for on-chip cache/processor-to-cache networks where network utilization is low.

Network-on-Chips (NoCs) are likely to become a critical shared resource in future many-core processors. The challenge is to develop policies and mechanisms that enable multiple applications to efficiently and fairly share the network, to improve system performance. Existing local packet scheduling policies in the routers fail to fully achieve this goal, because they treat every packet equally, regardless of which application issued the packet.

The proposed demonstration is based on commodity 802.11 wireless cards and a low cost 2.4GHz sniffing device and shows how current WLAN based networks can benefit from spectrum awareness and dynamic access to the assigned band. The demonstrator presents a solution to problems in current wireless networks, like inefficient radio spectrum usage and limited ability to withstand interferences. The presented spectrum-aware radio management framework flexibly negotiates transmission parameters based on spectrum usage and application requirements and opportunistically utilizes available bandwidth. A key feature of this demonstrator is the fact that it breaks the traditional fixed channel bandwidth limitation and enables dynamic bandwidth allocation according to the needs of applications. It continuously monitors the assigned spectrum, tracks application behaviour, and dynamically adapts to the radio environment, such as interference and competition. Furthermore, a cross-media roaming mechanism is provided in the framework to support seamless handovers within and between radio technologies. Our enhancements are transparent to upper layer applications and will automatically benefit any software using network resources. The presented demonstrator uses wireless video streaming in a typical household scenario to illustrate the benefits without changes to the multimedia applications.

We define and study the bandwidth determination problem in ad-hoc P2P environments. Using point-to-point bandwidth probes, the goal is to quickly determine each host's upload and download bandwidth. We present matching upper and lower bounds on the number of probing rounds required by any algorithm. We also devise algorithms which, for realistic bandwidth distributions, beat the lower bounds.

Networking over UHF white spaces is fundamentally different from conventional Wi-Fi along three axes: spatial variation, temporal variation, and fragmentation of the UHF spectrum. Each of these differences gives rise to new challenges for implementing a wireless network in this band. We present the design and implementation of Net7, the first Wi-Fi like system constructed on top of UHF white spaces. Net7 incorporates a new adaptive spectrum assignment algorithm to handle spectrum variation and fragmentation, and proposes a low overhead protocol to handle temporal variation. builds on a simple technique, called SIFT, that reduces the time to detect transmissions in variable channel width systems by analyzing raw signals in the time domain. We provide an extensive evaluation of the system in terms of a prototype implementation and detailed experimental and simulation results.

We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1 - o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.

Traditionally, the channelization structure in IEEE 802.11-based wireless LANs has been fixed: Each access point (AP) is assigned one channel and all channels are equally wide. In contrast, it has recently been shown that even on commodity hardware, the channel-width can be adapted dynamically purely in software. Leveraging this capability, we study the use of dynamic-width channels, where every AP adaptively adjusts not only its center-frequency, but also its channel-width to match its traffic load. This gives raise to a novel optimization problem that differs from previously studied channel assignment problems. We propose efficient spectrum-distribution algorithms and evaluate their effectiveness through analysis and simulations using real-world traces. Our results indicate that by allocating more spectrum to highly-loaded APs, the overall spectrum-utilization can be substantially improved and the notorious load-balancing problem in WLANs can be solved naturally.

In a chip-multiprocessor (CMP) system, the DRAM system is shared among cores. In a shared DRAM system, requests from a thread can not only delay requests from other threads by causing bank/bus/row-buffer conflicts but they can also destroy other threadspsilaDRAM-bank-level parallelism. Requests whose latencies would otherwise have been overlapped could effectively become serialized. As are sult both fairness and system throughput degrade, and some thread scan starve for long time periods. This paper proposes a fundamentally new approach to designing a shared DRAM controller that provides quality of service to threads,while also improving system throughput. Our parallelism-aware batch scheduler (PAR-BS) design is based on two key ideas. First, PARBS processes DRAM requests in batches to provide fairness and to avoid starvation of requests. Second, to optimize system throughput,PAR-BS employs a parallelism-aware DRAM scheduling policy that aims to process requests from a thread in parallel in the DRAM banks, thereby reducing the memory-related stall-time experienced by the thread. PAR-BS seamlessly incorporates support for system-level thread priorities and can provide different service levels, including purely opportunistic service, to threads with different priorities.We evaluate the design trade-offs involved in PAR-BS and compare it to four previously proposed DRAM scheduler designs on 4-, 8-, and16-core systems. Our evaluations show that, averaged over 100 4-core workloads, PAR-BS improves fairness by 1.11X and system through put by 8.3% compared to the best previous scheduling technique, Stall-Time Fair Memory (STFM) scheduling. Based on simple request prioritization rules, PAR-BS is also simpler to implement than STFM.

We study a distributed version of the order scheduling problem that arises when scheduling memory requests in shared DRAM systems of many-core architectures. In this problem, a set of n customer orders needs to be scheduled on multiple facilities. An order can consist of multiple requests, each of which has to be serviced on one designated facility, and an order is completed only when all its requests have been serviced. In the distributed setting, every facility has its own request buffer and must schedule the requests having only limited knowledge about the buffer state at other facilities In this paper, we quantify the trade-off between the amount of communication among different facilities and the quality of the resulting global solution. We show that without communication, the average completion time of all orders can be by a factor Ω(√n) worse than in the optimal schedule. On the other hand, there exists a 2-approximation algorithm if the complete buffer states are exchanged in n communication rounds. We then prove a general upper bound that characterizes the region between these extreme points. Specifically, we devise a distributed scheduling algorithm that, for any k, achieves an approximation ratio of O(k) in n/k communication rounds. Finally, we empirically test the performance of our different algorithms in a many-core environment using SPEC CPU2006 benchmarks as well as Windows desktop application traces.

Without well-provisioned dedicated servers, modern fast-paced action games limit the number of players who can interact simultaneously to 16-32. This is because interacting players must frequently exchange state updates, and high player counts would exceed the bandwidth available to participating machines. In this paper, we describe Donnybrook, a system that enables epic-scale battles without dedicated server resources, even in a fast-paced game with tight latency bounds. It achieves this scalability through two novel components. First, it reduces bandwidth demand by estimating what players are paying attention to, thereby enabling it to reduce the frequency of sending less important state updates. Second, it overcomes resource and interest heterogeneity by disseminating updates via a multicast system designed for the special requirements of games: that they have multiple sources, are latency-sensitive, and have frequent group membership changes. We present user study results using a prototype implementation based on Quake III that show our approach provides a desirable user experience. We also present simulation results that demonstrate Donnybrook's efficacy in enabling battles of up to 900 players.

We study a fundamental yet under-explored facet in wireless communication -- the width of the spectrum over which transmitters spread their signals, or the channel width. Through detailed measurements in controlled and live environments, and using only commodity 802.11 hardware, we first quantify the impact of channel width on throughput, range, and power consumption. Taken together, our findings make a strong case for wireless systems that adapt channel width. Such adaptation brings unique benefits. For instance, when the throughput required is low, moving to a narrower channel increases range and reduces power consumption; in fixed-width systems, these two quantities are always in conflict. We then present a channel width adaptation algorithm, called SampleWidth, for the base case of two communicating nodes. This algorithm is based on a simple search process that builds on top of existing techniques for adapting modulation. Per specified policy, it can maximize throughput or minimize power consumption. Evaluation using a prototype implementation shows that SampleWidth correctly identities the optimal width under a range of scenarios. In our experiments with mobility, it increases throughput by more than 60% compared to the best fixed-width configuration.

In wireless networks mutual interference impairs the quality of received signals and might even prevent the correct reception of messages. It is therefore of paramount importance to dispose of power control and scheduling algorithms, coordinating the transmission of communication requests. We propose a new measure disturbance in order to comprise the intrinsic difficulty of finding a short schedule for a problem instance. Previously known approaches suffer from extremely bad performance in certain network scenarios even if disturbance is low. To overcome this problem, we present a novel scheduling algorithm for which we give analytical worst-case guarantees on its performance. Compared to previously known solutions, the algorithm achieves a speed up, which can be exponential in the size of the network.

The key application scenario of wireless sensor networks is data gathering sensor nodes transmit data, possibly in a multi-hop fashion, to an information sink. The performance of sensor networks is thus characterized by the rate at which information can be aggregated to the sink. In this paper, we derive the first scaling laws describing the achievable rate in worst-case i.e.arbitrarily deployed,sensor networks. We show that in the physical model of wireless communication and for a large number of practically important functions, a sustainable rate of Ω(1 / log2 n) can be achieved in every network even when nodes are positioned in a worst-case manner. In contrast, we show that the best possible rate in the protocol model is Θ(1 /n), which establishes an exponential gap between these two standard models of wireless communication. Furthermore, our worst-case capacity result almost matches the rate of Θ(1 / log n) that can be achieved in randomly deployed networks. The high rate is made possible by employing non-linear power assignment at nodes and by exploiting SINR-effects. Finally,our algorithm also improves the best known bounds on the scheduling complexity in wireless networks.

DRAM memory is a major resource shared among cores in a chip multiprocessor (CMP) system. Memory requests from different threads can interfere with each other. Existing memory access scheduling techniques try to optimize the overall data throughput obtained from the DRAM and thus do not take into account inter-thread interference. Therefore, different threads running together on the same chip can experience extremely different memory system performance: one thread can experience a severe slowdown or starvation while another is unfairly prioritized by the memory scheduler. This paper proposes a new memory access scheduler, called the Stall-Time Fair Memory scheduler (STFM), that provides quality of service to different threads sharing the DRAM memory system. The goal of the proposed scheduler is to "equalize " the DRAM-related slowdown experienced by each thread due to interference from other threads, without hurting overall system performance. As such, STFM takes into account inherent memory characteristics of each thread and does not unfairly penalize threads that use the DRAM system without interfering with other threads. We show that STFM significantly reduces the unfairness in the DRAM system while also improving system throughput (i.e., weighted speedup of threads) on a wide variety of workloads and systems. For example, averaged over 32 different workloads running on an 8-core CMP, the ratio between the highest DRAM-related slowdown and the lowest DRAM-related slowdown reduces from 5.26X to 1.4X, while the average system throughput improves by 7.6%. We qualitatively and quantitatively compare STFM to one new and three previously- proposed memory access scheduling algorithms, including network fair queueing. Our results show that STFM provides the best fairness, system throughput, and scalability.

A number of studies have shown the abundance of unused spectrum in the TV bands. This is in stark contrast to the overcrowding of wireless devices in the ISM bands. A recent trend to alleviate this disparity is the design of Cognitive Radios, which constantly sense the spectrum and opportunistically utilize unused frequencies in the TV bands. A key challenge in the design of such networks is that of Spectrum Allocation, which enables nodes to reserve chunks of the spectrum for certain periods of time. In this paper, we introduce the concept of a time-spectrum block to model spectrum reservation, and use it to present a theoretical formalization of the spectrum allocation problem. We also present a centralized and a distributed protocol for spectrum allocation and show that these protocols are close to optimal in most scenarios. We have implemented the distributed protocol in QualNet and show that our analysis closely matches the simulation results.

We address a critical deployment issue for network systems, namely motivating people to install and run a distributed service. This work is aimed primarily at peer-to-peer systems, in which the decision and effort to install a service falls to individuals rather than to a central planner. This problem is relevant for bootstrapping systems that rely on the network effect, wherein the benefits are not felt until deployment reaches a significant scale, and also for deploying asymmetric systems, wherein the set of contributors is different than the set of beneficiaries. Our solution is the lottery tree (lottree), a mechanism that probabilistically encourages both participation in the system and also solicitation of new participants. We define the lottree mechanism and normally state seven properties that encourage contribution, solicitation, and fair play. We then present the Pachira lottree scheme, which satisfies five of these seven properties, and we prove this to be a maximal satisfiable subset. Using simulation, we determine optimal parameters for the Pachira lottree scheme, and we determine how to configure a lottree system for achieving various deployment scales based on expected installation effort. We also present extensive sensitivity analyses, which bolster the generality of our conclusions.

Motivated by an application in distributed gaming, we define and study the latency-constrained total upload maximization problem. In this problem, a peer-to-peer overlay network is modeled as a complete graph and each node vi has an upload bandwidth capacity ci and a set of receivers R(i). Each sender-receiver pair (vi,vj), where vj ∈ R(i),isarequest that should be satisfied, i.e., vi should send a data packet to each vj ∈ R(i). The goal is to find a set of at most n multicast-trees Ti of depth at most 2, such that each node can be part of multiple trees, all capacity constraints are met, and the number of satisfied requests is maximized. In this paper, we prove that the problem is NP-complete, and we present an algorithm with approximation ratio 1 − 2 / √ cmin, wherecmin is the minimum upload capacity. Finally, we also study the impact of network coding on the quality and approximability of the solution. Categories and Subject Descriptors

We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various distributed network applications. Given a network graph G = (V,E), and a capacity cap(v) ∈ N for each node v ∈ V , the CapMDS problem asks for a subset S ⊆ V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v ∈ S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter ε > 0, capacities can be violated by a factor of 1 + ε, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log3n + log(n)/ε), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local.

In this paper, we study distributed approximation algorithms for fault-tolerant clustering in wireless ad hoc and sensor networks. A k-fold dominating set of a graph G = (V,E) is a subset S of V such that every node v \in V \ S has at least k neighbors in S. We study the problem in two network models. In general graphs, for arbitrary parameter t, we propose a distributed algorithm that runs in time O(t^2) and achieves an approximation ratio of O(t\delta^2/t log\delta), where n and \delta denote the number of nodes in the network and the maximal degree, respectively. When the network is modeled as a unit disk graph, we give a probabilistic algorithm that runs in time O(log log n) and achieves an O(1) approximation in expectation. Both algorithms require only small messages of size O(log n) bits.

Abstract — The inherent trade-off between energy-efficiency and rapidity of event dissemination is characteristic for wireless sensor networks. Scarcity of energy renders it necessary for nodes to spend a large portion of their lifetime in an energyefficient sleep mode during which they do neither receive nor send messages. On the other hand, the longer nodes stay in sleep mode, the slower will be the reaction time for disseminating an external event. The trade-off is prominently exhibited during the deployment phase of sensor networks, if some nodes are deployed earlier than others. In this paper, we study this fundamental trade-off by giving a formal model that enables us to compare the performance of different protocols and algorithms. Based on this model, we propose, analyze, and simulate two novel algorithms which significantly outperform existing solutions. I.

We define and study the scheduling complexity in wireless networks, which expresses the theoretically achievable efficiency of MAC layer protocols. Given a set of communication requests in arbitrary networks, the scheduling complexity describes the amount of time required to successfully schedule all requests. The most basic and important network structure in wireless networks being connectivity, we study the scheduling complexity of connectivity, i.e., the minimal amount of time required until a connected structure can be scheduled. In this paper, we prove that the scheduling complexity of connectivity grows only polylogarithmically in the number of nodes. Specifically, we present a novel scheduling algorithm that successfully schedules a strongly connected set of links in time O(log 4 n) even in arbitrary worst-case networks. On the other hand, we prove that standard MAC layer or scheduling protocols can perform much worse. Particularly, any protocol that either employs uniform or linear (a node’s transmit power is proportional to the minimum power required to reach its intended receiver) power assignment has a Ω(n) scheduling complexity in the worst case, even for simple communication requests. In contrast, our polylogarithmic scheduling algorithm allows many concurrent transmission by using an explicitly formulated non-linear power assignment scheme. Our results show that even in large-scale worst-case networks, there is no theoretical scalability problem when it comes to scheduling transmission requests, thus giving an interesting complement to the more pessimistic bounds for the capacity in wireless networks. All results are based on the physical model of communication, which takes into account that the signal-tonoise plus interference ratio (SINR) at a receiver must be above a certain threshold if the transmission is to be received correctly.

To date, topology control in wireless ad hoc and sensor networks--the study of how to compute from the given communication network a subgraph with certain beneficial properties .has been considered as a static problem only; the time required to actually schedule the links of a computed topology without message collision was generally ignored. In this paper we analyze topology control in the context of the physical Signal-to-Interference-plus-Noise-Ratio (SINR) model, focusing on the question of how and how fast the links of a resulting topology can actually be realized over time.For this purpose, we define and study a generalized version of the SINR model and obtain theoretical upper bounds on the scheduling complexity of arbitrary topologies in wireless networks. Specifically, we prove that even in worst-case networks, if the signals are transmitted with correctly assigned transmission power levels, the number of time slots required to successfully schedule all links of an arbitrary topology is proportional to the squared logarithm of the number of network nodes times a previously defined static interference measure Interestingly, although originally considered without explicit accounting for signal collision in the SINR model, this static interference measure plays an important role in the analysis of link scheduling with physical link interference. Our result thus bridges the gap between static graph-based interference models and the physical SINR model. Based on these results, we also show that when it comes to scheduling, requiring the communication links to be symmetric may imply significantly higher costs as opposed to topologies allowing unidirectional links.

Over the last years, game theory has provided great insights into the behavior of distributed systems by modeling the players as utility-maximizing agents. In particular, it has been shown that selfishness causes many systems to perform in a globally suboptimal fashion. Such systems are said to have a large Price of Anarchy. In this paper, we extend this active field of research by allowing some players to be malicious or Byzantine rather than selfish. We ask: What is the impact of Byzantine players on the system's efficiency compared to purely selfish environments or compared to the social optimum? In particular, we introduce the Price of Malice which captures this efficiency degradation. As an example, we analyze the Price of Malice of a game which models the containment of the spread of viruses. In this game, each node can choose whether or not to install anti-virus software. Then, a virus starts from a random node and iteratively infects all neighboring nodes which are not inoculated. We establish various results about this game. For instance, we quantify how much the presence of Byzantine players can deteriorate or---in case of highly risk-averse selfish players---improve the social welfare of the distributed system.

Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. By giving tight bounds on the price of anarchy, we show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. Finally, we establish the complexity of Nash equilibria in our game theoretic model of P2P networks. Specifically, we prove that it is NP-hard to decide whether our game has a Nash equilibrium and can stabilize.

Many large-scale networks such as ad hoc and sensor networks, peer-to-peer networks, or the Internet have the property that the number of independent nodes does not grow arbitrarily when looking at neighborhoods of increasing size. Due to this bounded "volume growth," one could expect that distributed algorithms are able to solve many problems more efficiently than on general graphs. The goal of this paper is to help understanding the distributed complexity of problems on "bounded growth" graphs. We show that on the widely used unit disk graph, covering and packing linear programs can be approximated by constant factors in constant time. For a more general network model which is based on the assumption that nodes are in a metric space of constant doubling dimension, we show that in O(log*!n) rounds it is possible to construct a (O(1), O(1))-network decomposition. This results in asymptotically optimal O(log*!n) time algorithms for many important problems.

In this paper, we initiate the study of the approximability of the facility location problem in a distributed setting. In particular, we explore a trade-off between the amount of communication and the resulting approximation ratio. We give a distributed algorithm that, for every constant k, achieves an O(√k(mρ)1/√klog(m+n)) approximation in O(k) communication rounds where message size is bounded to O(log n) bits. The number of facilities and clients are $m$ and n, respectively, and ρ is a coefficient that depends on the cost values of the instance. Our technique is based on a distributed primal-dual approach for approximating a linear program, that does not form a covering or packing program.

We study the distributed complexity of computing a maximal independent set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism available. Specifically, we propose a novel randomized algorithm that computes a MIS in time O(log2! n) with high probability, where n is the number of nodes in the network. This significantly improving on the best previously known solutions. A lower bound of Ω(log2!n / log log n) given in [11] implies that our algorithm's running time is close to optimal. Our result shows that the harsh radio network model imposes merely an additional O(log n) factor compared to Luby's MIS algorithm in the message passing model. This has important implications in the context of ad hoc and sensor networks whose characteristics are closely captured by the radio network model.

During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any reasonable communication can take place, nodes must come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works under the unstructured radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous wake-up, no collision-detection, and scarce knowledge about the network topology. Our algorithm produces a correct coloring with O(Δ) colors in time O(Δ log n) with high probability in a unit disk graph, where n and Δ are the number of nodes in the network and the maximum degree, respectively. Furthermore, the number of locally used colors depends only on the local node density.

When being deployed, ad-hoc and sensor networks are unstructured and lack an efficient and reliable communication scheme. Hence, the organization of a MAC layer is the primary goal during and immediately after the deployment of such networks. Computing a good initial clustering facilitates this task and is therefore a vital part of the initialization process. A clustering based on a maximal independent set provides several highly desirable properties. Besides yielding a dominating set of good quality, such a clustering avoids interference between clusterheads, thus allowing efficient communication. We propose a novel algorithm that works under a model capturing the characteristics of the initialization phase of unstructured radio networks, i.e., asynchronous wake-up, scarce knowledge about the topology of the network graph, no collision detection, and the hidden terminal problem. We show that even under these hard conditions, the algorithm computes a maximal independent set in polylogarithmic time.

A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi-hop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed efficiently. Our algorithm efficiently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings.

We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Ω(nc/k2/k) and Ω(∆1/k /k) for some constant c, where n and ∆ denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Ω ( √ log n / log log n) and Ω(log ∆ / log log ∆). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.

No abstract available.