Abstract

It is well known that the consensus problem can be solved in a distributed system if, after some time TS, no process fails and there is some upper bound δ on how long it takes to deliver a message. We know of no existing algorithm that guarantees consensus among N processes before time TS +O(Nδ). We show that consensus can be achieved by time TS +O(δ).