Distributed algorithm and reversible network

Motivated to design a feasible optical network architecture for the future Internet, we address the question of scheduling (wavelength assignment) in an optical network. The key challenge in designing a scheduling algorithm lies in solving a combinatorial optimization problem under very stringent distributed constraints. Specifically, given R random variables x1;… ; xR taking integer values, each variable is required to find its assignment so that collectively they maximize ¿rWrxr subject to some linear constraints that Ax ¿ C. In doing so, each variable can only avail of two pieces of information (and nothing else): one, its own weight Wr, two, given its current values (and the values of other variables being unknown), can it increase it by +1 or not. As the main result of this paper, we present a randomized algorithm that solves this problem. Our algorithm builds upon classical theory of reversible networks. To the best of our knowledge, this is the first such algorithm for such a stringent distributed problem.