patternMinor
Principles of Distributed Computing - "processors" and "states"
Viewed 0 times
principlesprocessorsstatesdistributedandcomputing
Problem
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.
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.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#12159, answer score: 6
Revisions (0)
No revisions yet.