# News feed

### Log in to your course web

You are not logged in KTH, so we cannot customize the content.

In the News feed, you find updates for pages, schedule and posts from teachers (when aimed also at earlier registered students).

May 2016
Event Omtenta, 8 June 2016 09:00
Changed by scheduling staff 13 May 2016
Show more similar (1)
Event Omtenta, 10 June 2015 08:00
Changed by scheduling staff 25 May 2015
January 2014
Teacher Seif Haridi posted 23 January 2014

March 2013
Assistant Niklas Ekström posted 27 February 2013
commented 6 March 2013

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?

Assistant commented 6 March 2013

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.

commented 7 March 2013

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?

Assistant commented 8 March 2013

Hi Mahboobeh and all,

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

commented 9 March 2013

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?

One user removed his/her comment
commented 10 March 2013

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.

commented 10 March 2013

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?

Assistant commented 11 March 2013

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_conjunctionhttp://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.

commented 12 March 2013

Hi,

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

Assistant commented 12 March 2013

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

commented 12 March 2013

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!

commented 12 March 2013

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?

commented 13 March 2013

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

Assistant commented 13 March 2013

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.

commented 13 March 2013

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!

commented 13 March 2013

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!

commented 13 March 2013

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)

commented 13 March 2013

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?

Assistant commented 13 March 2013

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.

Teacher Seif Haridi posted 6 March 2013

Assistant Niklas Ekström posted 1 March 2013

February 2013
Assistant Niklas Ekström posted 19 February 2013
Assistant Niklas Ekström edited 19 February 2013

I updated the video lectures page, http://www.ict.kth.se/courses/ID2203/video_lectures.html, with the slides that were in the classroom lecture today but that are not in the video lecture.

It is highly recommended that everyone read pages 203-216 in the book (the abstract of ch. 5, and ch. 5.1, 5.2).

As you might have seen there is no video available for lecture 10, which is about Paxos, which will be held tomorrow morning. The slides for lecture 10 are available on the video lectures page though.

Assistant Niklas Ekström edited 19 February 2013

I updated the video lectures page, http://www.ict.kth.se/courses/ID2203/video_lectures.html with the slides that were in the classroom lecture today but that are not in the video lecture.

It is highly recommended that everyone read pages 203-216 in the book (the abstract of ch. 5, and ch. 5.1, 5.2).

As you might have seen there is no video available for lecture 10, which is about Paxos, which will be held tomorrow morning. The slides for lecture 10 are available on the video lectures page though.

Assistant Niklas Ekström posted 4 February 2013
commented 4 February 2013

So please change this also!!!

Assistant commented 5 February 2013

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

January 2013
Jiawei Zhang posted 17 January 2013

Jiawei Zhang tagged with Partner. 17 January 2013

commented 31 January 2013

Borrowing your thread.

I'm looking for a lab partner as well. You can email me at yuris@kth.se

Thank you!

Teacher Seif Haridi posted 25 January 2013