> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/distributed_systems.md).

# distributed\_systems

## Basic idea

Multiple networked nodes that coordinate to appear as one system. The interesting problems all come from partial failure, asynchrony, and the absence of a global clock.

## Key formulas

* CAP: under partition, choose either consistency or availability
* FLP: no deterministic consensus in async with even one crash failure
* Quorum: $R + W > N$ ⇒ read sees most recent write
* $f$-Byzantine consensus needs $N \ge 3f+1$ nodes
* Causality: $a\rightarrow b$ is a partial order; vector clocks capture it exactly.
* Failure detectors classify which crash suspicions eventually become complete and accurate.
* Chandy–Lamport records a consistent distributed cut; state-machine replication agrees on a deterministic command order.
* Parallel speedup: $S(p)=T\_1/T\_p$; efficiency: $E(p)=S(p)/p$
* BSP cost per superstep: $w+gh+L$; LogP exposes latency, overhead, gap, and processor count.
* Message cost model: $T(n)=\alpha+\beta n$
* TCP flow control protects receivers; congestion control adapts in-flight data to network capacity.
* Consensus and atomic broadcast implement one another under standard assumptions; read/write registers alone cannot solve wait-free consensus for two processes.