Nyhetsflöde

Hi Niklas,
I have a question about the Exam of May 2011, Part I, Question 1. 
b) is incorrect because Omega is reducible to any FD (that implements consensus), but not the other way around
c) is incorrect. Are they equivalent?
a) should be incorrect, since Omega is equivalent to Eventually Strong detector, so Omega is reducible to P (but not the other way around)
d) should also be incorrect for the same reason as a). Omega is equivalent to Eventually Strong detector, so Omega is reducible to Eventual P (but not the other way around) 

What is the correct aswer? What am I doing wrong?

Hi Gerard and all,

You are correct in that all of the options are false.

The text for the question is perhaps a bit misleading, but if you read on the first page of the exam it says that there can be zero or more correct answers on the multiple-choice questions.

hi

question number 3 in 2010-04-17 has the same options but we have to choose one or more correct answers! can we consider it as a mistake in that exam? 

Hi Mahboobeh and all,

Yes good catch, that question is indeed wrongly formulated, since all of the statements are false.

Hi Niklas,

about question 3 in the exam 2011/03/17. The question is about Paxos.
I think that (b) and (d) are false, and (a) is true.
But is (c) true? 

option a is false: you can see an example of execution in paxos lecture slide 34, p1  accepted different values (red and yellow). according to the conditions, Acceptors only check the timestemp and do not care about the value.

option c is also false since safety properties (integrity, uniform agreement, and validity) are satisfied by algorithm it self. Omega only ensure termination property, refer to slide 30. on the other hand you can not satisfy safety property eventually. Once you violate safety it can never be corrected eventualy.

therefore I think none of the options are correct.

Hi Niklas,
I have a question about the Exam of March 2010, Part I, Question 3. 

 3. Which one of the following statements is correct: 
(a) Every property is a safety property and, simultaneously, a liveness property.
(b) Every property is either a safety property, or, exclusively, a liveness property, never
both.
(c) Every property is equivalent to a union of a safety property and a liveness property.
(d) None of the others. 

The answer given in the Solutions-ID2203-March2010.txt is D, why C is not correct?

what I can find in the lecture:

“Any [property] can be expressed as the conjunction of a safety property and a liveness property”
Alpern & Schneider, Inf.Proc.Letters 1985

To this question, dose the description of "every property" lead C to false?

Gerard & Mahboobeh: Mahboobeh is correct, all of the options are false.

Jiawei: The information you found is the correct one to look to for this question. Look here for the difference between conjunction and disjunction: http://en.wikipedia.org/wiki/Logical_conjunction, http://en.wikipedia.org/wiki/Logical_disjunction

The reason why c is false is because a conjunction (intersection) implies that both the safety property and the liveness property must hold for the execution, while a disjunction (union) only requires that one of the properties hold for the execution.

Hi,

  Is there any part of the course lectures that is excluded from the exam?

Zaid, at the last lecture Seif talked about what will be included in the exam. The slides are available here: http://www.ict.kth.se/courses/ID2203/material/course-summary.pdf

Hello. While going through some questions I found this question:

In a fail-stop model, can we determine a priori a time period such that, whenever a process crashes, all correct processes suspect this process to have crashed after this period?

And the solution:

The answer is no, because the perfect failure detector only ensures that processes that crash are eventually detected, but there is no bound on the time it takes for these crashes to be detected. This demonstrates a fundamental difference between algorithms assuming a synchronous system and algorithms assuming a perfect failure detector (fail-stop model). In a precise sense, a synchronous model is strictly stronger.

What I understand from the answer is that a fail-stop model assumes the possibility of a perfect failure detector without assuming the system syncrhronous. How is that possible? I mean, is it possible to implement a perfect failure detector in a non synchronous system? 

Beside that, in the correction of the exam of March 2008, the first reasoning question the answer establishes a direct relationship between a fail-stop model and a syncrhonous system: 

fail-stop (synchronous) (0.75p)

