Spent the other day reading up on ZooKeeper a little.  ZooKeeper is a distributed, open-source coordination service for distributed applications.  Out of the box ZooKeeper can be used for name service, configuration and group membership.  Building on ZooKeeper's primitives, you can create barriers, locks, queues, etc.

Sounds interesting enough, but what got me really interested was ZooKeeper's atomic broadcast, the guts of ZooKeeper.  Atomic broadcast is very closely related to consensus (apparently equivalent in certain asynchronous systems).  Both are fundamental problems in distributed systems.

So what exactly is atomic broadcast?  To answer this, lets work our way from Reliable Broadcast.

Reliable Broadcast

Reliable Broadcast is the weakest type of fault-tolerant broadcast.  Informally, if a correct process broadcasts a message then all correct processes eventually receive that message.  Reliable Broadcast doesn't impose any message delivery ordering.

FIFO Broadcast

FIFO Broadcast is reliable broadcast that satisifies FIFO Order.  If a process broadcasts message m₁ before message m₂, then no correct process delivers m₂ before it delivers m₁.  For example, if message m₁ is a deposit of $100 into your banking account and message m₂ is a subsequent withdrawal of $75, you most definitely want FIFO Broadcast, otherwise your bank will charge you an overdraft fee (on top of their ridiculous $5 ATM fee).

Causal Broadcast

Sometimes FIFO Order is not enough because FIFO ordering too limited in context (a single process).  You need Causal Order to guarantee that if the broadcast of message m₁ "happens before" or "causally precedes" the broadcast of message m₂, then no correct process delivers m₂ before it delivers m₁.

For example, imagine three processes a, b and c.  Process a broadcasts m_1a, "Banks to charge $5 ATM fee."  Process b delivers m_1a then broadcasts message m_1b, "That's outrageous!"  Without Causal Order, process c could deliver message m_1b before m_1a,

m_1b : "That's outrageous!"
m_1a : "Banks to charge $5 ATM fee."

which doesn't make sense (what is outrageous?).  Causal Order requires delivery of m_1a before m_1b.

Atomic Broadcast

Causal Order imposes a partial ordering in the system, so messages without causal relationships are logically concurrent and do not have any delivery order guarantees.  This can be problematic in some cases.  For example, imagine two replicated databases DB₁ and DB₂.  Process a broadcasts message m_1a, "deposit $100."  Process b broadcasts message m_1b, "charge 10% fee."  Since there is no causal relationship between the messages, this situation may arise,

DB₁ : $0 + $100 - ($100 * 10%) = $90
DB₂ : $0 - ($0 * 10%) + $100 = $100

which is obviously not desirably.

Atomic Broadcast imposes a Total Order on the system so that all messages are delivered in the same order, whatever that order maybe.  So in this example, it's either $90 or $100 but never $90 in one database and $100 in the other.

We can further classify Atomic Broadcast by the actual ordering it imposes.  FIFO Atomic Broadcast is then Reliable Broadcast that is FIFO Order and Total Order.  Causal Atomic Broadcast is then Reliable Broadcast that is Causal Order and Total Order.  Causal Atomic Broadcast is the strongest guarantee we've examined.

Summary

This diagram nicely summarizes Reliable Broadcast and the orderings above (taken from "A Modular Approach to Fault-Tolerant Broadcasts and Related Problems," which the above is basically a summary of).

So there you have, atomic broadcast.

Time flies when you're having fun (even when you're not).  It's been more than a year since my last work related blog.  Writing about random computer science and programming topics is like going to the gym; once you get off the routine it's very easy to just sit on your literal and figurative ass.

For my first topic back I want to relay some sequential random sampling algorithms I came across this week.  It started out when we needed some random samples from the database.  Performance issues aside, MySQL lets you do

select column from table order by rand() limit n

to select n random rows from a table.  The randomness of the rand() function aside, someting troubled me about this approach.  Won't your results be skewed toward the lower rows when you get duplicate random values?

So I was searching around for some random sampling algorithms and ran across a few from the works of Jeffrey Vitter I found rather interesting.

Algorithm S

Sequentially go through N elements to select n random samples.  For each element generate an independent random variable U between 0 and 1 and test that NU > n.  If true, skip, otherwise select for the sample and decrement n.  In either case decrement N.

Algorithms A-D

These algorithms optimize Algorithm S by skipping elements.  Define a skip function S(n,N) that will tell us how many elements to skip.

Algorithm S and its optimizations are for sequential sampling where N is known.  But sometimes N is not known or it's prohibitive to determine N.  Then we turn to reservoir samping. 

Algorithm R

There is a reservoir R of n sample elements.  The invariant is that the reservoir is a random sample of all the elements we've processed thus far.  To maintain the invariant, as we sequentially process each element generate an independent random variable between 0 and the current element.  Then either put the current element into the reservoir or ignore it.

Algorithms X, Y and Z

Optimization of algorithm R so we can skip over elements, much like Algorithms A-D.

Skimmed a paper titled "Pure versus Impure Lisp" by Nicholas Pippenger the other day.  Impure Lisp dialects allow mutations.  Pippenger wanted to know if pure Lisp, without mutation, was less "powerful".  Under two conditions he showed the following,  

A computation in impure Lisp upper bounded by O(n) is lower bounded in pure Lisp by big-omega n log n.  Basically, given the same problem there's a theoretical lower limit to pure Lisp's efficiency compared to impure Lisp. 

