Combinatorics Seminar
When: Sunday, November 6, 10am
Where: Schreiber 309
Speaker: Guy Rutenberg, Tel Aviv University
Title: Priority Transmission
Abstract:
We consider a broadcast model involving multiple transmitters and
receivers. Transmission is performed in rounds, where in each round
any transmitter is allowed to broadcast a single message, and each
receiver can receive only a single broadcast message, determined
by a priority permutation over the transmitters. The message
received by receiver R in a given transmission round is the one
sent
by the first transmitter among all those broadcasting in that round
according to the permutation of R. In our model, each pair of
transmitter and receiver has a unique message which the transmitter
has to send to the receiver. We prove upper and lower bounds on
the minimal number of rounds needed for transmitting all the messages
to their respective receivers. We also consider the case where
the priority permutations are determined geometrically.
Joint work with Noga Alon.