Theory of Parallel and Distributed Computation

点击翻译按钮获取中文摘要

The goals of this continuing research project are to identify primitive operations in parallel and distributed computation, and to establish tight bounds on their complexity. Within this general framework, emphasis is placed on: (i) The design and analysis of algorithms for REALIZABLE models of parallel and distributed computation; (ii) the development of techniques that are applicable for a wide range of computational models and problem variations; (iii) the analysis of `simple` classes of algorithms which are easy to implement. This project concentrates on the following areas: (a) normal hypercube algorithms; (b) sorting networks; (c) list ranking; (d) algorithms for distributed networks, in particular, for the dynamic asynchronous network model; and (e) multiple-resource scheduling.