Models of Distributed Computation
Stub. Why a formal model is needed; the message-passing model (process actions, channels, sync vs. async), shared variables and Linda, modeling mobile agents, relationships between models, and complexity measures; then how algorithms are represented — guarded actions, nondeterminism, atomicity, and fairness (unconditional/weak/strong, central vs. distributed schedulers).
Before analyzing any algorithm, fix what “an algorithm” and “an execution” even mean in a distributed setting. Covers the two dominant computation models (message-passing with channels, vs. shared variables) and how to translate between them, plus the classification axes that determine what a model can express — synchronous vs. asynchronous, named vs. anonymous, reactive vs. transformational — and complexity measures suited to distribution (message complexity, not just time). Then covers the notation used to write a distributed algorithm (guarded-action/UNITY style), including the nondeterminism and nonatomicity that are the whole reason these algorithms are hard, and fairness as the assumption that rules out a scheduler unfairly starving an enabled action forever.
Outline (TODO — flesh out each)
- The need for a model
- A message-passing model — process actions, channels, sync vs. async
- Shared variables — Linda
- Modeling mobile agents
- Relationships among models — simulating one model with another; an impossibility result with channels
- Classification: reactive vs. transformational; named vs. anonymous
- Complexity measures
- Guarded actions; nondeterminism; atomic operations
- Fairness — unconditional, weak, strong
- Central vs. distributed schedulers