More recent questions will be at the beginning
(top) of the page.
Q&A Homework 3:
> Question - about q2:
> Can we (or should we) relate to anytime a
processor send V to all (king or in
> exchange 1,2) ,
>
> It means it also send V to
‘himself’?
YES.
> I have a few questions about Q1:
> 1.I did not understand the meaning of
"king-M" in the pseudo - code, what is
> it?
King-M is the name of a variable into which the
message received from the king
process at this phase is stored.
I.e., in Exchange 2 of phase $k$ the message I will recieve
from process k will
be stored in my local variable king-M.
> 2.Is the message received from pj is V if the sender and the receiver (pj)
> are
> not byzantic?
NO. There is a specific assignment statement
saying into which variable the
message received from Pj goes.
> 3.Does the message has constant size as in the
algorithm presented in class?
YES
YES
> Since you wrote in a
previous answer that the ring is bi-directional, am
> I right in saying that when a bi-directional
link is cut then messages
> are lost in both directions?
>
in question 3
>
can it be assumed the the smallest unique id is 1 or O(1)
>
NO.
>
in question 5
>
what is the bound on a message length
>
is the ring oriented (so that left and right are defined) do the
>
processors have O(logn) memory
Message length is O(log n) bits.
Ring is not oriented.
Right, nodes memory is not limited, i.e., O(log
n) or O(n log n) are fine.
> 1. (Q3) What are the model
limitations to consider (message size, memory
> size, one node begins the proccess
or spontanious initiation, etc.)
no memory limitations. Messages size O(log
n) bits (one node id), any subset
may start spontaneously.
> 2. (Q3) In rounds we mean TIME rounds, not
rounds around the ring, right?
Yes, roungs are pulses
of the global clock.
> 3. (Q4) I assume we are using a Bi-Directional
ring in this quetion - is this
> correct?
YES
> 4. (Q4) What complexity are you reffering to - time, message, bit?
Messages.
> 5. (Q4) In section c, do we at least know that
n>1? Otherwise, I don't think
> in a asyncronious
system can solve this problem when n=1 (any message the
> leader sends himself will not return and so
the leader will keep waiting for
> some feedback... and never finish)
Think again. Why is it any better when
n>1.
> 6. (Q5) When we talked in class about leader
election, we said the end result
> must be that each node knows who the leader
is. In a ring with no unique
> ID's, does leader election mean each node
knows the direction and distance of
> the leader from himself?
Once there is a leader then this information can easily be computed.
Any subset may spontaneously start
the algorithm.
> In question 3, is there a designated leader,
which initiates the algorithm,
> or may some subset initiate it?
I see. You are right, they
will identify the leader either by some random
string that the leader chose to identify itself with, or as you have
suggested by telling how many hops the leader is from each of the other nodes.
> There seems to be some misunderstanding here.
> I am simply trying to understand what the
definition of a leader-election
> algorithm is in this case. Does every node
need to know who the leader is, or
> only the leader himself? And if every node
needs to know the identity of the
> leader, how is this defined in a system where
nodes do not have unique
> identifiers?
> This is why I asked originaly
if the algorithm ends with each node knowing
> the amount of steps to his right/left to the
leader, or some other identifing
> tool.
Not necessarily. Not all the
nodes necessarily start at the same time.
You can do what ever you want with in the model given.
> Question 3:
> Does all nodes in this synchronous network
start at the same time ?
> Can we delay messages according to the ID as
shown in class in the leader
> election in ring algorithm ?
>
in question 3:
>
can I provide 2 different algorithms - one that achieve the lower
>
bound for messages and one for time, of should I provide one algorithm
>
that achieves both of them?
Best if you can provide an algorithm that achieves both, otherwise
go with two.