Distributed Computing exam 2000

Distributed Computing Q&A regarding the homework

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

Q&A Homework 2:

Good night.

I have a question about the 3rd question:

May i assume that when the algorithm starts the leader knows for sure that

there is a cut, it just doesn't know where it is? and also is there a

possibility of another cut creation during the algorithm execution?

Carefully read only the first sentence of the question and you will find

the answer to both questions.

its about question 1)c)

-------------------------

1) at the first line you refer to (3a) yet i assume its a mistake & you meant

(1a). is that right ?

YES

2) its is not clear what messages-complexity is required in this question ?

THE BEST YOU CAN ACHIEVE

should it be proportional to the number of edges in the graph (as in 1a) or to

the number of nodes in the graph (as in 1b) ?

OR TO SOME FUNCTION OF BOTH

i ask this because a theres a simple DFS algorithm that works on either

directed/undirected graphs.

Hello,

another question:

in 1(b), after modifying the algorithm, its output

still has to remain the same? I.e., it is still DFS,

and DFS-tree is built?

YES.

Hello,

two questions:

1. In question 1, do I have to show that the token

must traverse all the links on the network - in my

algorithm, or in ANY distributed DFS traversal

algorithm?

YOur algorithm should make sure the traversal is

a DFS like. I.e., there is some DFS on the network

that in some scenario would traverse the network in the

same order that your algorithm ends up traversing the network.

(and in any event all links are traversed in such a traversal).

2. In (c) part of the first question, what algorithm

do you mean - of (3a)? The algorithm we design in

question 3, part (a)?

Sorry, meant 1a.

OLD Q&A on Homework 1:

am still confused about whether f(x1,x2...xn) equals f(xn,xn-1...x1).

a function on a ring, is what is computable on a ring, i.e., f(x1,x2...xn) equals f(xn,xn-1...x1)

If it is not the case what is the correct order of the input bits (CW or CCW) ?

Is it relevant (is the ring oriented), and if so, does the processors know this order ?

IN a reply to another email I wrote:

In any event the ring is not necessarily oriented.

and a function on a ring, is a function that is computable

on a ring. So if you mean that

f(x1,x2,...,xn)=f(xn,xn-1,...,x2,x1), that is true.

Hi, Yehuda!

Q6:

In the "Question & answers" you say that f(x1...xn) is not necessary equal to f(xn...x1)

and that the ring doesn't have to be oriented.

NEVER SAID, or if I did then I erred.

If so, I do not see how a processor can know whether it got x1..xn or xn...x1. Is it ok to

just evaluate both f(x1..xn) and f(xn..x1) and say, that the consumer will decide itself which

output does it need ?

Thank you,

Good night!

Q5:

May I assume that:

- all nodes are initialized to the same values ?

YES.

- the model is synchronous ?

- all nodes are awoken at once ?

For each of these two parameters (Synchronous and awaking all at once):

It may not be always the case, but when proving an impossibility you may

assume so. It is certainly possible that this is the case (although it does not have

to be the case).

Q4, Q6:

I don't quite see the difference between the environment of these questions

and if I prove Q6, Q4 is wrong. What do I miss ?

One key difference is that while in Q4 processors dont know n, in Q6 they know.

See also my previous replies.

Thank you,

Hello,

I have a few questions regarding the assignment.

question 6

What is a function on a ring ? Is it like the definition in question 4

(i.e. a function with a boolean string as an input and a boolean as an

output).

YES>

Can we assume that the function is cyclic ?

YES.

If not, how do we know where the input starts ?

question 4

Are there any limitations on the ring of processors that we can use ?

NO (if I understand your question, which is not so clear).

Thanks

Question1:

I think I have a scenario where the algorythm described fails

(I have checked it with one freind so I hope I dont waste your time)

Lets say we have nodes:"1" (initiator), "a", "b", "k"

* node "k" only "listens" (termination detection messages) and doesnt participate on sending and receivng normal msgs.

* all SENT matrix are initiated to (Send(1,a) = 1 other 0)

Scenario

INIT1) node"1" spontaneously send msg to node"a" (node K matrix (Send(1,a) = 1 other 0))

2) node "a" receives this msg and node"a" sends two msgs one for node"b" (which wont get to b in our scenario) and one for node"1".

TERMINATIONS MSGS:node "a" send (Received(1,a)Sent(a,b)Sent(a,1)) , IMPORTANT: K Won't receive this msg in our scenario

3) node "1" receives the msg from "a"(prev stage) and send one msg for "a"

TERMINATIONS MSGS:node "1" send (Received(a,1)Send(1,a)), IMPORTANT: K Won't receive this msg in our scenario

4) "a" recieves the msg from "1" (prev stage) and become idle

