# Principles of Distributed Computing - “processors” and “states”

So I'm learning about distributed computing, and I do understand a lot of the prerequisite material on algorithms and automata and whatnot... but I'm curious about the definitions I'm seeing as I read my textbook.

A system consists of $n$ processors $p_{0},\dots,p_{n-1}$, where $i$ is the index of the processor $p_i$. Each processor is modeled with a (possibly infinite) state machine with state set $Q_i$. The processor is identified with a particular node in the topology graph. The edges incident on $p_i$ are labeled arbitrarily with the numbers $1$ thru $r$, where $r$ is the degree of the $p_i$. Each state of the processor $p_i$ contains $2r$ special components: $inbuf_i[\mathcal{l}]$ and $outbuf_i[\mathcal{l}]$.

Does this mean that each state of an n-state state machine has a separate inbuffer and outbuffer? Based on the wording of this, it seems to imply that there are n of each buffer, which would say to me that an outbuffer is mapped directly to the inbuffer of another state in another processor.

## 1 Answer

Based on the wording of this, it seems to imply that there are n of each buffer

Assuming that each edge in the network graph $G=(V,E)$ corresponds to a bidirectional channel, there are $4|E|$ many buffers in total: For an (undirected) edge $(p_i,p_j)$, we have one pair of in/out buffers for $p_i$ and one pair for $p_j$.

Each state of the processor $p_i$ contains $2r$ special components: $inbuf_i[l]$ and $outbuf_i[l]$.

Let's look at an example to get an intuition for what the above means: Suppose that we have some network where $p_3$ is connected to $p_1$ and $p_2$. Let's assume that process $p_3$ sends a message $m$ to process $p_1$ and has received (but not yet processed) a message $m'$ from process $p_2$. Moreover, $p_3$ has a local variable $counter$. Then we could represent the current state $\sigma_3$ of $p_3$ as $$\sigma_3 = (inbuf_3[1],inbuf_3[2],outbuf_3[1],outbuf_3[2],counter).$$ According to the above example, $m' \in inbuf_3[2]$ and $m \in outbuf_3[1]$. Note that the state of the network is given by $(\sigma_0,\dots,\sigma_n-1)$.

• Oh, ok.. I see it - I was mistaking the subscript 'i' for the index of the particular state in $Q$, when it's referring to the index of the processor. So Each processor has two buffers per channel to another processor. – agent154 May 20 '13 at 23:24
• Yes that's true. Please mark as answered if your question is answered. – Peter May 26 '13 at 15:45