A Critique of the CAP Theorem

The CAP Theorem is a frequently cited impossibility result in distributed systems, especially among NoSQL distributed databases. In this paper we survey some of the confusion about the meaning of CAP, including inconsistencies and ambiguities in its definitions, and we highlight some problems in its formalization and proofs. CAP is often interpreted as proof that eventually consistent databases have better availability properties than strongly consistent databases; although there is some truth in this, we show that more careful reasoning is required. These problems cast doubt on the utility of CAP as a tool for reasoning about trade-offs in practical systems. As alternative to CAP, we propose a ‘delay-sensitivity’ framework, which analyzes the sensitivity of operation latency to network delay, and which may help practitioners reason about the trade-offs between consistency guarantees and tolerance of network faults.

A Reliable and Cost-Efficient Auto-Scaling System for Web Applications Using Heterogeneous Spot Instances

Cloud providers sell their idle capacity on markets through an auction-like mechanism to increase their return on investment. The instances sold in this way are called spot instances. In spite that spot instances are usually 90\% cheaper than on-demand instances, they can be terminated by provider when their bidding prices are lower than market prices. Thus, they are largely used to provision fault-tolerant applications only. In this paper, we explore how to utilize spot instances to provision web applications, which are usually considered availability-critical. The idea is to take advantage of differences in price among various types of spot instances to reach both high availability and significant cost saving. We first propose a fault-tolerant model for web applications provisioned by spot instances. Based on that, we devise novel auto-scaling polices for hourly billed cloud markets. We implemented the proposed model and policies both on a simulation testbed for repeatable validation and Amazon EC2. The experiments on the simulation testbed and the real platform against the benchmarks show that the proposed approach can greatly reduce resource cost and still achieve satisfactory Quality of Service (QoS) in terms of response time and availability.

A Simulated Annealing Approach to Bayesian Inference

A generic algorithm for the extraction of probabilistic (Bayesian) information about model parameters from data is presented. The algorithm propagates an ensemble of particles in the product space of model parameters and outputs. Each particle update consists of a random jump in parameter space followed by a simulation of a model output and a Metropolis acceptance/rejection step based on a comparison of the simulated output to the data. The distance of a particle to the data is interpreted as an energy and the algorithm is reducing the associated temperature of the ensemble such that entropy production is minimized. If this simulated annealing is not too fast compared to the mixing speed in parameter space, the parameter marginal of the ensemble approaches the Bayesian posterior distribution. Annealing is adaptive and depends on certain extensive thermodynamic quantities that can easily be measured throughout run-time. In the general case, we propose annealing with a constant entropy production rate, which is optimal as long as annealing is not too fast. For the practically relevant special case of no prior knowledge, we derive an optimal fast annealing schedule with a non-constant entropy production rate. The algorithm does not require the calculation of the density of the model likelihood, which makes it interesting for Bayesian parameter inference with stochastic models, whose likelihood functions are typically very high dimensional integrals.

Case-Deletion Diagnostics for Quantile Regression Using the Asymmetric Laplace Distribution

To make inferences about the shape of a population distribution, the widely popular mean regression model, for example, is inadequate if the distribution is not approximately Gaussian (or symmetric). Compared to conventional mean regression (MR), quantile regression (QR) can characterize the entire conditional distribution of the outcome variable, and is more robust to outliers and misspecification of the error distribution. We present a likelihood-based approach to the estimation of the regression quantiles based on the asymmetric Laplace distribution (ALD), which has a hierarchical representation that facilitates the implementation of the EM algorithm for the maximum-likelihood estimation. We develop a case-deletion diagnostic analysis for QR models based on the conditional expectation of the complete-data log-likelihood function related to the EM algorithm. The techniques are illustrated with both simulated and real data sets, showing that our approach out-performed other common classic estimators. The proposed algorithm and methods are implemented in the R package ALDqr().

Efficient Task Collaboration with Execution Uncertainty

We study a general task allocation problem, involving multiple agents that collaboratively accomplish tasks and where agents may fail to successfully complete the tasks assigned to them (known as execution uncertainty). The goal is to choose an allocation that maximises social welfare while taking their execution uncertainty into account. We show that this can be achieved by using the post-execution verification (PEV)-based mechanism if and only if agents’ valuations satisfy a multilinearity condition. We then consider a more complex setting where an agent’s execution uncertainty is not completely predictable by the agent alone but aggregated from all agents’ private opinions (known as trust). We show that PEV-based mechanism with trust is still truthfully implementable if and only if the trust aggregation is multilinear.

Fast Gaussian Process Regression for Big Data

