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 Symmetry Reduction Enables Model Checking of More Complex Emerging Behaviours of Swarm Navigation Algorithms
Month: October 2015
How to memorize a random 60-bit string
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 How to memorize a random 60-bit string
Split-Level IO Scheduling
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 Split-Level IO Scheduling
Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming
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 Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming
Fast In-memory Transaction Processing using RDMA and HTM
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 Fast In-memory Transaction Processing using RDMA and HTM
Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis
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 Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis
Implementing Linearizability at Large Scale and Low Latency
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 Implementing Linearizability at Large Scale and Low Latency
Building Consistent Transactions with Inconsistent Replication
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 Building Consistent Transactions with Inconsistent Replication
High-Performance ACID via Modular Concurrency Control
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 High-Performance ACID via Modular Concurrency Control
Existential Consistency: Measuring and Understanding Consistency at Facebook
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 Existential Consistency: Measuring and Understanding Consistency at Facebook
the morning paper 