3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – agent154 May 20 '13 at 23:24
  • $\begingroup$ Yes that's true. Please mark as answered if your question is answered. $\endgroup$ – Peter May 26 '13 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.