This Article   Bibliographic References   Add to:  Optimal
Prioritized Conflict Resolution on a Multiple Access Channel
October 1991 (vol. 40 no. 10) pp. 1102-1108  A multiple access
broadcast network (MABN) is a computer network in which there is
a single shared communication channel and every network node can
receive all messages transmitted over the channel. A major
difficulty in using broadcast communication is the issue of
access to the channel. The authors deal with the following
prioritized conflict resolution problem: a collection of c
messages is initially distributed among nodes on an MABN; each
message is associated with a value representing its priority or
deadline; and it is required that the messages be broadcast in
ascending order of this value. This problem is solved by a
distributed prioritized conflict resolution algorithm. It is
proved that the expected waiting time of the ith network node to
transmit is Theta (i+log c), which is optimal. It is also shown
that the algorithm runs in the expe