Theory of (Distributed) Computation
Seminar - Winter Term 2014/15
Fabian Kuhn
Seminar topic
The underlying theme of all papers in this seminar is "distributed algorithms". How to calculate a certain structure among individually operating entities, how to model communication in large-scale distributed systems, how to speed up, stabilize or secure tasks if multiple entities are available, etc.
Administrative information
In order to get a grade, students have to study and later present the content of a specific paper from the field of distributed computing; see the list below. The seminar will be held as a block seminar and attendance is mandatory. Your slides and talk should be in English. The presentation should last 30 minutes plus about 15 minutes of discussion.
Schedule of the Seminar Day
The seminar will be held in room 052-02-017 on January 23, 2015, 9:30 a.m - 04.40 p.m. (approx.)
| 09:30 a.m. | Talk 1: Christoph Gissler presenting Fast Distributed Construction of Small k-Dominating Sets and Applications by Shay Kutten, David Peleg |
| 10:20 a.m. | Talk 2: Mohsin Ali presenting Distributed Verification and Hardness of Distributed Approximation by Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer |
| 11:10 a.m. | Talk 3: Layla Franke presenting A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs by Baswana, Sandeep Sen |
| noon | Lunchbreak |
| 01:00 p.m. | Talk 4: Pawel Ranoszek presenting Dynamic Analysis of the Arrow Distributed Protocol by Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, Roger Wattenhofer |
| 01:50 p.m. | Talk 5: Pia Petrizio presenting Stone Age Distributed Computing by Yuval Emek, Jasmin Smula, Roger Wattenhofer |
| 02:40 p.m. | Break |
| 03:00 p.m. | Talk 6: Christian Marquardt presenting Broadcasting in dynamic radio networks by Andrea E.F. Clementi, Angelo Monti, Francesco Pasquale, Riccardo Silvestri |
| 03:50 p.m. | Talk 7: Ivo Enke presenting Radio Network Lower Bounds Made Easy by Calvin Newport |
Please be on time (for every talk)!
We will meet the first time in the 2nd week of the semester, on Thursday, 30 October, at 12:15, also in room 106-00-015.
Requirements
The course is mainly directed towards Master students and 3rd year Bachelor students (and interested PhD students) of computer science or mathematics. There are no specific requirements, but students should be interested in mathematical and algorithmic questions and basic mathematical maturity is expected.
Report
You have to write a report of about 4-8 pages. It should contain a summary of the content of the paper, the core ideas and notes you want your audience to have access to during your presentation (e.g., definitions or a recurring lemma), so that there is no need to swap back and forth in your slides.
Timeline
We require the following steps to ensure a high quality of the talks and hope that these will result in a good grade for you:
- Until the November 14: Decide for a paper.
- Until the beginning of December: first meeting with your mentor (you need to read the assigned literature before this meeting).
- Before Christmas: meet your mentor to discuss the structure of your talk.
- At least 1 week before your talk: discuss your (complete) slides with your mentor, so that he/she can give feedback.
- One day before the presentation date: hand in your report and an electronic copy of your slides
- 2015, January 23: Present your slides
Papers
- What Can Be Computed Locally - Naor, Stockmeyer (Contact person: Yannic)
A problem can be solved locally if a node in a communication network can decide about its output on the basis of its c-hop view, where c is a constant independent from the size of the network. Two of the main results are:- There are non-trivial problems that can be solved locally.
- There is a variant of the dining philosophers problem that can be solved locally.
- (TAKEN) Network Decomposition and Locality in Distributed Computation - Awerbuch, Luby, Goldberg, Plotkin (Student: Manuel Schneider, Contact person: Yannic)
This paper introduces a method to efficiently partition the sets of nodes of a given graph into clusters with the following properties- Each cluster has low diameter
- The clustergraph can be partitioned into few independent sets (there is no connection between two clusters which belong to the same independent set)
- (TAKEN)
Low diameter graph decompositions - Linial, Saks
(Student: Marcel Rücker, Contact person: Yannic)
Linial and Saks improve the network decomposition of Awerbuch, Luby, Goldberg and Plotkin with the help of randomization. They also show that there are graphs which cannot be decomposed in a better way. - (TAKEN) Radio Network Lower Bounds Made Easy - Calvin Newport (Student: Ivo Enke, Contact person: Sebastian)
In this paper a multitude of lower bounds for solving problems in a distributed setting are proven by reduction from a simple probabilistic hitting game for which there is a known lower bound. Before this paper, the same or worse lower bounds for these problems have been proven over many pages, while here it all comes down to the right reduction technique, which often enough fits into a single page. - (TAKEN) Stone Age Distributed Computing - Yuval Emek, Jasmin Smula, Roger Wattenhofer (Student: Pia Petrizio, Contact person: Sebastian)
In this paper the authors look at a new model for distributed computing which puts major limitations upon communication/computation/memory power of devices in a network. They solve important problems in that model despite those limitations. The model is motivated from biology, as it is known that cells do calculate and solve some typical problems from computer science, while it is not fully understood how they can do so with their limited capabilities. - (TAKEN) A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs - Baswana, Sandeep Sen (Student: Layla Franke, Contact person: Anisur)
This is a classical paper on computing a spanner of a graph. A spanner is a (sparse) subgraph of a given graph that approximately preserves the distance between all pairs of vertices. Computing a spanner of minimum number of edges is an well-motivated problem and has lots of applications in computer science including distributed systems and communication networks. While their algorithm is mainly for the centralized setting, the local approach of their algorithm also leads to simple and efficient algorithms for computing spanners in distributed network model and in other important computational environments such as parallel, and external memory. - (TAKEN)
Fast Distributed Construction of Small k-Dominating Sets and
Applications - Shay Kutten, David Peleg (Student:
Christoph Gissler, Contact person: Fabian)
The main result is an efficient distributed construction of an MST (minimun weighted spanning tree). - (TAKEN)
Broadcasting in unreliable radio networks - Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, Andrea Richa (Student:
Janosch Pelzer, Contact person: Fabian)
This paper considers broadcasting (an opration in which a single processor as a source sends a message to all other processors) in radio networks where the set of communication links includes two types of links. One type is reliable links which always deliver messages and induce a connected graph. The other one is unreliable links which sometimes fail to deliver messages and are changed from time to time. - (TAKEN) Distributed Verification and Hardness of Distributed Approximation - Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer (Student: Mohsin Ali, Contact person: Anisur)
This paper gives almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and s-t cut verification etc. Then they derive strong lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree, shortest paths, and minimum cut etc. For the lower bound proofs, they derive an interesting connection between communication complexity and distributed computing which could be useful in establishing the time complexity of exact and approximate distributed computation of many problems. - (TAKEN) Dynamic Analysis of the Arrow Distributed Protocol - Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, Roger Wattenhofer (Student: Pawel Ranoszek, Contact person: Hamid)
Arrow is a distributed queuing protocol that allows the processors of a network (on a pre-constructed spanning tree) to concurrently and asynchronously request for acceessing (reading/writing) a shared object in such a way that it guarantees mutual excelusion. This paper provides a competitive analysis of Arrow where the processors concurrently and asynchronously issue the requests. - (TAKEN) Broadcasting in dynamic radio networks - Andrea E.F. Clementi, Angelo Monti, Francesco Pasquale, Riccardo Silvestri (Student: Christian Marquardt, Contact person: Hamid)
This paper presents a study of broadcasting (an opration in which a single processor as a source sends a message to all other processors) in dynamic radio networks. In this work, dynamic network is modeled by means of adversaries (with different power) where the set of processors is fixed and the set of communication links changes time to time, in contrast to the static networks, where all links are supposed to be reliable.
Your talk
Presentation
Above we have a series of suggested papers which will be assigned on a first-come-first-serve basis. All presentations should cover the motivation for the problem as well as some technical parts of the paper in detail. Assume that the other participants know nothing about the subject. You are not supposed to present the whole paper, but just the aspects that were most intriguing to you. We encourage you to deviate from the logical structure of the paper and strive for the most lucid presentation of the topic. Furthermore you may want to have a look at how to design slides (e.g. link 1, link 2, link 3 (chapter 5)).
Evaluation
Below are the criteria according to which we judge a good presentation.
Motivated Talk
The speaker was motivated and kept the audience interested throughout the presentation.
Clearly Explained
The speaker made the material clear and comprehensible.
Knowledge Transfer
The (awake and participating) audience learned something.
Difficulty
The presentation was (too) difficult, easy, or just right to follow.
Prior Knowledge
The speaker did not assume inappropriate prior knowledge.
Structure
The presentation had a clear concept and discernible structure.
Encouraged Participation
The speaker actively encouraged participation and successfully led the discussion.