Matrix completion (MC) is fundamental for predicting missing data with a wide range of applications in personalized healthcare, e-commerce, recommendation systems, and social network analysis. Traditional MC approaches typically assume centralized data storage, which raises challenges in terms of computational efficiency, scalability, and user privacy. In this article, we address the problem of federated MC, focusing on scenarios where user-specific data is distributed across multiple clients, and privacy constraints are uncompromising. Federated learning (FL) provides a promising framework to address these challenges by enabling collaborative learning across distributed datasets without sharing raw data. We propose FedMC-ADMM for solving federated MC problems, a novel algorithmic framework that combines the alternating direction method of multipliers (ADMM) with a randomized block-coordinate strategy and alternating proximal gradient steps. Unlike existing federated approaches, FedMC-ADMM effectively handles multiblock nonconvex and nonsmooth optimization problems, allowing efficient computation while preserving user privacy. We analyze the theoretical properties of our algorithm, demonstrating subsequential convergence and establishing a convergence rate of $\mathcal {O}(K^{-1/2})$ , leading to a communication complexity of $\mathcal {O}(\epsilon ^{-2})$ for reaching an $\epsilon $ -stationary point. This work is the first to establish these theoretical guarantees for federated MC in the presence of multiblock variables. To validate our approach, we conduct extensive experiments on real-world datasets, including MovieLens 1M, 10M, and Netflix. The results demonstrate that FedMC-ADMM outperforms existing methods in terms of convergence speed and testing accuracy.

One of the key challenges for data analytics deployment is configuration tuning. The existing approaches for configuration tuning are expensive and overlook the dynamic characteristics of the analytics environment (i.e. frequent changes in workload due to receiving evolving input sizes or change in the underlying cluster environment). Such workload/environment changes can cause significant performance degradation, with retuning the configuration to accommodate those changes can yield up to 85% potential execution time saving. We propose SimTune, an approach that accommodates such changes through efficient configuration tuning. SimTune combines workload characterization and Multitask Bayesian optimization to identify similarity across workloads and accelerate finding near-optimal configurations. Our experimental results show that SimTune reduces the search time for finding close-to-optimal configurations by 56-73% (at the median) when compared to existing state-of-the-art techniques. This means that the amortization of the tuning cost happens significantly faster, enabling practical tuning in the rapidly changing environment of distributed analytics.

This experimental study presents a number of issues that pose a challenge for practical configuration tuning and its deployment in data analytics frameworks. These issues include: 1) the assumption of a static workload or environment, ignoring the dynamic characteristics of the analytics environment (e.g., increase in input data size, changes in allocation of resources). 2) the amortization of tuning costs and how this influences what workloads can be tuned in practice in a cost-effective manner. 3) the need for a comprehensive incremental tuning solution for a diverse set of workloads. We adapt different ML techniques in order to obtain efficient incremental tuning in our problem domain, and propose Tuneful, a configuration tuning framework. We show how it is designed to overcome the above issues and illustrate its applicability by running a wide array of experiments in cloud environments provided by two different service providers.

The execution of distributed data processing workloads (such as those running on top of Hadoop or Spark) in cloud environments presents a unique opportunity to explore multiple trade-offs between elasticity (and types of resources being allocated), overall runtime and total costs. However, beyond high-level constraints and objectives, it's not the end-users who should be mainly concerned with those optimizations, but the cloud providers. They have both the vantage point to collect actionable information, economies of scale and position to adjust parameters when dynamic conditions change, in order to fulfil SLOs that go beyond classic measures of latency and throughput. This is at odds with the existing approach of making software (including the interfaces to the cloud and the processing frameworks) as configurable as possible. We propose that rather than configurability, self-tunability (or the illusion of it as far as the end-user is concerned) is a better long-term goal.

