I haven't done much with Paxos and friends and I only read the blog, not the paper, but this seems like elect a coordinator, send all changes through the coordinator which creates an ordering and sends out the ordered changes to the group. And by the way, hide the coordinator in your switch.

This seems pretty straightforward -- running MySQL replication in a sane way is essentially appoint a master server, send all writes through that, and hope you don't need to have a new election.