Actually, the original Paxos paper is about a "forgotten Greek island, Paxos, and its Parliament". And allegedly he presented it in an Indiana Jones outfit the first time.
Byzantine generals were there in one of his earlier papers.
Yep, the original Paxos paper wasn't easy to understand, and he says so in his follow up paper "Paxos made simple"[1] whose name justifies its existence as well.
Byzantine generals were there in one of his earlier papers.