On the Amount of Randomness Needed for Improving Distributed Wireless Link Scheduling Under Arbitrary Interference

We study the Distributed Wireless Link Scheduling (DWLS) problem: there is a set of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> autonomous stations, called senders, each with a message to be delivered to some other station, called receiver. The names and locations of all stations are arbitrarily selected and unknown to each other, to mirror an arbitrary scenario that may occur in mobile communication. Each pair ((sender,receiver),message) is called a request, and the event of successfully delivering the message is called the realization of the request. In the DWLS problem, the requests are realized through wireless communication links (which is a conceptual notion of two nodes being capable of direct wireless delivery of a message) between the stations. The decision to transmit a message is made locally by each station. We consider networks where communication links may interfere with each other, where the interference is an arbitrary input function of each pair of links, customarily called affectance; if the total affectance of other links whose senders are currently transmitting is above a given threshold, the considered transmission is not successful. In the above context, we study the impact of the number of truly random bits used by each link/sender, on the length of the transmission schedules. Specifically, for any set <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</i> of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> requests with maximum average affectance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$A(L)$ </tex-math></inline-formula>, we present a deterministic algorithm (i.e., 0 random bits) and a randomized algorithm using <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\log A(L)\log n)$ </tex-math></inline-formula> random bits per link. (In this abstract we present formulas in simplified forms, for brevity.) The lengths of their transmission schedules are <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(A(L)^{2}\log ^{3} n)$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(A(L)\log n)$ </tex-math></inline-formula>, respectively. We then combine both approaches to get a randomized solution using <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\log W \log n)$ </tex-math></inline-formula> truly random bits per station with schedules of length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O\left ({{\frac {A(L)^{2}}{W}\log n}}\right)$ </tex-math></inline-formula>, for any <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$W\le A(L)$ </tex-math></inline-formula>. To the best of our knowledge, our study is a first step towards understanding the trade-offs between randomness and time complexity of Link Scheduling under arbitrary interference. It is particularly important as currently used (in practice) wireless protocols are either deterministic or use a very small random seed of (truly) random bits.