NECESSARY AND SUFFICIENT CONDITIONS FOR BROADCAST CONSENSUS PROTOCOLS

We consider consensus protocols in asynchronous distributed systems th at are based on broadcast communication. We show that a necessary and sufficient condition for the existence of a deterministic consensus pr otocol is delivery of each broadcast message to at least inverted righ t perpendicular (n + k + 1)/2 inverted left perpendicular processes in an n-process system subject to k crash failures with either eventual fair broadcasting or eventual full broadcasting. The broadcast model c aptures the idea of a broadcast communication medium, such as the Ethe rnet, in which messages, if delivered, are delivered immediately and i n order but not necessarily to all processes.