Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
A solution to the following fundamental communication problem is presented. Suppose that n tokens are arbitrarily distributed among n processors with no processor having more than K tokens. The problem is to specify a bounded-degree network topology and an algorithm that can distribute the tokens uniformly among the processors. The first result is a tight Θ(K + log n) bound on the complexity of this problem. It is also shown that an approximate version of this problem can be solved deterministically in O(K + log n) on any expander graph with sufficiently large expansion factor. In the second part of this work, it is shown how to extend the solution for the approximate distribution problem to an optimal probabilistic algorithm for the exact distribution problem on a similar class of expander graphs. These results have direct applications to the efficient implementation of many-to-one and one-to-many communication requests, as well as to the solution of load-balancing problems in distributed systems.
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997