[drkp]

Yes, Viewstamped Replication is underappreciated! It is actually older than Paxos, although the original paper is pretty incomprehensible too.

The more recent "Viewstamped Replication Revisited" paper is probably my favorite introduction to consensus protocols and their use in a real system: http://pmg.csail.mit.edu/papers/vr-revisited.pdf