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 1:

Hi,

I just want to make sure that I understand the lessons and the exercise

correctly:

- when a vertex V is asked to take snapshot in time t, he should save

the messages in queue and the messages that in t are to the way to V.

Did I miss anything?

>>> Well, the vertex was asked to take a snapshot at time t, it might

actually take the snapshot a short while after t, or at t (assuming it has

not yet taken the snapshot). When it takes the snapshot then in the

algorithm we saw in class (assuming FIFO) it starts recording the messages

incoming from its neighbors that have not yet told it that they took a

snapshot. The recording continues on each incoming link until the

vertex receives a signal over the link that the vertex on the other side

took a snapshot as well. Let me know if you still have questions.

- In Q2 are there 2 different algorithms, one for 2a and the other for 2b, with

different complexity?

Yes, there are different algorithms for the asynchronous and the synchronous

cases.

- How can algorithm on unidirectional ring have different upper and lower

bounds?

The upper bound is the worst case complexity of the algorithm, the

lower bound is the best lower bound you can prove on the problem.

I have some questions about ques. (4) in the

excersice:

I don't fully understand the question, so...

-> what are the relations between the processors - do

they know their orientation (e.g. left/right) ?

>REPLY: Either way. It is not relevant.

-> are there any assumptions we can make about the

algorithm that the processors (run) / (compute the

function)? does it must end after a known constant

time ?

>REPLY: Eventually each processor should compute

f(x) and halt.

-> does the only thing we know about the algorithm

(that each processor runs) that it begins after the

processor gets an input bit (i.e. after that we don't

know anything about message passing (e.g. bit

sending), etc. that each proccesor does) ?

RIGHT.

-> can we assume a syncronous network?

>REPLY: again, does not matter.

-> what does it mean "a processor which computes f" -

do you mean a processor that always (without relation

to the sequence that it gets the bits from the other

processors) calculate f currectly?

>REPLY: They run some algorithm of message exchange

and then the processor computes f(x). To compute

f(x) necessarily means correctly. Otherwise I dont know

what it means to compute f(x) not correctly.

From

Sent: Tuesday, February 25, 2003 5:58 PM

To: afek@math.tau.ac.il

Subject: Distributed Computing Questions

Yehuda hi,

I have few questions about the subjects that were

studied in the last lecture (and a question about the

homework):

1) In the Beta-synchronizer, you said that the first

part is to built a spanning tree. However, we haven't

learned how to built such a tree. (to be more precise,

my problem is how each processor know who are its

children (e.g. the nodes which got the message first

from the previously mentioned processor))

>>A: You are partially right: We did learn how to build

a spanning tree (with the broadcast and echo) however

we assumed only one node starts. We did not study

how to make sure that there will be one tree even if

several start broadcast and echo. And, as you said,

we did not address the issue of nodes knowing who

their children are. For this last point I challenge you to

come up with a simple solution.

2) How can time complexity be measured in an

Asynchronous network (i.e the sending/receving time

can be a bounded but infinitly large) - i.e. in the

time complexity analysis of the synchronizers the

result was adjusted to a "syncronized time" - does

this the way to deal with it ?

>>A: We discussed it twice in class. For time

complexity analysis, and ONLY for that, assume

that the slowest packet in the network took 1 time

unit from sending it until the receiving node starts

processing it. Notice that during this one time unit

still there could be an unbounded of packets going

over another link.

3) in the homework (question 1), what is the meaning

of "Idle (from the underlying algorithm's point of

view)" - does it mean that the node finished all its

activities (i.e. it will not sent/receive messages any

more) or just transit stop (i.e. it is idle between

message dealing) ?

>>A: It means that this node finished all its activities,

AS FAR AS it knows. I.e., it could receive a new

packet one second later and become active again.

It cannot anticipate when will it receive new packets.

Thanks,

__________________________________

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.

__________________________________

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.

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 ?

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

__________________________________

__________________________________