TERMINATION MSGS:Rceived(1,a), VERY IMPORTNAT: K GETS THIS MSG

And Now for node "k", Sent(1,a)=1 other =0 and Received(1,a)=1 and other = 0 SO Sent=Received

and we have one msg from a to b that is NOW ON TRANSIT ! (see stage 2)

THE THING IS THAT EACH NODE SENDS EACH TIME THE TOTALS OF THE NUMBERS IN EACH ITEM.

I.E., IT WILL SEND IN STEP 4: SEND(1,A)=2. ALSO NODE A WILL SEND RECEIVED(1,A)=2, THE

TOTAL NUMBER OF MESSAGES IT GOT FROM A.

Question 2a

Can I assume an "end of msg" signal (different from 0 and 1) ?

It can be simulated by doubling all bits 0->01 1->10 and end of msg is ->00

YES. (OR THAT NODES KNOW THE LENGTH OF THE MESSAGE).

this is not an assumption, you should see that it is easy to implement and get it.

Question6

I think that either the ring must be oriented or the function f satisfies

f(x1,x2..xn) = f(xn,x2..x1) (and also should cyclic)

because the processor doesnt know which is on its "left" (are fictive numbering, is it X(i-1) or X(i+1) )

WRONG .

__________________________________

1. What's the difference between an automata and a processor?

Just an automata is the same as a processor. However, usually

in the Q2 and others, when we say an automata we mean a finite

state automata, i.e., one that cannot count etc.

2. Are the rings in all questions, except 2, bi-directional?

YES.

3. What's the purpose of the connections between nodes in a ring? Is it for

message transfering or for other uses, such as connecting automata states or

getting one node output into the input of the next one?

Just sending messages between them.

The messages of course effect the states of the different automata.

__________________________________

----

is there only one node that starts the algorithm or can there be more than

one. for one processor it seems very easy to solve the problem.

SINCE YOU ASK, YOU GET AN EXTRA QUESTION:

SHOW THAT IF ONLY ONE NODE STARTS THEN IT IS POSSIBLE.

BUT IN AN ANNONIMOUSE RING WHEN ANY SUBSET

MAY START THEN IT IS IMPOSSIBLE.

----

to compute the AND of all inputs we should only ask if there is someone with

a "0" bit on the ring. this requires only a single message to go around the

ring with a single bit from the one who initiated it until it gets back to

him.

in case multiple nodes are allowed to start the computation simultaneously,

then its a different story.

so can multiple nodes start doing the same

SAME ANSWER AS ABOVE, THERE IS NO ONE INITIATOR. MULTIPLE

MAY START.

Q 3b

--------

you still haven't answered about whether the snapshot algorithm may

intervene with the messages of the underlying algorithm (change msg order,

detain msgs, etc).

please answer.

NO, IT MAY NOT.

__________________________________

Hello,

If nothing else mentioned in the question, we assume:

FIFO, asynchronous model,

YES

for rings: identical (anonymous) processors that don't known their IDs and

don't known n, bi-directional, oriented ring.

Is that true?

NO. FOR RINGS THE QUESTION SHOULD SAY ANNONIMOUS IF IT IS.

ALSO KNOWLEDGE OF n either should say specifically or you should

understand it from other parameters. I.e., if all processors are identical,

then their initial knowledge is also identical, i.e., not having unique names

and ring size.

Question 6,7:

Is the ring oriented?

DOES NOT MATTER. NOTICE, EVEN IF THE RING IS NOT ORIENTED STILL

IT IS TRIVIAL TO SEND A MESSAGE AROUND THE RING IN ONE DIRECTION -

EACH PROCESSOR HAS TO FORWARD A MESSAGE RECEIVED ON ONE INTERFACE

ON THE OTHER INTERFACE. THE ORIENTATION ALGORITHM WAS DESIGNED ONLY

SO THEY ALL agree ON TO NAME ONE DIRECTION CW AND THE OTHER CCW (COUNTER

CLOCK WISE)

Can we assume that the number of input bits is always equal to the number of

arguments to f?

What is the number of arguments(inputs) to the computed function f ? Is it

always n ? Can it be more than n?

ASSUME ALWAYS n.

If yes, then how the input bits are supplied to the ring? There must be at

least one processor which receives more than one input bit, right?

NO. ASSUME THE BITS ARE MAGICALLY GIVEN TO THE PROCESSORS. NOT YOUR

PROBLEM HOW THEY GET THERE.

If number of arguments is k and k<n, Is the input supplied to subset of

processors?

Is the function always cyclic ?

YES.

If not, how the processor knows what bit he

received ? I mean, if order of bits is important, then how the processor

knows if he received the first bit of the input, the second or the i-th bit

and etc.

Can we assume that a processor that received input bit at the beginning of

