Diffusing Computations Self Test

Question 1

In this module we differentiate between acks and messages. An ack travels along channels exactly like a message does; however, we use acks only to acknowledge messages. So acks are not themselves acknowledged.

Part a

When agent \(x\) gets a message from agent \(y\) then which of the following is True

At that point agent \(y\) is on the tree, i.e., \(y.parent \neq null\)
At that point agent \(y\) is not on the tree, i.e., \(y.parent = null\)

Part b

When agent \(x\) gets a message from agent \(y\) then what action does \(x\) take if \(x.parent = null\)?

Part c

When agent \(x\) gets a message from agent \(y\) then what action does \(x\) take if \(x.parent \neq null\)?

Part d

If x.num_unacked = 0 then which of the following is True?

There are no messages in \(x\)'s outgoing channels.
\(x\) has no descendants.
There are no acks in \(x\)'s incoming channels

Part e

True or False?

If \(x.parent = y\), then \(x\) has received more messages from \(y\) than \(x\) has sent acks to \(y\).

Part f

True or False?

If \(x.parent = y\), and \(w\) is different from \(x\) and \(y\), then \(x\) has received more messages from \(w\) than \(x\) has sent acks to \(w\).

Answers

Question 1

Part a

When agent \(x\) gets a message from agent \(y\) then which of the following is True

At that point agent \(y\) is on the tree, i.e., \(y.parent \neq null\)
At that point agent \(y\) is not on the tree, i.e., \(y.parent = null\)

Part a: Answer

At that point agent \(y\) is on the tree, i.e., \(y.parent \neq null\).

This is because if there is a message in an outgoing channel from \(y\) then \(y\) is on the tree.

Part b

When agent \(x\) gets a message from agent \(y\) then what action does \(x\) take if \(x.parent = null\)?

Part b: Answer

Agent \(x\) sets \(x.parent = y\) and does not (immediately) send an ack to \(y\) for that message.

Part c

When agent \(x\) gets a message from agent \(y\) then what action does \(x\) take if \(x.parent \neq null\)?

Part c: Answer

Agent \(x\) sends an ack to \(y\) and leaves \(x.parent\) unchanged.

Part d

If x.num_unacked = 0 then which of the following is True?

There are no messages in \(x\)'s outgoing channels.
\(x\) has no descendants.
There are no acks in \(x\)'s incoming channels

Part d: Answer

All are True.

Part e

True or False?

If \(x.parent = y\), then \(x\) has received more messages from \(y\) than \(x\) has sent acks to \(y\).

Part e: Answer

True.

\(x\) has received one more message than it has acknowledged.

Part f

True or False?

If \(x.parent = y\), and \(w\) is different from \(x\) and \(y\), then \(x\) has received more messages from \(w\) than \(x\) has sent acks to \(w\).

Part f: Answer

False.

\(x\) immediately acknowledges messages from agents other than its predecessors.

K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology