Paxos is certainly non-trivial in the sense that tiny changes can break it, but in terms of functionality it is not that big. 50 KLOC just seems like a lot of code to me.