Automated build systems are routinely used by software engineers to minimize the number of objects that need to be recompiled after incremental changes to the source files of a project. In order to achieve efficient and correct builds, developers must provide the build tools with dependency information between the files and modules of a project, usually expressed in a macro language specific to each build tool. In order to guarantee correctness, the authors of these tools are responsible for enumerating all the files whose contents an output depends on. Unfortunately, this is a tedious process and not all dependencies are captured in practice, which leads to incorrect builds. We automatically uncover such missing dependencies through a novel method that we call build fuzzing. The correctness of build definitions is verified by modifying files in a project, triggering incremental builds and comparing the set of changed files to the set of expected changes. These sets are determined using a dependency graph inferred by tracing the system calls executed during a clean build. We evaluate our method by exhaustively testing build rules of open-source projects, uncovering issues leading to race conditions and faulty builds in 31 of them. We provide a discussion of the bugs we detect, identifying anti-patterns in the use of the macro languages. We fix some of the issues in projects where the features of build systems allow a clean solution.

Programmers spend a substantial amount of time manually repairing code that does not compile. We observe that the repairs for any particular error class typically follow a pattern and are highly mechanical. We propose a novel approach that automatically learns these patterns with a deep neural network and suggests program repairs for the most costly classes of build-time compilation failures. We describe how we collect all build errors and the human-authored, in-progress code changes that cause those failing builds to transition to successful builds at Google. We generate an AST diff from the textual code changes and transform it into a domain-specific language called Delta that encodes the change that must be made to make the code compile. We then feed the compiler diagnostic information (as source) and the Delta changes that resolved the diagnostic (as target) into a Neural Machine Translation network for training. For the two most prevalent and costly classes of Java compilation errors, namely missing symbols and mismatched method signatures, our system called DeepDelta, generates the correct repair changes for 19,314 out of 38,788 (50%) of unseen compilation errors. The correct changes are in the top three suggested fixes 86% of the time on average.

Clauses and subgoals in a Datalog program can be given in any order without affecting program meaning. However, practical applications of the language require the use of built-in or external predicates with particular dataflow requirements. These can be expressed as input or output "modes" on arguments. We describe a static analysis of moding for Datalog which calculates how to transform an ill-moded program into a well-moded program by reordering clause subgoals to satisfy dataflow requirements. We describe an incremental algorithm which efficiently finds a reordering if it exists. This frees the programmer to focus on the declarative specification of a program rather than implementation details of external predicates. We prove that our computed reorderings yield well-moded programs (soundness) and if a program can be made well-moded, then we compute a reordering to do so (completeness).

Arrays computations are at the core of numerical modelling and computational science applications. However, low-level manipulation of array indices is a source of program error. Many practitioners are aware of the need to ensure program correctness, yet very few of the techniques from the programming research community are applied by scientists. We aim to change that by providing targetted lightweight verification techniques for scientific code. We focus on the all too common mistake of array offset errors as a generalisation of off-by-one errors. Firstly, we report on a code analysis study on eleven real-world computational science code base, identifying common idioms of array usage and their spatial properties. This provides much needed data on array programming idioms common in scientific code. From this data, we designed a lightweight declarative specification language capturing the majority of array access patterns via a small set of combinators. We detail a semantic model, and the design and implementation of a verification tool for our specification language, which both checks and infers specifications. We evaluate our tool on our corpus of scientific code. Using the inference mode, we found roughly 87,000 targets for specification across roughly 1.1 million lines of code, showing that the vast majority of array computations read from arrays in a pattern with a simple, regular, static shape. We also studied the commit logs of one of our corpus packages, finding past bug fixes for which our specification system distinguishes the change and thus could have been applied to detect such bugs.

