Distributed Computing Q&A regarding the homework


More recent questions will be at the beginning (top) of the page.

Q&A Homework 1:

Correction  to the QA:

In q1(b) a node can send messages of type M(i) where i is an integer.     

1. must it be typed in english (or is hebrew acceptable as well)?

Hebrew acceptable.

2. in question 1(b) - can a node only send M?

A node can send only one type of messages, that is correct.

3. In question 3 - Can a node only send M(i) messages, or a ACK too?

an ACK too.

> q4 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.

Q4 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.

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.