The concept of a blockchain was invented by Satoshi Nakamoto to maintain a distributed ledger. In addition to its security, important performance measures of a blockchain protocol are its transaction throughput and confirmation latency. In a decentralized setting, these measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propagation delay. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in the bandwidth-delay product CD; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing Nakamoto's blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.

Computing the medoid of a large number of points in high-dimensional space is an increasingly common operation in many data science problems. We present an algorithm Med-dit to compute the medoid with high probability, which uses $O(n\log n)$ distance evaluations. Med-dit is based on a connection with the Multi-Armed Bandit problem. We evaluate the performance of Med-dit empirically on the Netflix-prize and single-cell RNA-seq datasets, containing hundreds of thousands of points living in tens of thousands of dimensions, and observe a $5$-$10$x improvement in performance over the current state of the art. We have released the code of Med-dit and our empirical results at https://github.com/bagavi/Meddit.

We address a classical problem concerning energy efficiency in sensor networks. In particular, we consider the problem of maximizing the lifetime of coverage of targets in a wireless sensor network with battery-limited sensors. We first show that the problem cannot be approximated within a factor less than lnn by any polynomial time algorithm, where n is the number of targets. This provides closure to the long-standing open problem of showing optimality of previously known lnn approximation algorithms. We also derive a new ln n approximation to the problem by showing the lnn approximation to the related maximum disjoint set cover problem. We show that this approach has many advantages over algorithms in the literature, including a simple and optimal extension that solves the problem with multiple coverage constraints. For the 1-D network topology, where sensors can monitor contiguous line segments of possibly different lengths, we show that the optimal coverage lifetime can be found in polynomial time. Finally, for the 2-D topology in which coverage regions are unit squares, we combine the existing results to derive a 1 + € approximation algorithm for the problem. Extensive simulation experiments validate our theoretical results, showing that our algorithms not only have optimal worst case guarantees but also match the performance of the existing algorithms on special network topologies. In addition, our algorithms sometimes run orders of magnitude faster than the existing state of the art.

Given a universe U of n elements and a collection of subsets S of U, the maximum disjoint set cover problem (DSCP) is to partition S into as many set covers as possible, where a set cover is defined as a collection of subsets whose union is U. We consider the online DSCP, in which the subsets arrive one by one (possibly in an order chosen by an adversary), and must be irrevocably assigned to some partition on arrival with the objective of minimizing the competitive ratio. The competitive ratio of an online DSCP algorithm A is defined as the maximum ratio of the number of disjoint set covers obtained by the optimal offline algorithm to the number of disjoint set covers obtained by A across all inputs. We propose an online algorithm for solving the DSCP with competitive ratio ln n. We then show a lower bound of Ω(√ln n) on the competitive ratio for any online DSCP algorithm. The online disjoint set cover problem has wide ranging applications in practice, including the online crowd-sourcing problem, the online coverage lifetime maximization problem in WSNs, and in online resource allocation problems.