But then the guys at FP Lunch lead me to a follow-up paper titled "More Haste, Less Speed: Lazy Versus Eager Evaluation".  In it, Bird, Jone and de Moor showed that if you changed the pure Lisp evaluator to pure and lazy as oppose to Pippenger's original pure and eager then you can get the same linear time as the impure program.  Interestingly enough, the authors noted that lazy evaluation is often implemented with mutations behind the scenes (via memoization), so it's really a discussion of restricted mutation.  This is along the lines of an earlier posting I made about the problem with immutability and how compilers can, behind the scenes, solve some of the inefficiencies of immutability, but then it becomes a philosophical debate on what it really means to be immutable (or pure).

And that concludes another installment of interesting topics I'll never need to know.

Here's an example of where I read random articles just because the title is very catchy: F-Bounded Polymorphism for Object-Oriented Programming by Peter Canning, William Cook, Walter Hill, Walter Olthoff and John Mitchell.  Polymorphism is already confusing enough.  Just look at the Wikipedia entry on type polymorphism: "this article may be confusing or unclear to readers".

There's parametric polymorphism, let-polymorphism, impredicative polymorphism, ad-hoc polymorphism, intensional polymorphism and subtype polymorphism.  So WTF is F-bounded polymorphism then.  If there's no Wikipedia entry does it really exist?  Despite no mention in Wikipedia F-bounded polymorphism is pretty important and I'm using it everyday without knowing it.

Lets start with "bounded quantification".  With bounded quantification you can do something like this

Moveable {
 Moveable move(int x, int y)
}

Moveable moveMeOneInch(Moveable m) {...}

The method moveMeOneInch takes in some a Moveable, moves it one inch, and returns a Moveable.  It is polymorphic and will work on Cars, Trains, Points--anything that's Moveable.  All good, except we'll have to do some unsafe type casting.

Car c = ...
Car movedCar = (Car) moveMeOneInch(c);

But with Java 5 we can do something like this

<T extends Moveable> T moveMeOneInch(T m) {...}

Car c = ...
Airplane p = ...

Car movedCar = moveMeOneInch(c);
Airplane movedAirplane = moveMeOneInch(p);

and get the type safety we want, because "run time is a little late to find out whether you have a landing gear".  What we've done is created an "F-bound".

F-Moveable[t] = { move : int, int -> t }
F-Moveable[Car] = { move : int, int -> Car }
F-Moveable[Airplane] = { move : int, int -> Airplane }

Note the type appears on both sides. 

Here's a real world example.  The Collections utility class has a max method that takes in a Collection of Comparables and return the max of the collection.

public static <T extends Object & Comparable<? super T>> 
 T max(Collection<? extends T> coll) {...}

//Integer implements Comparable<Integer>
Collection<Integer> ints = ...
Integer i = Collections.max(ints);

Here we bound the type of the collection and the type is part of the bound for Comparable.  A collection of integers, and integers are comparable to integers.

That's F-bounded polymorphism in a nutshell.  Now you can say, "yea, I like Java, it supports F-bounded polymorphism."

I picked up Real World Haskell last week when Gilad Bracha warned me that I might become unemployable if I don't brush up on my functional programming skills.  I found his comment amusing because I have Lisp on my resume and have always wondered if anybody cared that I know Lisp.  Know is an exaggeration;  all I remember is cons, car, cdr and thinking why the f*** are there so many parentheses.  Yet here I am, a decade older, reading up on lambda-calculus and folding to remain marketable.

One thing that might confuse the imperative programmer when reading Haskell code for the first time is the unfamiliar function definitions.  In Java if you have an "add" method that adds two ints and returns an int you might write it as

add (int, int) : int

or

int add (int a, int b)

or

(int, int) -> int

In any case it's clear that add takes two ints and returns an int.  But in Haskell your add function will be

add :: Int -> Int -> Int

You might guess that the first int is the first argument, the second int is the second argument, and the final int the return type.  But not really.  In Haskell all functions are single argument functions.  Add is a function that takes an int, returns a function that takes an int, returns a function that evaluates to an int.  Here's an example with the map function. 

map abs [-1,-3,4,-12] 
[1,3,4,12]

:type map
map :: (a -> b) -> [a] -> [b]

It appears that the map function takes two arguments, a mapping function (in this case the abs function that returns the absolute value of a number) and a list, and applies the mapping function to each element of the list.  But as you can see in the type definition map is a function that takes a mapping function (a->b), returns a function that takes a list [a], returns a function that evaluates to a list [b]. 

This is because the lambda-calculus which Haskell is based upon doesn't have built-in support for multi-argument functions.  It'd be pretty easy to support multi-argument functions according to Benjamin Pierce, but to confuse us imperative programmers they decided it would be easier and better to use higher-order functions (functions that accept and/or return functions). Instead of f = λ(x,y).s we have f = λx.λy.s.  Then we would just write f v w and do two "reductions" instead of writing something like f(v,w). 

Converting multi-argument functions into higher-order functions is called "currying" after Haskell Curry, for whom the Haskell language is named.  Haskell was a contemporary of Alonzo Church, who developed the lambda-calculus during the 1920s.  While at Princeton Church supervised the doctoral thesis of Alan Turing, the tape machine guy, who committed suicide in 1954 after being prosecuted for his homosexuality.   (That was for all the history buffs out there.)

Once you see it a few times the notation becomes "normal".  It's actually very elegant (among other things).  Everything is a single argument function.  I mean everything.  You know how Smalltalk guys are always saying everything is an object, well the lambda ultimate guys say everything is a function, including numbers like 23 and 17.  Maybe that's what Java's missing, a pithy tag line.  Java, where everything is a....