Fast Secure and Reliable Coded Computing

Module Number: CIT4330003

Duration: 1 Semester

Occurence: Winter Semester

Language: English

Number of ECTS: 5

Staff

Professor in charge: Antonia Wachter-Zeh

Amount of work

Contact hours: 60

Self-study hours: 90

Total: 150

Description of Achievement and Assessment Methods

The students would be assessed through a semester-long group-project consisting of three students, and a written exam. The project is divided into three phases: In phase 1, the students choose a paper from a collection of suggested papers, read it and choose one of them ("student A") to present it. The duration of the presentation is expected to be between 15 to 25 minutes depending on the number of groups. In phase 2, the students implement (in a programming language of their choice) the algorithm introduced in the chosen paper. "Student B" explains their observations in a poster, while the other two roam around and ask about the posters of others. The poster should be of size A0. In phase 3, the students write a report about their own project summarizing their findings and summarizing the findings of two projects of their peers. "Student C" drives the report-writing phase. The report should consist of 5 to 10 pages. A summary on good practices in writing and structuring a report and a poster will be given during the semester.

For fairness and to encourage all students to collaborate and give their best, the project grading is divided as follows: The grade of student A is equal to 0.5*(group grade for presentation) + 0.25*(group grade for poster) + 0.25*(group grade for re the report). Students B and C are graded in a similar fashion with the highest weight corresponding to their main task.

In case the total number of students is not a multiple of three, groups of 4 students will be formed. Phase 1 for those groups will consist of reading two papers. The additional student presents the second paper. The grading will be of the form 0.4*(group grade for first presentation) + 0.2*(group grade for second presentation) + 0.2*(group grade for poster) + 0.2*(group grade for re the report). The 0.4 corresponds to the main task of the student.

The written exam (duration 60 mins) will consist of problems covering the topics explained by the lecturer in class.
The final grade for each student is equal to 2/3*(project grade) + 1/3*(exam grade).

Exam retake is only allowed for the written exam. To make up for the project, students should participate in the whole project phase again next semester.

Prerequisites (recommended)

Basic knowledge of mathematics, e.g., linear algebra, calculus and probability theory
Basic knowledge of a programming language, e.g., MATLAB or python
The course "Channel Coding" is recommended

Intended Learning Outcomes

At the end of this course, the students are able to:
- Identify the challenges of modern distributed computing systems and tackle them using coding theory
- Analyze and assess the privacy and the performance guarantees of coding theoretic methods applied to distributed computing
- Manipulate the fundamental secret sharing tool and be able to apply it in several applications to private distributed systems
- Understand the basics of machine learning algorithms
- Implement through programming languages algorithms explained in a research paper, produce their own observations and analyze their findings
- Prepare and present a poster (or a paper) within the standards of international conferences/workshop

Content

This course covers the coding-theoretic tools behind speeding up distributed computing. In addition, data privacy being of crucial importance, this course includes a deep understanding of the main tool behind information-theoretic privacy: secret sharing. Several applications of secret sharing and coding theoretic tools in modern distributed systems and distributed machine learning are then explained together with the impact brought by applying those tools.

More precisely, the course covers the following topics
- Coding to ensure information-theoretic privacy through secret sharing.
- Communication efficient secret sharing: a modification of secret sharing to better suit modern distributed systems
- Basic probability theory such as ordered statistics used to analyze the performance of different techniques used in coding for distributed systems
- Coding for private and fast distributed matrix multiplication, based on secret sharing schemes. Several state-of-the-art techniques will be explained in detail and their performance will be analyzed
- Basics of machine learning algorithms: gradient descent, stochastic gradient descent, linear and logistic regression
- Fast distributed gradient descent with and without coding theory

Teaching and Learning Methods

Lectures: The lecturer uses slides and the blackboard (or an iPad) to explain the fundamental theoretical concepts. Lectures are designed to be interactive and to encourage the students to ask questions and initiate discussions with the lecturer and each other.

Tutorials: The lecturer, or teaching assistants, solve concrete problems to simplify the understanding of the theoretical content and help the students better understand the material.

Students’ presentations: Each group of three students nominates one of them to present a paper of their choice. The paper is recent research on topics discussed in class. (Groups of four students nominate two students, each presents a paper)

Poster session: A workshop-style session in which each group of three students nominate one of them to present a poster. The others would go around and ask questions about other posters. This session is designed to introduce the students to environments of international scientific events.

Throughout the semester, the students can ask for question-and-answer sessions and/or lab sessions in which the lecturers and teaching assistants come to answer the students' questions about the topics discussed in class. In lab sessions, the teaching assistants provide help to further their progress in the programming tasks.

Reading List

A collection of papers will be given to the students for further reading.

All slides and notes written in class will be passed to students.