the algorithm, must also become "awake" as a result.

NO!

In other words, if

there is a subset A of processors that received input and there is another

subset B of processors that start the algorithm (become "awake" and send

messages not as a result of receiving a message).

I THINK YOU DID NOT READ THE QA IN THE WEB PAGE.

__________________________________

Question 3b

----------------------

please indicate whether it is possible to disturb the alg on which we need

to take a snapshot (e.g.: change order of msgs, acknowledge msgs,... )

NO.

__________________________________

Hello

In regard of question 2b:

the question is about a finite autmata or

about a processor ?

FINITE AUTOMATA

If it is about a finite automata it doesn't seem better than the asynchronous case is it? (we just have another "event" which is the "synch" event and it is sent to every body . so if k machines where in state x thay will all move to state y (if they didnt get any other event) so it still doesn't seperate between processors).

SO TRY TO WRITE A FORMAL PROOF THAT WHATEVER YOU FOUND IN 2a IS THE BEST FOR THE SYNCHRONOUS CASE AS WELL.

__________________________________

I've got two question regarding question 4:

A. Do the processors know the value of "n" (total number of processors and the size of the domain of f),

since if they hold a function from {0,1}^n then they should know the value of "n".

ANSWER:

NO. HERE IS THE SCENARIO YOU HAVE TO KEEP IN MIND: A FACTORY MANUFACTURES THESE

PROCESSORS. IT MAKES ZILION OF THEM including their progrmas and software. AN ARBITRARY

NUMBER OF COPIES OF THESE MACHINES ARE THEN TAKEN AND HOOKED TOGETHER TO FORM A RING.

THE PROOF RELIES MOSTLY ON PROPERTIES OF DISTRIBUTED ALGORITHMS THAN ON PROPERTIES OF

BOOLEAN FUNCTIONS. ESSENTIALLY THERE IS SOMETHING ABOUT THE SETUP FROM WHICH YOU CAN

FORMALLY PROVE THAT THE ONLY POSSIBLE FUNCTION IS THE FUNCTION THAT IS FIXED AHEAD OF TIME.

B. Regarding your comment of question 4 to the students question: Am I correct to assume that we should

could think of the algorithm as an algorithm that recieves both function f's boolean result table as input

and the value of n ? Or in other words, f is "encoded" in the algorithm but defined for every n.

ANSWER:

F IS "ENCODED" IN THE PROCESSORS - TRUE.

IS DEFINED FOR ANY POSSIBLE RING SIZE - YES.

__________________________________

Q2 - What do you mean by "undirectional links".

UNIDIRECTIONAL - INFORMATION CAN FLOW IN ONLY ONE DIRECTION (AS WAS

EXPLAINED IN CLASS). NO THING FLOWS IN THE OTHER DIRECTION.

Does a node have right and left neighbors in it's interfaces?

HAS ONE INCOMING LINK AND ONE OUTGOING LINK.

What do you mean by bit-complexity ?

NUMBER OF BITS SENT OVER ALL THE LINKS THROUGHOUT

THE ALGORITHM EXECUTION.

Can a node send messages to both sides ?

SEE ABOVE.

What is wrong with this simple alg. ?

The awakened node send "You are the predecessor"-message

to it's left-neighbor, a node which gets this message knows

that it is the predecessor.

SEE ABOVE.

Q5 - What is wrong with the following alg. for even rings ?

The awakened node is initialized with FLAG=1 and the others with 0.

The awakened node sends to it's right neighbor "BeLeft-Message"

When a node receives "BeLeft-Message" from it's right neighbor it

performs the routine Switch() and sends "BeLeft-Message" to it's right

neighbor. When a node receives "BeLeft-Message" from it's left neighbor

it only sends "BeLeft-Message" to it's right neighbor. The alg. is

finished when the node with FLAG=1 receives "BeLeft-Message".

YOU MAKE ONE WRONG ASSUMTION, TRY TO THINK WHCH.

Q6 - Does the function f is cyclic ?

YOU MAY ASSUME SO.

Is there an awakened node (a root) to start/end the alg. ?

NOT NECESSARILY

Can i assume FIFO ?

ONLY IF YOU NEED FOR THE PROOF

Is the ring oriented?

DOES NOT HAVE TO BE

Do the nodes have left neighbor and right neighbor in it's interfaces?

1. Question 2 –

can a finite automaton, as defined in the question, store an arbitrary number ?

More specifically:

Assume the number of processors is n, and assume the number of states in the

automaton is k. Then, for large enough n, there is at least one state that

represents 2 different numbers.

Thus, I can’t store any ID, from the range 1…n in the automaton. RIGHT

Did I miss anything ? NO

2. Question 2b -

In a synchronous model, can a processor count the pulses, that is – can it

