Symmetry Reduction Enables Model Checking of More Complex Emerging Behaviours of Swarm Navigation Algorithms

October 30, 2015 ~ Adrian Colyer ~ 1 Comment

Symmetry Reduction Enables Model Checking of More Complex Emerging Behaviours of Swarm Navigation Algorithms - Antuñya et al. 2015 Don't let the title put you off - this paper is all about robot swarms! Previously we looked at some nature-inspired optimisation algorithms, including Particle Swarm Optimisation which draws inspiration from the behaviour of flocks of ... Continue Reading

How to memorize a random 60-bit string

October 29, 2015 ~ Adrian Colyer ~ 3 Comments

How to memorize a random 60-bit string - Ghazvininejad et al. 2105 A bit of fun for today - this paper has been the source of many articles around the net over the last couple of weeks (though not many have dug into the actual algorithms... ). Inspired by an XKCD cartoon, the challenge is ... Continue Reading

Split-Level IO Scheduling

October 28, 2015 ~ Adrian Colyer ~ 1 Comment

Split-Level IO Scheduling - Yang et al. 2015 The central idea in today's paper is pretty simple: block-level I/O schedulers (the most common kind) lack the higher level information necessary to perform write-reordering and accurate accounting, whereas system-call level schedulers have the appropriate context but lack the low-level knowledge needed to build efficient schedulers - ... Continue Reading

Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming

October 27, 2015 ~ Adrian Colyer ~ Leave a comment

Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming - Matveev et al. 2015 An important paradigm in concurrent data structure scalability is to support read-only traversals: sequences of reads that execute without any synchronization (and hence require no memory fences and generate no contention). The gain from such unsynchronized traversals is significant because they account ... Continue Reading

Fast In-memory Transaction Processing using RDMA and HTM

October 26, 2015 ~ Adrian Colyer ~ 4 Comments

Fast In-memory Transaction Processing using RDMA and HTM - Wei et al. 2015 This paper tries to answer a natural question: with advanced processor features and fast interconnects, can we build a transaction processing system that is at least one order of magnitude faster than the state-of-the-art systems without using such features? The authors build ... Continue Reading

Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis

October 23, 2015 ~ Adrian Colyer ~ Leave a comment

Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis - van den Hooff, Lazar, et al. 2015 Many users would like their communications over the Internet to be private, and for some, such as reporters, lawyers, or whistleblowers, privacy is of paramount concern... Recently, officials at the NSA have even stated that “if you have enough ... Continue Reading

Implementing Linearizability at Large Scale and Low Latency

October 22, 2015 ~ Adrian Colyer ~ 8 Comments

Implementing Linearizability at Large Scale and Low Latency - Lee at al. 2015 Yesterday we saw how to layer a strictly serializable transaction model on top of an inconsistent replication protocol. Previously we've also looked at how to bolt-on a causal consistency model on top of eventual consistency. Today's paper demonstrates how to bolt-on (layer) ... Continue Reading

Building Consistent Transactions with Inconsistent Replication

October 21, 2015 ~ Adrian Colyer ~ 3 Comments

Building Consistent Transactions with Inconsistent Replication - Zhang et al. 2015 Is there life beyond 'beyond distributed transactions?' In this paper, Zhang et al. introduce a layered approach to supporting distribution transactions, showing that a Transactional Application Protocol can be built on top of an Inconsistent Replication protocol (TAPIR). This direction is similar in spirit ... Continue Reading

High-Performance ACID via Modular Concurrency Control

October 20, 2015 ~ Adrian Colyer ~ 1 Comment

High-Performance ACID via Modular Concurrency Control - Xie et al. 2015 In yesterday's paper on Existential Consistency at Facebook the authors postulated that a future direction might be to use different consistency mechanisms for different parts of a system. 'High Performance ACID via Modular Concurrency Control' applies a similar idea within the confines of an ... Continue Reading

Existential Consistency: Measuring and Understanding Consistency at Facebook

October 19, 2015 ~ Adrian Colyer ~ 2 Comments

Existential Consistency: Measuring and Understanding Consistency at Facebook - Lu et al. 2015 At the core of this paper is an analysis of the number of anomalies seen in Facebook's production system for clients of TAO, which is impressively low under normal operation (0.0004%) - to interpret that number of course, we'll have to dig ... Continue Reading

the morning paper

a random walk through Computer Science research, by Adrian Colyer
Made delightfully fast by strattic

Month: October 2015