pozorvlak

What I saw on my holidays

by Miles, age 32¾

General themes

Big computations aren't just array-munging any more

CvRDTs are (almost?) as general as they can be

What are you talking about, and why should I care?

Now that we live in the Big Data, Web 3.14159 era, lots of people want to build databases that are too big to fit on a single machine. But there's a problem in the form of the CAP theorem, which states that if your network ever partitions (a machine goes down, or part of the network loses its connection to the rest) then you can keep consistency (all machines return the same answer to

Here's where I understand the state of the art to be:

In this INRIA tech report, Shapiro, Preguiça, Baquero and Zawirski (SPBZ) prove, amongst other things, that a sufficient condition for CRDTs to achieve eventual consistency on networks which may reorder and duplicate packets (which I'll call flaky networks, henceforth) is that
1. the underlying datatype forms a semilattice,
2. messages are full states,
3. incoming messages are combined with the node's current state using the least-upper-bound operation in the semilattice.
It's possible to relax condition 2 and still achieve eventual consistency over flaky networks by fragmenting the state into independent parts and transmitting updates to each part separately. For instance, in the G-Set CRDT (an add-only bitset) one can transmit only the index of the element to be added.
In [these slides from a talk at Dagstuhl](http://www.dagstuhl.de/mat/Files/13/13081/13081.BaqueroCarlos.Sl

"Write your name and badge number in the space provided. You may not turn over the exam paper until I say so."

Kung obediently picked up his pen, and wrote "Fury, K." in the first box and "4637" in the second.

He tried to breathe deeply and focus his qi, but the serenity he needed would not come. This was his last chance. He lived a bare, monastic existence and could live happily on a Detective's pay himself, but Bubbie Zosia's medical treatment got more expensive every month. She'd survived Hitler, and he was damned if he'd let her die from neglect. But he'd made some serious mistakes as a rookie which had blown his chances of promotion by the management track. That left only this track: heavily oversubscribed, and with a very low acceptance ratio. But at least the hours he'd spent in the dojo would now count in his favour.

A thought struck him. This was a test. Well, obviously this was a test. But maybe it was a test within a test?

Kung breathed deeply, stole a quick look at the proctor, and flicke

	$ curl -s -upozorvlak:<my password here> http://api.twitter.com/1/statuses/mentions.json \| jf -p user/name user/screen_name text
	[
	{
	"text" : "@pozorvlak I have to admit that if you have polymorphism then things like +. are particularly pointless.",
	"user" : {
	"name" : "Christopher Yocum",
	"screen_name" : "cyocum"
	}
	},
	{

	/* tc-arc.c -- Assembler for the ARC
	Copyright 1994, 1995, 1997, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
	2006 Free Software Foundation, Inc.
	This file is part of GAS, the GNU Assembler.

	GAS is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2, or (at your option)
	any later version.

	#!/bin/sh

	# Suppose you want to do blind reviewing of code (eg for job interview
	# purposes). Unfortunately, the candidates' names and email addresses are
	# stored on every commit! You probably want to assess each candidate's version
	# control practices, so just `rm -rf .git` throws away too much information.
	# Here's what you can do instead.

	# Rewrite all commits to hide the author's name and email
	for branch in `ls .git/refs/heads`; do

	%
	% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
	%
	\section[PrimOp]{Primitive operations (machine-level)}
	\begin{code}
	{-# LANGUAGE CPP #-}
	module PrimOp (
	PrimOp(..), PrimOpVecCat(..), allThePrimOps,
	primOpType, primOpSig,
	primOpTag, maxPrimOpTag, primOpOcc,

	#!/usr/bin/env python

	PLUS = '+'
	MINUS = '-'
	CONCAT = ''
	ops = [PLUS, MINUS, CONCAT]

	def op_sequences(n):
	if n == 0:
	yield []

	#!/usr/bin/perl

	# Script to (generate a script to) fix excess use of double-quotes in HAML.
	# To use:
	#
	# haml-lint app/views/ > haml_errors
	# grep "you don't need string interpolation" haml_errors \| awk '{print $1}' > single_quote_me
	# perl single_quote.pl
	# bash fixme.sh
	# git commit -a -m "Use single-quotes in straightforward cases"