execute a computation following a pulse without receiving a message ? YES.

In other words – can the fact that a message was NOT received during a round

serve as an indication for initiating a computation ? YES (BUT IF IT IS A FINITE STATE

THEN THE COMPUTATION IS STILL LIMITED TO THAT OF A FINTE STATE MACHINE

COMPUTATION).

3. Question 2b –

What’s the meaning of an upper bound for bit complexity ??? One can always

design an algorithm that would send infinite number of unnecessary bits, so I

don’t really understand what’s an upper bound in this sense.

GIVE A TIGHT UPPER BOUND MEANS: FIND AN ALGORITHM WHOSE

WORST CASE COMPLEXITY (BIG O NOTATION) IS THE SAME AS THE

LOWERBOUND (BIG OMEGA NOTATION).

4. Question 4 –

What do you mean with “Eventually” ?

MEANING, WITHIN A FINITE AMOUNT OF TIME.

Do you mean that every processor decides, after a certain number of bits, that

it should output and halt ? If so – how many bits ? Does it depend in the order

in which it received the bits ?

(I understood from the question that the processors don’t know of n)

5. Question 5 –

I lack a precise definition of “orientation algorithm”.

Does every processor know its ID ?

Do we deal with synchronous model ?

Do all the processors start at the same time ? Some of the processors ? Exactly

one of them ?

6. Question 6 –

Does every processor know its ID ?

NOT NECESSARILY

7. Question 7 –

The Hint contains two questions. I’d like to verify that those questions within

the hint are not to be answered.

THE HINT SAYS THAT IN ONE WAY THAT I KNOW TO PROVE THE CLAIM

YOU END UP ANSWERING THESE QUESTIONS. PERHAPS YOU CAN COME

UP WITH A DIFFERENT WAY THAT DOES NOT ANSWER THESE QUESTIONS.

Additionally, I’d like to make sure the last line is part of the hint (so it

seems).

WRONG, THE LAST LINE IS ANOTHER SUB QUESTION PART OF QUESTION 7.

__________________________________
Question 2 : The ring in undirectional so how a prededecessor is defined?

For example: who is the predecessor in the following graph ?

awakened automation

* V THE NODE WITH THE STAR * ASSUMING CLOCKWISE DIRECTIONALITY

0---0---0---0---0

| |

--------------------

Question 4 : I think you ask to prove something which cannot be proved -

For example:

* n=2

* f(X1,X2) = X1 AND X2

* Each processor get the input, send it to the other processor, when getting the boolean input - and function

is computed. Each processor outputs (X1 AND X20 and hults).

** This function is cyclic since f(X1,X2)=f(X2,X1)

** However f is not constant !!!

YOU ARE ABSOLUTELY RIGHT IN THE EXAMPLE, BUT YOU ASSUME SOME THING WRONG.

WHAT IS YOUR WRONG ASSUMPTION??

Question 5 : What is orientation algorithm ?

IN AN ORIENTATION ALGORITHM EACH NODE MARKS ITS TWO INCIDENT LINKS

WITH R (RIGHT) AND L (LEFT), I.E., EXACTLY ONE INTERFACE R AND ONE L.

INITIALLY THE NODES MARK THEIR TWO INTERFACES

ARBITRARILY WITH THESE MARKINGS. IN THE END OF SUCH AN ALGORITHM (I.E.,

THE OUTPUT OF SUCH AN ALGORITHM) THE NODES SETS THE MARKINGS SUCH THAT

FOR ALL THE EDGES AROUND THE RING, ONE END IS MARKED L AND THE OTHER R.

__________________________________
I have a questuin regarding Q1 in the homework:

I think I did not understand question since the following case contraticts

it...

Assume we have a network with 2 nodes a,b.

a starts the alg. and send msg to b and b receives the msg.

At node b SENT(a,b)=1 (initialized to 1).

And RECV(a,b)=1 (since b received the msg).

SEND(b,a)=RECV(b,a)=0 (Since there were no messages b sent to a)

So the conditions are satisfied - in node b SENT(i,j)=RECV(i,j) for all i,j,

but I cannot be sure that there is not another message from a to b that is

currently in transit.

Answer:

Two things with respect to the scenario you describe:

1. node b checks the conditions either before it processes

a received message (i.e., before receiving it) or after

the message was completely processed (and all resulting

messages have been sent). So in your scenario b did not send

any new messages. That is, messages processing is an indivisible

operation. Nothing can take place at a node in the

interval of time at which a message is being processed.

2. node a, sending a second message. Is this message sent

spontaneously or as a response to node a receiving another

message. In the former the SEND(a,b) would be initialized to 2

and in the later their should be another node whose SEND(x,y) was

initialized to a value different than zero.

__________________________________

__________________________________