Academic year 2014-15

Advanced Distributed Systems

Degree:	Code:	Type:
Bachelor's Degree in Computer Science	23106	Optional subject
Bachelor's Degree in Telematics Engineering	23110	Optional subject
Bachelor's Degree in Audiovisual Systems Engineering	23114	Optional subject

 

ECTS credits:

4

Workload:

100 hours

Trimester:

2nd

 

Department:	Dept. of Information and Communication Technologies
Coordinator:	Jorge Lobo
Teaching staff:	Jorge Lobo Windy Rankothge
Language:	English
Timetable:
Building:

 

Introduction

We are witnessing an explosion of devices that can connect us to each other and connect among themselves. This has created many opportunities to develop distributed network applications. These are applications where data and computation are distributed among many devices and where, in principle, all the devices send and receive data and benefit from the computation of the group. Complementary to this evolution we are also seeing how many computing services are moving to cloud environments. These are computational environments where computation is distributed into, many times, tens of thousands of computers to serve millions of users. Hence, it is becoming essential for any computer professional to have a good understanding of what it means to program in a distributed environment.

The goals of this course are to introduce students to some of the core foudational concepts in distributed computing and study different distributed algorithms.  The emphasis will be on algorithms in which computational nodes communicate  asynchronously exchanging messages. There will be lectures where algorithms will be introduced  and student will able to solidify the concepts through several small and medium programming  projects and exercises.

 

Prerequisites

Students must have knowledge of basic graph concepts such as the ones covered in “Linear Algebra and Discrete Mathematics”, understanding of asymptotic complexity analysis notation as  is covered in “Programming Fundamentals”, as well as programming skills as the ones covered in “Data Structures and Algorithms” and in “Development of Distributed Applications” or “Protocols and Distributed Applications”.

 

Associated competences

Cross-disciplinary competences	Specific competences
Instrumental Capacity to analyze problems Capacity for abstraction Organization and planning Interpersonal Comprehension of existing solutions or already built by others Collaborative work in software development Systematic Creation of well-structured solutions Re-use of known techniques to solve new problems Creation of new ideas	An understanding of distributed computational models and algorithms. Capacity to design new distributed algorithms. Capacity to program such algorithms in a distributed computing environment. Ability to understand how these algorithms can be used for writing reliable and fault tolerant systems. Ability to understand how these algorithms can be used to parallelize computation.

 

Assessment

 

 

Contents

1. Preliminaries

• Motivation: Routing/Broadcasting/Multicasting/Skype/File Sharing, Fault tolerance, ZooKeeper, Hadoop - NLP

• Our computational model: General overview of distributed computation, Asynchronous computational model using message passing, Clocks, Safety and liveness

• Notions of computational complexity in distributed algorithms

2. Waves

3. Deadlock/Termination detection

4. Leader elections

5. Spanning trees

6. Anonymous networks

7. Synchronization

8. Distributed Hash tables

9. MapReduce

 

Methodology

 

 

Resources

The course will mostly follow the book “Distributed Algorithms, An Intuitive Approach” by Wan Fokkink.

Other references:

Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. 2003. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw. 11, 1 (February 2003), 17-32.

Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM 51, 1 (January 2008), 107-113.