Gaussian Processes are widely used for regression tasks. A known limitation in the application of Gaussian Processes to regression tasks is that the computation of the solution requires performing a matrix inversion. The solution also requires the storage of a large matrix in memory. These factors restrict the application of Gaussian Process regression to small and moderate size data sets. We present an algorithm based on empirically determined subset selection that works well on both real world and synthetic datasets. On the synthetic and real world datasets used in this study, the algorithm demonstrated sub-linear time and space complexity. The correctness proof for the algorithm is also presented.

Optimal Subsampling Approaches for Large Sample Linear Regression

A significant hurdle for analyzing large sample data is the lack of effective statistical computing and inference methods. An emerging powerful approach for analyzing large sample data is subsampling, by which one takes a random subsample from the original full sample and uses it as a surrogate for subsequent computation and estimation. In this paper, we study subsampling methods under two scenarios: approximating the full sample ordinary least-square (OLS) estimator and estimating the coefficients in linear regression. We present two algorithms, weighted estimation algorithm and unweighted estimation algorithm, and analyze asymptotic behaviors of their resulting subsample estimators under general conditions. For the weighted estimation algorithm, we propose a criterion for selecting the optimal sampling probability by making use of the asymptotic results. On the basis of the criterion, we provide two novel subsampling methods, the optimal subsampling and the predictor- length subsampling methods. The predictor-length subsampling method is based on the L2 norm of predictors rather than leverage scores. Its computational cost is scalable. For unweighted estimation algorithm, we show that its resulting subsample estimator is not consistent to the full sample OLS estimator. However, it has better performance than the weighted estimation algorithm for estimating the coefficients. Simulation studies and a real data example are used to demonstrate the effectiveness of our proposed subsampling methods.

(Blue) Taxi Destination and Trip Time Prediction from Partial Trajectories

A Paley-like graph in characteristic two

An application of multivariate total positivity to peacocks

An irreversible local Markov chain that preserves the six vertex model on a torus

Array Layouts for Comparison-Based Searching

Bayesian Parameter Inference for 1D Nonlinear Stochastic Differential Equation Models

Bayesian structured additive distributional regression with an application to regional income inequality in Germany

Bipodal structure in oversaturated random graphs

Cayley numbers with arbitrarily many distinct prime factors

Computing the Rectilinear Center of Uncertain Points in the Plane

Detecting Community Structures in Hi-C Genomic Data

DeXpression: Deep Convolutional Neural Network for Expression Recognition

Disjoint difference families and their applications

Estimating operator norms using covering nets

Exact simultaneous recovery of locations and structure from known orientations and corrupted point correspondences

Extraction of evidence tables from abstracts of randomized clinical trials using a maximum entropy classifier and global constraints

Face numbers of manifolds with boundary

Fast Sequence Component Analysis for Attack Detection in Synchrophasor Networks

Finite-size critical scaling in Ising spin glasses in the mean-field regime

Fluctuations in the Homogenization of Semilinear Equations with Random Potentials

Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis

Investigation of asymmetry in E. coli growth rate

Iterated scaling limits for aggregation of randomized INAR(1) processes with idiosyncratic Poisson innovations

Learning Preferences from Assortment Choices in a Heterogeneous Population

Lévy Processes and Lévy White Noise as Tempered Distributions

Logarithmic, Coulomb and Riesz energy of point processes

MRL order, log-concavity and an application to peacocks

Multivariate Subexponential Distributions and Their Applications

Network analysis of named entity interactions in written texts

Noncommutative martingale inequalities associated with convex functions

Normalized incomplete beta function: log-concavity in parameters and other properties

Notions of maximality for integral lattice-free polyhedra: the case of dimension three

On some conjectures concerning critical independent sets of a graph

Online compressed sensing

Partitioning polyominoes into polyominoes of at most 8 vertices

Performance Analysis and Prediction in Educational Data Mining: A Research Travelogue

Periods and borders of random words

Quasi-homomorphisms of cluster algebras

Regression based principal component analysis for sparse functional data with applications to screening growth paths

Response to a local quench of a system near many body localization transition

Selection of the Regularization Parameter in Graphical Models using a Priori Knowledge of Network Structure

Self-organization of network dynamics into local quantized states

Singularity analysis for heavy-tailed random variables

Some Theorems for Feed Forward Neural Networks

Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences

Taming the ReLU with Parallel Dither in a Deep Neural Network

The Erdos discrepancy problem

The zero-inflated cure rate regression model: Applications to fraud detection in bank loan portfolios

Waiter-Client and Client-Waiter Hamiltonicity games on random graphs

Words with many palindrome pair factors