## Parallel and Distributed Computing

*14 Jul 2011 12:22*

Cellular automata are parallel, interacting finite state machines; some of them are Turing-equivalent, that is, can compute any computable function.

Complexity classes --- in space (memory), time, other resources?

What would analog parallel computing look like? (A partial differential equation, presumably.)

Uses: data mining, simulations.

*See also*:
Computation, Automata, Languages;
Computer Networks;
Multi-Agent Systems

- Recommended:
- David Gelernter, Mirror Worlds
- Metropolis and Rota (eds.), A New Era in Computation
- Mitchel Resnick, Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds [Review: Turtles Up the *]
- Nancy A. Lynch, Distributed Algorithms [Laudatory review by Danny Yee]
- Bruce Sterling, "Pervasive Computing," Viridian Note 00113

- To read:
- Andrews, Fundamentals of Multithreaded, Parallel, and Distributed Programming
- Jon Barwise and Jerry Seligman, Information Flow: The Logic of Distributed Systems
- Ron Bekkerman, Mikhail Bilenko and John Langford (eds.), Scaling up Machine Learning: Parallel and Distributed Approaches [Blurb]
- Albert Benveniste, Eric Fabre and Stefan Haar, "Markov
Nets: Probabilistic Models for Distributed and Concurrent Systems",
IEEE Transactions on
Automatic Control
**48**(2003): 1936--1950 - George F. Coulouris, Jean Dollimore, and Tim Kindberg, Distributed Systems: Concepts and Design
- Shlomi Dolev, Self-Stabilization [Blurb]
- Wan Fokkink, Introduction to Process Algebra
- Neil Gershenfeld, When Things Start to Think
- Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory
- H. Guclu, G. Korniss, M. A. Novotny, Z. Toroczkai and
Z. R´cz, "Synchronization landscapes in small-world-connected computer
networks", Physical Review
E
**73**(2006): 066115 = cond-mat/0601058 - Peter J. Haas, Stochastic Petri Nets: Modelling, Stability, Simulation
- Holger Hermanns, Interactive Markov Chains [Markov models for distributed system analysis and design]
- Jane Hillston, A Compositional Approach to Performance Modelling [blurb]
- Huberman, Ecology of Computation
- Zohar Manna and Amir Pnueli, The Temporal Logic of Reactive and Concurrent Systems
- Robin Milner, Communicating and Mobile Systems: The Pi-calculus
- Peter Pacheco, MPI
- Wolfgang Reisig, Elements of Distributed Algorithms: Modeling and Analysis with Petri Nets
- L. Ridgway Scott, Terry Clark, and Babak Bagheri, Scientific Parallel Computing [Blurb]
- Sterling et al., How to Build a Beowulf
- R. E. Tarjan, Data Structures and Network Algorithms
- Gerard Tel, Introduction to Distributed Algorithms