Is the set of servers that participate a paxos value too (ie determined using the consensus algorithm), or is it configured ? Can you grow a cluster without bringing it down ?
The consensus algorithm is only used to elect a master -- once the master is identified, it coordinates all the distributed transactions. If the master dies, everyone who remains elects a new master and re-escalates all unprocessed write transactions to the new master.
Read transactions are processed locally by each node, so only writes need to be escalated.