All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any efficient algorithms that are completely symmetric, i.e. which do not elect a leader and therefore allows querying any server in the cluster?
Since a given server doesn't crash very often, from an engineering perspective it would seem like electing a leader is simpler because you can worry separately about what to do when the leader goes down, which would seem to allow for more modular protocol design. On the other hand, if all the queries are directed at one sever, then this server will get hammered, since in addition to all queries, it will have to send updates to all other servers in the cluster.
My questions can be phrased as follows: is dependence on a leader seen as a problem? Are there some fundamental issues with this approach in addition to problems with load? Do we have some fundamental problems when running a leaderless protocol? Do we know if there exists efficient leaderless protocols?