A distributed computing system can achieve consensus while introducing fewer message delays by using an algorithm that allows the constituent devices to vote on functions received directly from one or more clients. If a conflict occurs, a leader device from among the devices can be selected such that the leader device already knows of the other devices' previous votes, and can determine an appropriate function to propose, using an immediately subsequent proposal number, without performing the first phase of the Paxos algorithm. Alternatively, each device can independently determine, by using the same repeatable mechanism used by a leader device, what function the leader device would propose, and can then vote for that function using the immediately subsequent proposal number. If the devices' votes again result in a conflict, the Paxos algorithm can be used, or additional iterations can be performed prior to resorting to the Paxos algorithm.