Parallel Complexity Theory (Research Notes in Theoretical Computers Science)

Parallel complexity theory is one of the fastest-growing fields in theoretical computer science. This rapid growth has led to a proliferation of parallel machine models and theoretical frameworks. This book presents a unified theory of parallel computation based on a network model. It is the first such synthesis in book form. The network paradigm is fundamental to the understanding of parallel computation, and this assertion is backed up by new and refined theoretical results. Chapters cover the basic model, comparison of the network model to others, programming techniques for a practical network model, efficient simulations of the general network model (including a universal, feasible network), extension of the network model and definition of arity, universal networks, including discussion of their lower bounds and the conditions under which they hold.