Identifier names are often used by developers to convey additional information about the meaning of a program over and above the semantics of the programming language itself. We present an algorithm that uses this information to detect argument selection defects, in which the programmer has chosen the wrong argument to a method call in Java programs. We evaluate our algorithm at Google on 200 million lines of internal code and 10 million lines of predominantly open-source external code and find defects even in large, mature projects such as OpenJDK, ASM, and the MySQL JDBC. The precision and recall of the algorithm vary depending on a sensitivity threshold. Higher thresholds increase precision, giving a true positive rate of 85%, reporting 459 true positives and 78 false positives. Lower thresholds increase recall but lower the true positive rate, reporting 2,060 true positives and 1,207 false positives. We show that this is an order of magnitude improvement on previous approaches. By analyzing the defects found, we are able to quantify best practice advice for API design and show that the probability of an argument selection defect increases markedly when methods have more than five arguments.

Online educational tools often generate learning data, and sharing such data between tutors and students can often improve learning outcomes. Unfortunately the process of sharing learning data today is not always transparent to students. Our aim is to improve the transparency and user control aspects of sharing data whilst maintaining the educational utility of data sharing between tutors and students. To do so, we start by surveying the possible methods of sharing data, and we use this to design a token-based scheme for facilitating data sharing. We implemented our scheme and observed it in use by 7,798 students over the course of one year. We find that our proposed scheme provides a good balance between transparency, user control, educational utility and scalability.

We investigate the use of hints as a form of scaffolding for 4,652 eligible users on a large-scale online learning environment called Isaac, which allows users to answer physics questions with up to five hints. We investigate user behaviour when using hints, users' engagement with fading (the process of gradually becoming less reliant on the hints provided), and hint strategies including Decomposition, Correction, Verification, or Comparison. Finally, we present recommendations for the design and development of online teaching tools that provide open access to hints, including a mechanism that may improve the speed at which users begin fading.

There is growing demand for researchers to share datasets in order to allow others to reproduce results or investigate new questions. The most common option is to simply deposit the data online in its entirety. However, this mechanism of distribution becomes impractical as the size of the dataset increases or if the dataset is frequently changing as new data is collected. In this paper we describe Picky, a new Merkle tree based system for sharing large datasets which allows users to download selected portions and to receive incremental updates. We demonstrate the viability of our approach by quantifying its benefit when applied to a number of large datasets used in the networking and measurement community.

We describe a new tool, Equality, for equation entry using free-form layout of components drawn from a palette of symbols. Our approach is designed to enable learners to easily manipulate the structure of their equations, to be functional in both desktop and mobile environments, and to minimize the amount of learning required to use the tool. We present the results of a study comparing a prototype of our approach with Microsoft Equation Editor using a desktop machine. The initial results are promising with participants reporting that the mechanism is easy to learn and an easy way to manipulate their equations. We report the results of the study and the views of the participants and identify how these will inform the future development of Equality.

The provision of location-based services on consumer devices has moved from on-demand navigation capabilities to always-on ubiquitous location-aware tools such as weather updates, travel information, location-based reminders and many more. Background localisation is generally provided by Wi-Fi fingerprinting, since GPS does not provide service in indoor environments where we spend 80% of our time. However the power consumption of a Wi-Fi scan is proportional to the number of channels scanned, and so naive full-channel scans are inefficient. Here we describe and validate SwiftScan, an intelligent, self-training Wi-Fi fingerprinting scheme that reduces the energy consumption of periodic background Wi-Fi scanning for localisation. SwiftScan is tested with data from more than a thousand Android users over a six month time period and we show that energy savings of over 90% are possible, and that the majority of users benefit from more than a 70% reduction in the energy consumption associated with a Wi-Fi scan for localisation purposes.

Device Analyzer is an Android app available from the Google Play store. It is designed to collect a large range of data from the handset and, with agreement from our contributors, share it with researchers around the world. Researchers can access the data collected, and can also use the platform to support their own user studies. In this paper we provide an overview of the privacy-enhancing techniques used in Device Analzyer, including transparency, consent, purpose, access, withdrawal, and accountability. We also demonstrate the utility of our platform by assessing the security of the Android ecosystem to privilege escalation attacks and determine that 88% of Android devices are, on average, vulnerable to one or more of these type of attacks.

