* [June 15, 2007 at 16:00] The [[Workshop Presentation]] schedule, time and location are now available.\n* [May 1, 2007 at 20:00] The 4th lecture is rescheduled from May 7 to May 14 (same day of the week, room and hours).\n* [March 7, 2007 at 14:00] The [[Second Assignment]] is accounted.\n* [February 2, 2007 at 14:00] The [[First Assignment]] is accounted.\n* [January 17, 2007 at 11:51] The Web-page is up for the 2007 spring edition of the course.
The course lectures follow the author's text book [[slides|http://www.cs.bgu.ac.il/~dolev/book/slides.html]] \n\n|!Date |!Time |!Location |!Topic |\n|Feb. 5 | 10:00 | to be announced|Introduction: [[Definitions, Techniques, and Paradigms|http://www.cs.bgu.ac.il/~dolev/book/c2.ppt]] |\n|Mar. 5 | 10:00 | to be announced|[[Motivating Self-Stabilization|http://www.cs.bgu.ac.il/~dolev/book/c3.ppt]] |\n|Apr. 16 | 10:00 | to be announced|[[Self-Stabilizing Algorithms for Model Conversions|http://www.cs.bgu.ac.il/~dolev/book/c4.ppt]] |\n|May 14 | 10:00 | to be announced|[[Convergence in the Presence of Faults|http://www.cs.bgu.ac.il/~dolev/book/c6.ppt]] |\n|June 4 | 10:00 | to be announced|[[Local Stabilization|http://www.cs.bgu.ac.il/~dolev/book/c7.ppt]] |\n|June 18 | 10:00 | to be announced|[[Workshop Presentation]] |\n
* The course text book: [[Shlomi Dolev, Self-Stabilization, MIT Press, March 2000.|http://www.cs.bgu.ac.il/~dolev/book/book.html]]\n* [[Edsger W. Dijkstra: Self-stabilizing systems in spite of distributed control. Commun. ACM
Announcements\nGeneral-Info.
Announcement date: Feb. 2nd\nDue date Mar. 5th\n\nWrite your answers using formal proofs and detailed explanations.\n\n* Question 1\nIn a uniform system, all processors are identical, i.e., processors are running the same algorithm and they have no unique id’s. Show that in a synchronous uniform ring, in which processes start in the same state, there is no deterministic algorithm for token passing.\n\n* Question 2\nConsider the broadcast problem: on an undirected graph, one node (the initiator) wishes to send a message m to all other nodes. Design a PIF algorithm for broadcast with acknowledgement. Use at most O(log |V |) memory for each processor, and prove it’s correctness. Please remember: in a PIF algorithm, the initiator should notify in a finite time only after all processes receive the message.\n\n* Question 3\nConsider an undirected Tree, T = (V,E). We call a node v in V a center if the maximal distance between it to any other node in the tree is minimal over all other nodes.\n1. Prove that there are at most two centers in a tree.\n2. Present an asynchronous algorithm, prove its correctness and analyze the message and the time complexity.\n3. Present a simple synchronous algorithm that finds the center(s) of the tree.\nProve its correctness, and analyze the message and the time complexity.\n
* Audience: All graduate and senior undergrads.\n* Course credit: One mandatory point for attending three (out of five) the [[Course Lectures]] and a [[Workshop Presentation]] presentation. An elective point for preparing five [[Homework Assignments]] of three questions.\n* Evaluation: The credit of the first mandatory point credit requires that the participant would attend at least three out of five lecture, present in the workshop in a satisfactory manner, and attend two third of the workshop's presentations. The credit of the second elective point requires that the participant would submit all assignment in a satisfactory manner. \n* Course responsible: [[Elad Michael Schiller]]\n
There are five homework assignments in the course. Please note that these are elective assignments. Students that are interested in the elective point should submit all assignment (with 65 percent correct answers). We do not allow assignment group submission.\n\n* [[First Assignment]]\n* [[Second Assignment]]\n* [[Third assignment (announcement date Apr. 16) ]]\n* [[Fourth assignment (announcement date May. 7) ]]\n* [[Fifth assignment (announcement date June. 4) ]]\n
[[Announcements]]\n[[General-Info.]]\n[[Course Lectures]]\n[[Workshop Presentation]]\n[[Homework Assignments]]\n[[Course Literature]]
Announcement date: Apr. 8th\nDue date May. 7th\n\nWrite your answers using formal proofs and detailed explanations.\n\n* Question 1\nIs there a leader election algorithm in a synchronous ring in which all but one processor\nhave the same identifier, where no bound on the ring size is known? Either give an\nalgorithm (prove correctness and analyze complexity) or prove an impossibility\nresult.\n\nDoes the answer changes for the asynchronous case?\n\n\n* Question 2\nDesign a PIF algorithm to broadcast (one initiator which sends one message)\nover a directed graph. The initiator must decide (and notify) after a finite amount\nof time, and only after all nodes receive the message.\n1. What are the minimal required properties from the network topology?\n2. Describe your algorithm, and prove correctness.\n3. What is the expected number of messages sent by the algorithm?\n\n[>img[A leader election algorithm in a synchronous and uniform system over a complete\ncommunication graph. |alg1.JPG][http://www.cs.chalmers.se/~elad/teaching/SelfStabSem/Alg1Big.JPG]]\n\n* Question 3\nConsider algorithm 1 for leader election in a synchronous uniform complete\ngraph shown in class.\n\nCan you enhance this algorithm so a leader will be chosen faster (on the\navarage)? Either provide an enhanced algorithm and analyze it’s convergance\ntime, or prove that the above algorithm provides the lower bound.
The objective of self-stabilization is for a distributed system that enters an illegitimate (e.g. erroneous or suboptimal) state to return to a legitimate state within a finite time without any external (e.g. human) intervention.\n\nAttaining self-stabilization is especially difficult in a distributed system such as a computer network. This was demonstrated in the classic paper by E.W. Dijkstra in 1974 that originated research on self-stabilization. The ability to recover without external intervention is very desirable in modern computer and telecommunications networks, since it would enable them to repair errors and return to normal operations on their own. Computers and networks can thus be made fault-tolerant. Hence, many years after the seminal paper of Dijkstra, this concept is gaining in importance as it presents an important foundation for self-managing computer systems and fault-tolerant systems.
A one/two points graduate course (Feb. to Jun. 2007)
Seminar on Self-Stabilization
All course participants are required to prepare and present a forty five minutes presentation. We devote a one day workshop-like meeting to present these lectures. The presentation topics can be either on one of the advance topic of the course that appear in the course text book, or on one academic publication within the area of self-stabilization. Please contact the course responsible for coordinating time and topic.\n\nHere is a tentative schedule of the workshop in room 5128:\n|!Date|!Time |!Name |!Topic |\n|June 18 | 10:00-11:00|Andreas Larsson|[[Self-Stabilizing Algorithms for Model Conversions|http://www.cs.bgu.ac.il/~dolev/book/c4.ppt]] |\n|June 18|11:00-12:00 |Daniel Cederman|[[Stabilizing Synchronizers: Converting Synchronous to Asynchronous Algorithms|http://www.cs.bgu.ac.il/~dolev/book/c4.5.ppt]] |\n|June 20 |10:00-11:00 |Phu H. Phung |[[Convergence in the Presence of Faults|http://www.cs.bgu.ac.il/~dolev/book/c6.ppt]]|\n|June 20|11:00-12:00 |Marcin Zalewski|Stabilization in Spite of Byzantine Faults and Superstabilization|\n|June 25 |10:00-11:00 |Daniel Hedin |[[Monitoring and Resetting|http://www.cs.bgu.ac.il/~dolev/book/c5.2.ppt]]||\n|June 25|10:00-12:00 |Philipp Rümmer |[[Error-Detection Codes and Repair|http://www.cs.bgu.ac.il/~dolev/book/slides.html]]|\n
Type the text for 'YourName'