T-79.4001 Seminar on Theoretical Computer Science (3 cr) V

Spring 2007 -- Distributed Computation

This seminar, which is part of the major studies in Theoretical Computer Science, deals with annually varying topics of current interest in the field. The Spring 2007 instantiation of the seminar will be concerned with fundamental techniques in the design and analysis of algorithms for distributed computation.

The seminar T-79.4001 replaces the former courses/seminars T-79.192 Special Course on Theoretical Computer Science and T-79.194 Seminar on Theoretical Computer Science .

[Current] [General] [Arrangements] [Material] [Schedule]

Previous years: [Spring 2006]

Current

• [1 Jun 2007] Grade sheets (in Finnish, pdf) available here and here.
• [26 Apr 2007] The seminar for this Spring is over; many thanks for your active participation. Remember to provide feedback on the course via the department's course feedback system. The electronic questionnaires were opened on Wed 25 Apr and will close on Wed 23 May.
• [26 Feb 2007] By popular request, Ilari Nieminen has made the source code of his slides available for other speakers interested in using the LaTeX Beamer presentation class.
• [7 Jan 2007] First seminar session Wed 24 Jan 12-14, room TB353.

General

• Time, place: Wednesdays 12-14, seminar room TB353. First session Wed 24 Jan.
• Coordinator: Prof. Pekka Orponen, room TA348.
• Registration by TOPI.
• Prerequisites: T-79.1001/1002/T-79.148 Introduction to Theoretical Computer Science and T-106.1220/1223/T-106.250/253 Data Structures and Algorithms. Familiarity with telecommunications technology (e.g. T-110.2100/T-110.300) and algorithm design (T-106.4100/T-106.410) an asset.
• Credits: Seminar presentation plus archivable slides 3 cr. In addition, feedback must be provided for the speakers of at least three sessions using the respective electronic forms. (Forms available via the seminar schedule below.) Feedback forms for presentations in a given week must be completed by the beginning of the session on the following week.

Arrangements

• The presenter's archivable slides (preferably in PDF) will be linked to the schedule below by the coordinator.

Seminar material

N. Santoro: Design and Analysis of Distributed Algorithms (J. Wiley & Sons, 2006).

One copy of the book will be available for short-term loan and another for reading-room use in the DCSE library.

Schedule

• 24 Jan: Opening, overview, handing out assigments (P.O.)
• 31 Jan: No seminar.
• 7 Feb: Fundamentals
  1. Juhani Peltonen: Basic model and formalism (Sec. 1)
     Presentation: slides, feedback form
  2. Jukka Viinamäki: Fundamental problems (Secs. 2.1-2.4)
     Presentation: slides, feedback form
• 14 Feb: Tree-like networks
  1. Toni Kylmälä: Constructing a spanning tree (Sec. 2.5)
     Presentation: slides, feedback form
  2. Kim Blomqvist: Computations in trees (Sec. 2.6)
     Presentation: slides, feedback form
• 21 Feb: Election 1
  1. Ilari Nieminen: Election in trees and rings (Secs. 3.1-3.3.3)
     Presentation: slides (pdf, source), feedback form
  2. Eero Häkkinen: Advanced election techniques in rings (Secs. 3.3.4-3.3.8)
     Presentation: slides, feedback form
• 28 Feb: Election 2
  1. Heikki Kallasjoki: Election in mesh, cube and complete networks (Secs. 3.4-3.7)
     Presentation: slides, feedback form
  2. Risto Hakala: Universal election protocols (Sec. 3.8)
     Presentation: slides, feedback form
• 7 Mar: Exam week; no seminar.
• 14 Mar: Routing
  1. Panu Pitkämäki: Shortest path routing (Secs. 4.1-4.2.5)
     Presentation: slides, feedback form
  2. Tuomas Launiainen: Advanced routing topics (Secs. 4.2.6-4.4)
     Presentation: slides, feedback form
• 21 Mar: Synchronous computation
  1. Aleksi Hänninen: Basic techniques (Secs. 6.1-6.2)
     Presentation: slides, feedback form
  2. Pekka Orponen: Advanced techniques (Secs. 6.3-6.4)
     Presentation: slides, feedback form
• 28 Mar: Fault tolerance 1
  1. N.N.: Impact of faults and failures (Secs. 7.1-7.2)
     Presentation: slides, feedback form
  2. Jani Lampinen: Localised failures: synchrony (Sec. 7.3)
     Presentation: slides, feedback form
• 4 Apr: Fault tolerance 2
  1. Riku Saikkonen: Localised failures: randomisation and other techniques (Secs. 7.4-7.7)
     Presentation: slides, feedback form
  2. Tero Pietiläinen: Ubiquitous faults (Sec. 7.8)
     Presentation: slides, feedback form
• 11 Apr: Easter vacation; no seminar.
• 18 Apr: Distributed set operations
  1. Toni Kylmälä: Selection (Secs. 5.1-5.2)
     Presentation: slides, feedback form
  2. Eero Häkkinen: Sorting and other operations (Secs. 5.3-5.4)
     Presentation: slides, feedback form