Despite the tremendous market penetration of smartphones, their utility has been and will remain severely limited by their battery life. A major source of smartphone battery drain is accessing the Internet over cellular or WiFi connection when running various apps and services. Despite much anecdotal evidence of smartphone users experiencing quicker battery drain in poor signal strength, there has been limited understanding of how often smartphone users experience poor signal strength and the quantitative impact of poor signal strength on the phone battery drain. The answers to such questions are essential for diagnosing and improving cellular network services and smartphone battery life and help to build more accurate online power models for smartphones, which are building blocks for energy profiling and optimization of smartphone apps. In this paper, we conduct the first measurement and modeling study of the impact of wireless signal strength on smartphone energy consumption. Our study makes four contributions. First, through analyzing traces collected on 3785 smartphones for at least one month, we show that poor signal strength of both 3G and WiFi is routinely experienced by smartphone users, both spatially and temporally. Second, we quantify the extra energy consumption on data transfer induced by poor wireless signal strength. Third, we develop a new power model for WiFi and 3G that incorporates the signal strength factor and significantly improves the modeling accuracy over the previous state of the art. Finally, we perform what-if analysis to quantify the potential energy savings from opportunistically delaying network traffic by exploring the dynamics of signal strength experienced by users.

Live migration of virtual machines is now commonplace but the issue of synchronising storage remains an obstacle to wide-area migration between datacentres. We discuss the range of possible designs for synchronising disk images and argue that we have to be adaptive at the sector level to efficiently transfer disk-state to the destination. We show, using a number of production workloads, that delaying the transmission of "hot"sectors can achieve considerable bandwidth reduction over a naive eager strategy. We introduce the Activity Based Sector Synchronisation (ABSS) algorithm and show by trace-driven simulations that ABSS is able to deliver a useful trade-off with a data transmission overhead between 0.3% and 2.4% of a gigabit link whilst incurring in the majority of cases a migration latency of less than 1.1 s.

This paper quantifies the energy consumption in six 10 Gbps and four 1 Gbps interconnects at a fine-grained level, introducing two metrics for calculating the energy efficiency of a network interface from the perspective of network throughput and host CPU usage. It further compares the energy efficiency of multiport 1 Gbps to 10 Gbps interconnects.

With the ability to move virtual machines between physical hosts, live migration is a core feature of virtualisation. However for migration to be useful, deployable feature on a large (datacentre) scale, we need to predict migration times with accuracy. In this paper, we characterise the parameters affecting live migration with particular emphasis on the Xen virtualisation platform. We discuss the relationships between the important parameters that affect migration and highlight how migration performance can vary considerably depending on the workload. We further provide 2 simulation models that are able to predict migration times to within 90% accuracy for both synthetic and real-world benchmarks.

Modern mobile phones are an appealing platform for pervasive computing applications. However, the complexity of these devices makes it difficult for developers to understand the power consumption of their applications. Our measurement framework is the first we have seen which can produce fine-grained, annotated traces of a phone's power consumption and is designed to develop an understanding of how particular aspects of an application drive energy use. We are using our framework to analyse the power consumption of Android-based G1 and Magic handsets and show that particular choices of message size and send buffer can alter the energy required to send data by an order of magnitude in certain cases.

This paper presents Cantag, an open source software toolkit for building marker-based vision (MBV) systems that can identify and accurately locate printed markers in three dimensions. The extensibility of the system makes it ideal for dynamic location and poses determination in pervasive computing systems. Unlike prior MBV systems, Cantag supports multiple fiducial shapes, payload types, data sizes and image processing algorithms in one framework. It allows the application writer to generate a custom tag design and associated optimised executable for any given application. The system includes a test harness which can be used to quantify, compare and contrast the performance of different designs. This paper explores the design space of tags within the Cantag system, and describes the design parameters and performance characteristics which an application writer can use to select the best tag system for any given scenario. It presents quantitative analysis of different markers and processing algorithms, which are compared fairly for the first time