Distributed Computing Q&A regarding the homework
More recent questions will be at the beginning
(top) of the page.
Q&A Homework 1:
> Can we present an algorithm, or must we write an
automaton.
Algorithm (pseudo-code) is fine, and even
desired. As long as it is an algorithm
describing a
finite automata.
Anyhow, when you refer lower bound in 4a, you mean
message, right?
and when you refer lower and upper bounds in 3b, what
do you mean, time, message
or both?
You are required to provide and prove upper
and lower bounds on the BIT complexity (worst case total number of bits
exchanged between neighboring automata) for both the Asynchronous, and
Synchronous rings.
> in
question 3, there is a part that says "Whenever a node x become
> idle", does the term idle
means that the node x will no longer receive
> or
send any message in the underlying algorithm?
No !. Whenever a processor receives a message it
again goes out of idle state.
> regarding question 4, part b,
when stating tight upper and lower bound
> in
synchronous model, does it mean bound on the bit complexity?
Yes. Bit communication
complexity.
> also,
can I assume that each automata known the number n of identical
> finite
automata?
NO !. An automata, as you
know, has a constant number of states.
Therefore it cannot "know" a number that requires log n bits.
> Question 2a:
> * Can we assume one single initiator
node?
YES
> * If we use variables at each node, can
we assume that the
> beginning of the algorithm they
will be initialized to 0?
You need to specify what
value you want the variables to be initialized to.
> Question 2b:
> * Similar to a question you already
received for 1b - can we use
> ACK(i) instead of ACK?
YES
> Question 3:
> * Can we assume that once messages are
sent out of a node that
> the node
has completed the computation and is back to the idle state
> (until
receiving a new message)?
yes
Regarding question 4
-Perhaps you could clarify the
meaning of 'Exactly
one node receives a
WAKE'.
>>>> It means that the ring of automata is sitting
there idle nothing is happening until exactly ONE node gets an external WAKE
signal (or if you wish, is awaken spontaneously). Then as a result this one node starts the
distributed algorithm such that at the end of the algorithm the node that is
the predecessor to the one that was awaken, will know that it is the
predecessor.
Are you assuming there is another
algorithm that is running in parallel and
we will use it further? Or we need to
implement an algorithm where we
discover the predecessor such that it causes
the next (single) automata to
get AWAKEN.
>>>> I assume neither
of the two options. Only
my previous answer.
- What is bit complexity?
>>>> The total number
of messages of size 1 bit that are sent in the execution of the algorithm. Or, count how many bits are sent across
single edges - this is the bit complexity.
For example, a message with three bits going around the ring one time
costs 3n bits.
I have two
questions regarding question 4 in the distributed computing homework,
3. a) Can I assume that the node unique name is of
size O(log(n)) bits?
NO! The
finite automata are all identical. Indistinguishable.
They do not and cannot have unique ids.
3. b) Can the automaton have a temporary memory to store the
clock?
A
finite automata is a finite automata, has finite amount of memory
regardless of the ring size. Can remember anything
which may be encoded with a finite number of bits.