^May June – 2013 ^July

NoSQL databases have been initially designed to provide extreme scalability and availability for Internet applications, often at the expense of data consistency. The recent generation of Web-scale databases fills this gap, by offering transaction support. However, transaction processing implies a performance overhead that is redundant for many applications that do not require strong consistency. The solutions offered by state-of-the-art technologies, either static separation of the data accessed by transaction-enabled and native applications, or transforming all native operations into transactions in the latter, are both inadequate. We present a novel scalable transaction processing system, Mediator, that accommodates both transactional and native operations in the same database without compromising data safety. Our work introduces a lightweight synchronization protocol that enables conflict resolution between transactions and native operations that share the same data. We evaluate Mediator’s implementation on top of the HBase NoSQL database on a large-scale distributed testbed. Our results show that despite a slight overhead to the transactional traffic, Mediator substantially outperforms the best-in-class traditional system on a vast majority of mixed workloads – in particular, on all workloads in which the fraction of native operations exceeds 50%.

I will give a tour through a sparse sample of the information theory literature - both classical and recent - on relations between information and estimation. Beyond aesthetic value, these relations underlie some of the main tools in Shannon theory, such as the Entropy Power Inequality. They also give considerable insight into and a quantitative understanding of several estimation theoretic objects, such as the costs of causality and of mismatch, as well as the performance and structure of minimax estimators. Further, they enable the transfer of analytic tools and algorithmic know-how from one domain to another. Examples will be given to illustrate these points.

In a distributed message passing model a communication network is represented by an n-vertex graph whose vertices host processors, and edges serve as communication links. One of the most fundamental goals in this setting is breaking the symmetry in the network. Specifically, the tasks of computing vertex coloring, maximal matching, and maximal independent set are of great importance. In the mid-eighties several randomized distributed algorithms for these problems were devised. [Luby 86, Alon, Babai and Itai 86, Israeli and Itai 86]. These algorithms require O(log n) rounds, and until recently they remained the best-known ones. We present significantly improved results for these problems. These results include: 1. A randomized algorithm for computing a maximal matching in O(log Delta+ (log log n)^4) rounds, where Delta is the maximum degree in the graph. This result is provably optimal for all log Delta in the range [(log log n)^4, sqrt {log n}]. 2. A randomized maximal independent set algorithm requiring O(log Delta sqrt{ log n}) rounds. 3. A randomized (Delta+1)-coloring algorithm requiring O(log Delta + exp{ sqrt {log log n}}) rounds. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Low arboricity graphs include planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude any fixed minor, and many other graphs. These graphs may have unbounded maximum degree. Nevertheless, for low arboricity graphs we obtain a maximal matching algorithm that runs in O(sqrt {log n}) time, and a maximal independent set algorithm that runs in O(log^{3/4} n) time. The talk is based on a joint work with Michael Elkin, Seth Pettie, and Johannes Schneider.