Analysis of Asynchronous Binary Arbitration on Digital Transmission-Line Busses

A common misconception is that asynchronous binary arbitration settles in at most four units of bus-propagation delay, irrelevant of the number of arbitration bus lines. We disprove this conjecture by presenting an arrangement of modules on m bus lines, for which binary arbitration requires [m/2] units of bus-propagation delay to settle. We also prove that for any arrangement of modules on m bus lines, binary arbitration settles in at most [m2/] + 2 units of bus-propagation delay. © 1994 IEEE