Moses - Network Algorithms (6 LP)

Display language

To modulepage Generate PDF

Diese Modulbeschreibung gilt nicht im aktuellen Semester.

Die Modulbeschreibung gilt nur für den Zeitraum WS 2013/14 - SS 2019.

Module / Version:
#40589 / #1

Validity:
WS 2013/14 - SS 2019

Default display language:
English

Module title:
Network Algorithms (6 LP) (Network Algorithms)

Credits:
6

Responsible person:
Feldmann, Anja

Grading:
benotet

Type of exam:
Schriftliche Prüfung

Zugehörigkeit

Faculty:
Fakultät IV

Institute:
Institut für Telekommunikationssysteme

Area of expertise:
34331700 FG Intelligent Networks and Management of Distributed Systems (INET)

Prüfungsausschuss:
No information

Kontakt

Office:
No information

Contact person:
No information

E-mail address:
No information

Website:
No information

Learning Outcomes

Most modern computer systems are inherently distributed and networked: from multi-core computer architectures over wireless sensor systems and datacenters to peer-to-peer systems. Accordingly, network algorithms are needed to design and operate these computer systems in a scalable and robust way. The goal of this lecture is to provide the students with tools and techniques to reason about efficient network algorithms. The lecture is problem-oriented and structured into different fundamental princi-ples, such as Randomization, Decentralization, Indirection, etc. Each lecture will cover a different basic problem (such as Load Balancing, Medium Access, Symmetry Breaking, etc.) and will be self-contained. By the end of the lecture, the student will be able to develop her/his own network algorithms, and formally prove correctness as well as complexity guarantees (e.g., on the computational or message complexity). The students will also have a good understanding of when to apply which principle, i.e., where randomization can be useful and where not, or to which extent a distributed system should be decentralized. The students will also have a good idea of the different natures of today's networks. If time permits, we will also extend our discussion beyond computer networks and have an algorithmic look at social networks. This module is principally designed to impart: technical skills: 40x, method skills: 40x, system skills 10x, social skills 10x

Content

The lectures revolve around fundamental problems and design principles. A tentative outline of the main topics to be covered in the course are * Network Models and Distributed Systems * Robust Network Topology Design: Self-Stabilizing and Self-Optimizing Networks * Decentralization: why and how? Complexity Measures * Randomization: why and how? Basic Tools * Algorithms: Local Algorithms, Random Algorithms, Online Algorithms, Dynamic Programming * Network Algorithms for Leader Election, Coloring, Maximal Independent Sets, Medium Access * Resource Allocation and Embedding (e.g., energy, bandwidth, CPU) * Flow & Congestion Control, Routing * Social Networks: An Algorithmic Perspective

Module Components

Pflichtteil:

All Courses are mandatory.

Course Name	Type	Number	Cycle	Language	SWS	VZ
Network Algorithms	IV	0432 L 815	WiSe	No information	4

Workload and Credit Points

Network Algorithms (IV):

Workload description	Multiplier	Hours	Total
attendance lecture	15.0	2.0h	30.0h
attendance tutorial	15.0	2.0h	30.0h
preparation and rework of the lecture	15.0	3.0h	45.0h
preparation for the exam	1.0	15.0h	15.0h
solving exercises	15.0	4.0h	60.0h
			180.0h(~6 LP)

The Workload of the module sums up to 180.0 Hours. Therefore the module contains 6 Credits.

Description of Teaching and Learning Methods

* Common lecture * Exercises and/or programming assignments: to be issued weekly; half to be solved individually and half to be solved in groups of 2 (if the class has an odd number of participants then there will be a group of 3); to be graded by the instructor; solutions to be jointly discussed (by instructor + students) during the tutorials * English language for both the lecture and the tutorials

Requirements for participation and examination

Desirable prerequisites for participation in the courses:

Desirable - knowledge and qualifications equivalent to: * BINF-GL - MPGI1 Algorithmische und funktionale Lösung diskreter Probleme * BINF-GL - MPGI2 Algorithmen und Datenstrukturen im imperativen Stil * Network Protocols and Architectures * English language

Mandatory requirements for the module test application:

This module has no requirements.

Module completion

Grading

graded

Type of exam

Written exam

Language

English

Duration/Extent

No information

Duration of the Module

The following number of semesters is estimated for taking and completing the module:
1 Semester.

This module may be commenced in the following semesters:
Wintersemester.

Maximum Number of Participants

The maximum capacity of students is 30.

Registration Procedures

Registration for the course on ISIS. Registration for the complete module on QISPOS / registration office.

Recommended literature
David Peleg: Distributed Computing - A Locality-Sensitive Approach, SIAM 2000
Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005.

Assigned Degree Programs

Semester:

Zeige auch ausgelaufene Studiengänge und StuPOs

This module is used in the following Degree Programs (new System):

	Studiengang / StuPO	StuPOs	Verwendungen	Erste Verwendung	Letzte Verwendung
This module is not used in any degree program.

Students of other degrees can participate in this module without capacity testing.

Miscellaneous