Principles of Distributed Computing , lecture notes by Roger Wattenhofer.
Lectures were delivered by Sumathi and Billy. Reference: Chapters 1 and 2 of Peleg's book. The agreement problem was defined and various lower bounds and impossibility results were discussed. The lower bound on the number of rounds required in a faulty synchronous network was taken from Attiya and Welch's book Chap 5.
- Parallel and Distributed Algorithms in P Systems?
- The Truth in the Light?
- Am Ende der Welt: Eine Reise durch Feuerland und Patagonien (German Edition).
- Echo of an Angry God.
The impossibility of agreement in asynchronous shared memory model and message passing mode were based on Lynch's book Chap My own handwritten notes are available, but use at your own risk. The randomized algorithm for byzantine agreement with access to a global coin was taken from Motwani and Raghavan Chap We discussed various distributed routing algorithms. We discussed various leader election algorithms on rings from Lynch's book, Chapter 3.
We discussed two algorithms for computing the Maximal Independant Set. Reference: notes by Wattenhofer Chap 7 and my own notes based on notes Pandurangan shared with me. We will complete this proof next week. The material is taken from Peleg's book Chap. While the world of static networks is fairly well-studied, our understanding of networks that change over time is limited. In a sense, we have already seen dynamism in the form of fault tolerance, but we are interested in understanding algorithms designed for networks that are perpetually changing.
We covered the entire chapter on dynamic networks in Wattenhofer's notes.
We began with a discussion on what constituted p2p networks in essence boiling down to networks that accomplish meaningful tasks despite the lack of a central authority. I must admit that this definition is a bit biased by my own interests. Furthermore, these are systems characterised by heavy node churn, i.
This means that we must design algorithms that can tolerate churn. In this context, we discussed some recent work that tackled the agreement problem in networks that experience very heavy churn. A copy of the paper that we mainly focussed on was sent to the course students via email. We saw a simple form of distributed sorting in which the network is an array of nodes v 1 , v 2 , Each node in the array starts with an input value.
We discussed a simple algorithm that sorts the values such that the node v i outputs the value with the i th rank. Perhaps more interestingly, we studied a lemma that simplified our analysis quite a bit by allowing us to focus only on binary input values. A sorting network takes n input wires, each with some value and outputs them in sorted order employing comparators to swap values on wires.
Distributed Algorithms | Computer Science
We discussed the Batcher sorting network and analyzed it, again making use of the convenient lemma. Assignment 1 due on March 20 at 11AM before class starts. This shall be useful to a wide variety of research topics from the theory of distributed algorithms to protocol design, e. Spring , Starting on April 2nd see the schedule below for details.
- CS Distributed Algorithms (Even ).
- Finanzvertrieb - die Chance deines Lebens: wie du erfolgreich durchstartest (German Edition).
- Flipside of the COIN: Israel’s Lebanese Incursion Between 1982 - 2000.
To sign up for the course email one of the course organizers. Workload and form: Each student is required to give two seminars about two of the course topics, see the schedule section below.
It is also possible that a team of two students gives four seminars. The seminar leader s are required to prepare the slides of their presentation by studying the appointed book sections. The bottom line is that taking responsibility of a seminar is taking responsibility of being a teacher for other course participants for that seminar topic, so please study the relevant book sections well and do not only depend on reading any external slides which are prepared by already expert teachers for their own use.
Additionally, each PhD student has to deeply study at least three papers, and to write a summary of each that is no less than one-page long. Below is a recommended papers list. By 15th of July , each PhD student has to email all his summaries to another PhD student who may come back with comments to the writer and perhaps have a pair discussion if necessary. The dealine to submit the summaries and the reviews is 15th of July, Consensus in the presence of partial synchrony.
An Introduction to Distributed Algorithms
ACM 35, 2 April , Michael J. Fischer, Nancy A. Lynch, and Michael S. Impossibility of distributed consensus with one faulty process.