We describe our experience in building a fault-tolerant data-base using the Paxos
consensus algorithm. Despite the existing literature in the field, building such a
database proved to be non-trivial. We describe selected algorithmic and engineering
problems encountered, and the solutions we found for them. Our measurements
indicate that we have built a competitive system.