Distributed Computing
Q&A regarding the homework
More recent questions will be at the beginning (top) of the page.
Q&A take home exam:
We
said the default, i.e., if it does not say differently then
it
is Asynchonous.
-----Original
Message-----
From:
Sent:
Tuesday, February 12, 2002 11:48 AM
To:
afek@tau.ac.il
Subject:
Home Exam
Hello,
regarding
question 2:
is the
ring synchronous?
Q3(a).
As a base to
the proof can I say that the queue is initialized with 0 and with 1?
[Yehuda Afek]
No,
the q is initially empty
BUT, if you cannot do it for an uninitialized q, do it for an initialized q, you will get part of the points
For an initialized
queue.
Q4(a)
When the
processor writes a value into the one-use bit, and the one-use bit's status is dead,
can I return
a value that idicates a failure in the writing operation?
[Yehuda Afek] no, you get no indication.
Question
2b:
Do we work in synchronous or
asynchronous model? Put another way,
does the expected complexity in the
question refer to time complexity,
or message complexity?
Question
4b:
Your definition of bounded-use bit is
ambiguous.
Which of the following is true?
1) bounded-use bit with the bound k
allows exactly k writes and k reads
2) bounded-use bit with the bound k
allows x reads and y writes with x+y=k
Choose
which ever you want.
Either
way, which ever you want.
-----Original
Message-----
From: Sent: Wednesday, February 13, 2002 9:08 PM
To: afek@math.tau.ac.il
Subject: Question no. 4
(4b)
Let's assume
the "bounded use bits", is bounded by K operations.
Can it take
K READ operations and (K+1) WRITE operations
or
Can it take
K operations (K is the sum of READ and WRITE operations together) ?
Either
way is fine.
-----Original
Message-----
From: Sent:
Wednesday, February 13, 2002 8:09 PM
To:
afek@tau.ac.il
Subject:
Home Exam
Hello,
another
question regarding Q4:
you wrote
in Q&A that we should also show how to implement a binary
r/w bit
(single use and bounded use).
Do you
mean that we must use the one-use bit (from paragraph (a)) to
implement
a binary single use r/w bit? or we can use more than 1 such
one-use
bits for that purpose? or maybe we can just modify the
implementation
of the one-use bit to make it binary?
...and
similar for bounded use?
another
question:
there is
one unclear point in the definition of the SERIALIZABLE
operations.
you say
the operation is SERIALIZABLE when it is possible to shrink
the
interval of time of each operation into a point within the
interval
such that the behavior of the points satisfies the
sequential
specification of this operation.
Does it
have to be the same point in each scenario when the operation
is used?
Read
what you wrote above: "It is possible to shrink" i.e., for each
execution
of the implementation it should be possible to make such
shrinkage
so as to satisfy the above.
for
example, if the operation Op contains 2 atomic operations, and I
use the
Op in two different scenarios, in the first one can I choose
to shrink
the Op into a point between the 2 atomic operations, and in
the
second I choose to shrink the Op into the point after the second
atomic
operation?
Q5b
-------
Can I use
multi-write/multi-read normal registers ? (more than one writer to the same
register)
[Yehuda Afek] Yes. However try to do
it with not too many and not too complicated reg's.
Q3a
------
Someone
asked you if the queue may be initialized and you answered NO.
Initialized
queue as a starting point for 2 consensus is a bi-valent state,
[Yehuda Afek] Dont understand this. The
queue is initially empty. If you cannot
prove
for an un-initialized queue then prove it for an initialized queue. IT
will at least
give
you some of the points.
and we
proved in class that NO MATTER which bi-valent state we start we
cannot reach
a one-valent
one-valent junction.
[Yehuda Afek] You are confusing something but I
am not sure what. In class we proved for
reg's
that there is no wait-free consensus algorithm. Now the claim
is for a collection
of
queues with as many read/write reg's as you want. The queue is initially
empty.
moreover I
thing that if there is an implementation of a queue it should be functioning
well
after some
process enter one or more elements to the queue.
so why NOT
initializing queue as a starting point for the proof ?
Q3b
------
Is it
relatively easy to see that sometimes we get(by deq) the element from a
higher
index in the
items array before lower ones, but still I think that in any given FULL
scenario
I can reduce
the interval to points so order is correct.
I think that
who wrotes that code thought about that and that is why the loop in the deq is
starting from 1 (and not from last_non_null).
OR I'm
wrong.....
[Yehuda Afek] could be. I did not check
these scenarios but it could be.
Question
4:
Accoding
to the question, you said that when the object is moved to the dead
state,
no more information can be obtained from it. Can I assume that a call
to
Read operation on dead object will not return?
Can
I assume that Read operation always returns, but with any value in {0,
1}
?
The read operation on a dead object will finish, but will return no
valuable
information.
Question
4b:
What
do you mean by "fixed number" of one-use bits?
I
suppose it must be a function of k, while k is constant and a-priori
known,
before building the bounded use bit. It that correct ?
YES, a bounded use is good only for algorithms (executions) that
use it a fixed (bounded) number of times, where the bound is known
apriorily.
Question
1b:
(1)
Is it allowed to send message that contains number, proportional to n,
for
example: M(n),M(n-1),... ?
Same rules as in the first homework with the last on the ring question.
(2)
Is it allowed to perform operation
if
(k ==0) then...
when
this message M(k) is received, for k in range [0,n] ?
(n
is number of processors in the ring)
See my reply above.
(3)
Is it allowed to look at the messages that are waiting in the queue for
a
certain processor (at the begining of the round, for instance)?
NO.
Ex4.
a.
I still have problems with timing and the idea of sequential
specification.
Suppose
there is very long READ operation which start when the bit is off.
In
the middle of it there are 3 short WRITE operations which are finished
before
the
READ operation is finished. What is leggal functionality for the
one-use-bit
?
Returning
"on"? returning "off"? not returning value? Any
functionality of
those
is legal?
<
READ >
<WRITE> <WRITE> <WRITE>
ANY thing which may be serialized at any point before or after each of
the
writes.
b.
If my implementation can return 1 or can return no value in such
scenario,
Does it violate the sequential
specifications because of that and hecne
bad
implementation ?
I hope my previous answer answers this one too.
c.
What is the prototype of the operation write ? (with or without
parameters
?)
Like of an atomic write to a 1 bit register.
d.
Is the following sentence correct?
"The writer can write many
times and it is fine, however, the reader will
return value only if there was no
more than 1 write operation before".
What was specified in the question is what is correct.
e.
What do you mean by "bounded use bits" - what is the functionality of
this
register?
Read previous questions and answers.
regarding
question 4(a):
1. in
one-writer/one-reader model can I assume that if I want to
read, and
I see that someone else is doing something, then he must be
writing?
and if I want to write, then he must be reading?
Dont
understand the question. Dont know
what is "I see that someone else
is
doing something".
2. if in
the middle of the second allowed Write operation (that will
change
the state from ON to KILLED) the Read operation started, what
should it
return - ON or KILLED? same question about the situation
when Read
accures in the middle of the first allowed Write operation
(that
will change the state from OFF to ON) - should the Read
operation
return OFF or ON? or in both cases it can return any of the
2
possibilites?
You
should read the questions and answers regarding serialization,
and
then you will understand the answer
3. Does
it matter (for the grade for this question) if I use 2, 4 or
20
T&S ergister for the solution? I mean, if I find a solution with 4
registers,
should I try and think of a better solution or it's enough
to give
solution with any CONSTANT number of registers to get all the
points?
Most
important to come up with a solution that uses a constant
number
of T&Ss, the number of
such will not make a big
difference
on the grade.
As
written in the Q&A you should also
show
how to implement a binary r/w bit.
(single
use and bounded use).
Question
5b:
It
is not clear from the question, whether we are allowed to use in our
implementation
both 2-process Test&Set objects
and
atomic R/W registers, OR
we
must rewrite the algorithm, using only a combination of atomic registers
(without
any T&S objects).
The former.
Question
4b:
1)
Is it allowed to use Test&Set objects to build a bounded use bit object,
OR
we
must use ONLY one use bits to build a bounded use bit?
Either is okay , since the one use is built any how from T&Ss.
2)
Can we relay on the fact that one-use bit objects, that we are using to
build
a bounded use object,
are
implemented as we suggest in 4a. If yes, then we implement one-use bit
to
return a special value "dead" if it's dead.
Is
it legal?
Dont understand your question.
Its
a good start. Do it first for a power of 2 rings and then expand to
arbitrary size rings.
Solving
only for power of 2s will already grant you a considerable part of the grade.
-----Original
Message-----
From:
Sent: Sunday, February 10, 2002 3:37 PM
To: afek@math.tau.ac.il
Subject: Take home exam
To simplify
the answer of 1b can we assume that n is a power of 2
1.
In question 1 part b, can I assume that the ring is of size 2^k, for some
integer
k?
Do that, as a first step,
but then extend to arbitrary size rings.
2.
In question 3a: Can I assume that a FIFO queue is initialized with one
(or
more) elements?
NO.
One
use bit supports read and write operations.
According
to the specifications,
what's
the wanted result of read when one-use bit register is in dead state?
You cannot count on it returning anything meaningful in the dead state
and no reader is suppose to read it at this state. You can assume it
non deterministically returns either 1 or 0.
What's
the wanted result of read when one-use bit
register
is in off state (uninitialized) ?
As written in the exam.
i wanted to ask if you
were serious about the fact that typing the exam on a
word
processor will add 5 extra points ???
You
must type the exam, unless you have a very nice and easy to read
hand
writtings.
Q5) b
---------
you ask
to "modify immplementation" and also "using only atomic
read/write
registers"
do you
mean that the ENTIRE new implementation should use only read/write
registers
or that the ADDITION should use only R/W registers while the existing
code
(which you have provided) can still be used (it contains 2-process T&S
objects)
?
No,
the existing implementation (with the t&s bits) with the addition of r/w
reg's.
Q4) b)
-------
in the
Q&A page on the web you asked us to show how to build a 0/1 R/W bit from
the
one-use-bit or from bounded-use-bit.
isn't it
just taking a bounded-use-bit with a bound of infinity ????? & so
there's
nothing else to do
NO,
the requested r/w bit is also bounded use.
Q4) b)
-------
i wanted
to make sure that the bounded-use-bit is such that a WRITE operation
sets its
value to "ON" & from there & on it will remain "ON"
until all K
allowed
operations are consumed in which case it becomes "DEAD". it doesn't
have the
ability to change from "ON" back to "OFF".
NO. You are required to build a one-use bit
- with the on off and dead. From a
collection of
these
you are required to build a bounded use 1/0 read/write reg'.
I'd like
to clarify some point regarding the sequential specification in the Q3:
The
Deq(Q) could return the "empty" value. So, how could we apply the
rules
a) and b)
to such a value (the operation Enq(Q, x) is not defined for "empty"
value)?
assume
x & y are not empty in that rule.
and a deq returns empty in the
sequential
spec only if the number deq's before it is greater equal the number of
enq's
before it.
Q4, in
figure 1, in Deq, the phrase item:=swap(items[i],pass) is supposed to be
item:=swap(items[i],null)
if I'm not mistaken.
RIght.
Q5 - The
processors may call to ONE_TIME_TEST_AND_SET more than one time for
each
processor, do they? Because in the question you say each processor may
access it
only one time.
ONLY
ONCE>
Another
question:
can the
finite automata count the clock pulses?
Finite
automata can do what finite automata can do.
How
many states does a counter that counts more than
a
constant number of pulses has?
Q5
----
when we
need to find the BUG in the code it is not clear what exactly is the
meaning
of "first" in T&S.
(*) is it
the first one that CALLS the function ?
(*) is it
the first one that RETURNS from the function ?
(*)
should we use the definition of sequenciality ? by that you meant that a
register
is atomic if we can take each operation on it & reduce its operation
time to a
single point in time such that after all operation apear to work
correctly
after this was done to all of them.
this
gives a totaly different view of the problem & causes a different
explanation
to this question.
so is
this the way to go ?
YES,
the algorithm should work as you explained, each operation should
be
mapped into a point in time, which is after the operation has started
and
before the operation has terminated.
After all operations of the execution
have
been mapped, THEN the first is the opration whose point is serially first,
i.e.,
earlier than the other points.
Right. It is my mistake in the Q&As:
should
be:
the
"F&E" operation increases the counter variable & returns
the
new value - all done as an atomic operation.
-----Original
Message-----
Question
3(b), Figure 1:
I
think there might be a small bug in the code (if I'm right, the program
will
probably fail with "segmentation fault" before it gets confused with
the
queue :-)
It
is defined:
items[1..] array of swap...
and
the first time operation Enq is performed, item[head] is referenced, but
head=0
because:
(1)
counter initialized to 0
(2)
head = F&A(counter, 1)
(3)
F&A(counter,1) operation returns the old value of the counter, before
the
increment was preformed, according to your answer in the FAQ. The
question
was:
(*)
the "F&E" operation increases the counter variable & returns
the value
it
had
BEFORE being increased, right? it is also atomic so the operation
actually
allocates
unique & successive indices.
And
you answered:
YES
Hello
Prof Afek.
Ex.4,5
a. What is the difference
between One-Time T&S and normal T&S ?
A: Noraml T&S would have a reset operation and will re-usable.
b. Are the test and set
operations in Ex4 are "one-time" ?
YES.
c. Is there reset() operation
in Ex4?
NO.
d. If there exist reset()
operation in T&S object, when can a processor use
it?
ONLY IF IT IS SURE THAT IT IS THE ONLY ONE TO DO IT, i.e., if it
is the last winner, or see the mutual exclusion algorithm in the
Operating Systems book of Galvin and Silberchatz that you learned
from a few years ago.
e. Is the following sentence
correct for Ex5.c ...
"We suppose to built one-time T&S
Object(without reset operation)
from
T&S objects (with reset operation.
Where did you see the reset operation mentioned???
Ex
3. There are 2 roules for the "sequential specification of the
queue".
In these rouls
you write the word "before". To what occasion does this
word refers?
For example, suppose Process P1 calls operaton O1 and
before
it
perform the
first instruction of O1, there is A context-switch and P2
calls
operation O2 -
Did O1 was before O2 ?
READ what is written there, this is the SEQUENTIAL SPECIFICATION, i.e.,
this is how they should behave has the operation been atomic, i.e.,
assuming
the oprations are serialized.
Hi,
About
Q1b: Can I assume each automate has a unique ID or, as before, it comes
out from
a factory, ready to be used in any size ring?
A:
The
later. No IDs, they dont know
N. As before, they come from the
factory for any ring size.
hello,
I
have a few questions concerning the exam:
1.
(Q2b) What is a Las Vegas algorithm (there is no definition)?
A randomize algorithm that always terminates with the correct solution,
but its running time varies.
THe expected running better be bounded,
and in your solution, as small as you can.
2.
(Q3a) I just want to get this straight - Can we prove the claim in any
way
we see fit? There is a (seemingly) much easier proof that fifo queues
cannot be implemented using RW registers then the rigorous proof you
suggest.
See previous QA.
3.
In general, can one write into test & set register (I mean zero the
register
for another use). If not, what is the difference between one time
T&S
register and normal T&S register (If a normal T&S register cannot be
zeroed,
every call after the first is certain to return 1)?
Some times the specification of the testandset reg' include a RESET
operation
doing exactly what you call "zeroing".
So the answer to your question is NO, unless a reset op was specified
you
cannot write into a t&s.
4.
(Q5a) in the definition of one time T&S, is it mandatory that the FIRST
processor
gets 0 and every other gets 1, or is it enough that one processor
gets
0 and the others 1. In the implementation you suggest, it is obvious
that
the first processor that finishes the ONE_TIME_TEST_AND_SET does not
necessarily
get 0, but it does not seem to make the implementation not work
(unless
of course the order is important).
It has to be serializable.
That is, you should be able to shrink the
interval of time of each operation into a point within the interval such
that:
the behavior of the points satisfies that the first one is the only one
to get
0.
hi
I have a few
questions regarding questions 4 and 5
q5: (b)
in case a
processor fails in the middle of the T&S
should
still the first processor later on get 0 or there may be a case where
all later
processors get 1.
[Yehuda Afek] There is no real failures. A
faulty processor is one that is stuck forever or for
every
long time. Thus, in the scenario you describe it must be that had
processor f (for faulty)
wakes
up and contiues he better wins the T&S ( in the original algorithm it could be that a
processor
wins all the
tree but failes before executing the return command and all the other
processors will get 1).
[Yehuda Afek] DOnt understand your
question. It should follow the standard serial specification.
q5 : (c)
in the model
of the T&S bag can the algorithm use shared variables which are regular
atomic
registers or only T&S objects?
Either
way. Can be done without.
q4 : (a)
in the one
use bit there should be a value (0 or 1) or only the state : On Off and Dead?
You
should show also how from a one use (or bounded use) on/off/dead you implement
a
0 1 r/w reg'
Alot of misunderstandings
regarding Ex3 :
a. When you say wait-free
implementation for the Queue,
What do you
mean by that ?
WAIT_FREE
AS WAS EXPLAINED IN CLASS AND IS DEFINED
IN
THE CORRESPONDING PAPER OF Maurice Herlihy.
b. How many Processors use the
queue ? 2 ? more ?
ANY
NUMBER.
c. How many fail-stop
processors are in the model ?
UP
TO N-1
d. Is the model asynchronous ?
YES
e. What do you mean by queue
from read/write registers when you
use swap and
fetch-and-add objects?
IN
SUBSECTION 3(a) there are no SWAP OR FETCH AND ADD.
question
3
------------
as i
understand it :
(*) the
"Swap" operation is an atomic operation , right ?
YES
(*) the
"F&E" operation increases the counter variable & returns the
value it
had
BEFORE being increased, right? it is also atomic so the operation actually
allocates
unique & successive indices.
YES
Question
1
------------
1) there
are 2 items, (a) & (b). should we give ONE solution that addresses
both
restrictions or should we give TWO different solutions, each one for one
of the
two restrictions ?
TWO
2) is
"round" means one clock tick ?
YES
3) you
mention the technique from "last on the ring". i've solved the (a)
problem
without any special trick so to what trick do you refer ? is it the
trick of
sending messages with different delayes so that when they reach a node
at the
same round it means something ?
do we
have to use the trick or is it OK without it ?
I
DONT KNOW WHAT YOU ARE TALKING ABOUT.
YOU HAVE TO SOLVE IT
ONE
WAY OR THE OTHER>
4) you
say that "the lights should be lighted at the same round". should all
the
lights be turned on at the same clock tick ? for how long (how many ticks) ?
ALL
AT LIGHT AT THE SAME CLOCK TICK, FOREVER>
hi
another
question regarding Q3:
in q3 (a) do
I have to give a proof similar to the one we got in the consensus
or I can
prove it otherwise (I want to try proving that if there is a fifo
implementation then there is a 2-consensus solution).
[Yehuda Afek] Either way. Just make sure
you have a complete proof.
Ex2 -
We proved in
homeworks that there is no orientation
algorithm for
even length rings and not as you wrote
"rings of
any size".
Is there
orientation algorithm for odd length rings ?
A: No reply.
a. What is the
meaning of the symmetry breaking marking ?
Is
it a recommandation for the algorithm?
Is
it obligation for it?
Does it take the "coin" role when the alg. cannot choose?
A: Meaning, on each link one end of the
link is marked as "head" while
the other as
"tail", or if you want, one is marked "red" and the other
end
"blue". A
processor can check its interface to each incident link and see
whether it is on that end
or the other of the corresponding incident link.
question
4
-------------
1) we
need to build a n-process one-time Test&Set object from a 2-process one-
time
Test&Set objects.
are the
registers from which we build (2-process one-time) of 1 bit width or of
any width
we want. a wider register will allow us to easily create counters,
etc.
A: This question 5, since I did not
specify the size of the r/w register in quetion
5B,
you may use any size but the smaller you can do it with the better it is.
2) in the
beggining of page 3 (the line just below Figure 1) says:
"two write operations, or one read
operation".
is this a
mistake or is it correct (about 2 write but only one read).
A: Now you are on question 4: This is not a mistake.
3) is the
Constant number of operations on the "bounded use bits" register is
known in
advance (when designing the algorithm) ?
A: Yes, say it is k.
4) is the
bounded number includes both read & write operations or do we need to
count
each operation on its own.
A; as you wish
5) in 5.b
you ask "fixed number of one use bits". how can this number be fixed
for any
bound when the least we need is a counter to count operations ?
or maybe
it is fixed in the sende that it the number of bits is of proportions
of the
bound ?
A: I dont know what you need and what you
dont need. Try to think and read
it again.