{ crash-stop process model

{ perfect links

{ perfect failure detector (P)

So in my opinion there is some contradiction there and I would really appreciate if somebody could help me to clarify this. Thank you very much!

Hi Niklas,
I have a question about the Exam of March 2008, Part I, Question 8.

8. Which statements are true about Abortable Consensus: 1.5p
(a) Abortable Consensus can be implemented in the fail-noisy model by as-
suming a majority of correct processes
(b) Abortable Consensus can be implemented in the fail-silent model by
assuming a majority of correct processes
(c) Abortable Consensus can be implemented in the fail-silent model by assuming an
eventual leader detector
(d) Abortable Consensus can be implemented in the fail-noisy model by assuming an
eventual leader detector

The answer is (a)(b)

fail-noisy abstration is partially synchronous system, in which Eventually Perfect Failure Detector can be implemented, so as Eventual Leader Election. 

With the assumption of majority of correct processes, A is correct.

fail-silent abstration is asynchronous system, in which Eventually Perfect Failure Detector cannot be implemented, so Eventual Leader Election cannot be implemented.

In Abortable Consensus, we need  Eventual Leader Election, why B is correct?

did anybody solve the exams for march 2012 and march 2011. would be grateful if anybody could share the solutions for mcqs so that i can compare them to mine

Oriol: I think you should think of those models (fail-stop model vs. synchronous system) in a more abstract way. Certainly you need some bounds on communication and processing speeds to implement the perfect failure detector abstraction in a real system, but that isn't a strict requirement of the fail-stop model.

Jiawei: We haven't covered Abortable Consensus in the course this year. Abortable Consensus was used in the previous version of the course book, but it has been removed in this version and is replaced with Epoch Consensus instead. Abortable Consensus is a primitive used to implement Uniform Consensus, and does not use an eventual leader detector. Have a look at chapter 5.3.3 in the book where the Read/Write Epoch Consensus algorithm is implemented in the fail-silent model.

Hi Niklas,

I'm not sure about the answers of two questions from the exam of March 2011 Part 1.

Question 3: I think that none of the statements are correct.

Question 4: I think a, b and c are correct and d is not because it doesn't guarantee that correct nodes deliver the decide.

Is this correct and if not why?

Thank you!

Hi Niklas,

I have a question about Exam of May 2011, Part I, Question 1. You have already confirmed that all of the answers are false but is it possible to explain why option c (Consensus is strictly weaker than) is false?

 Thanks!

Hi, Niklas,

Abortable Consensus is included in Course Summary 22/34, and the whole lecture 10 talks about it (10-paxos-consensus.pdf) as well. 

What do you mean by "We haven't covered Abortable Consensus in the course this year." ?

I find this in course-summary.pdf 22/34 which is also included in lecture 10:

Paxos
Elect a single proposer using Ω
      Proposer imposes its proposal to everyone
      Everyone decides
Problem with Ω
      Several nodes might initially be proposers (contention)
Solution is Abortable Consensus
Single node attempts to impose its proposal
Might abort if there is contention (safety)
Ω ensures eventually 1 proposer succeeds (liveness)

Sorry, the last post is not completed.

To continue..

Solution is Abortable Consensus
Single node attempts to impose its proposal
Might abort if there is contention (safety)
Ω ensures eventually 1 proposer succeeds (liveness)

We can see Eventual Leader Election is needed in Abortable Consensus.

Where did I make a mistake?

Steffen: You are correct about question 3, all of the statements are false. For question 4, if you look at slide 33 of http://www.ict.kth.se/courses/ID2203/material/11-Epoch-consensus.pdf you see that TOB also has the properties of reliable broadcast, so TOB should be fine too. However, using TOB seems like overkill since TOB is equivalent to consensus on its own.

Theofilos: From page 12 of http://www.ict.kth.se/courses/ID2203/material/Lecture_4._Unit_9._Relations_between_failure_detectors.pdf you know that consensus is reducible to omega, so the question is if omega is reducible to consensus. If you have consensus, I believe (I haven't checked this thoroughly though) that you can implement omega by every process proposing it's own pid for consensus, and everyone suspects all processes except for the process whose pid is decided (keep proposing forever using increasing instance numbers). So it seems that consensus is not weaker than omega.

Jiawei: Yes you are right, disregard the part where I said that we haven't covered Abortable Consensus in the course. Sorry about that. I should have said only that it is not covered in the book. Instead of me trying to explain here how Abortable Consensus works I suggest that you read chapter 5.3 in the book, and especially chapter 5.3.3. I think that if you do that, you will understand the answer to your question.

So please change this also!!!

Just repeating that tomorrow Wednesday is lecture, and the presentation of the first programming assignment is on Thursday at 13:00 instead.