The course focuses on the study of basic distributed algorithms, including both algorithms for multicore shared memory systems and algorithms for message-passing systems. On the basis of these two models, we will build a concrete collection of algorithms, which constitute the cornerstones of most distributed applications. Specifically, the goal of this course is to familiarize students with topics related to (1) basic techniques for designing and analyzing distributed algorithms for multicore and message-passing systems, (2) fundamental algorithms of distributed computing, (3) synchronization protocols, (4) shared data structures, (4) basic algorithms for collaborative communication, (5) basic timing concepts, (6) deadlock detection and recovery, (7) detection of termination, failures and other states in message passing systems. Students that complete the course successfully will have gained the basic background needed to work in any field touching upon distributed systems and applications.
The course consists of two parts. A detailed presentation of the material covered by each part is given below.
PART I - Multiprocessor Algorithms
Introduction - Synchronization
Difficulties encountered in achieving parallelism
Amdhal's law
Modeling a shared memory system
Fundamental properties and parameters
Mutual Exclusion & Locks
Basic mutual exclusion algorithms
Practice: Spin Locks and Contention
Combining Techniques
Hierarchical Approaches
Atomic Objects
Linearizability
Blocking and non-blocking progress conditions
Concurrent Data Structures
Concurrent Queues, Stacks, Lists
Concurrent Hash Tables
Concurrent Trees
Garbage Collection, Safe memory reclamation
Barriers
Applications
Barrier Implementations
PART II - Algorithms for Message-Passing Systems
Introduction, Basic Network Algorithms
Modeling a message-passing system
Broadcast, convergecast and other collective communication algorithms
Basic distributed graph algorithms
Leader Election
Leader election in rings
Leader election in general graphs
Network Resource Allocation
Mutual exclusion algorithms
General resource allocation
Logical Time and global states
Adding logical time to distributed algorithms
Consistent global snapshots
Detection of properties on Distributed Executions
Termination detection
Deadlock detection
Failure detection
Learning Outcomes
The aim of the course is to provide students with theoretical and practical training in the design, analysis and implementation of algorithms in modern distributed systems. Students, after successful completion of the course:
will be familiar with the main synchronization techniques and the main examples of inter-process communication,
they will have understood the basic tools and fundamental techniques for effective programming of those parts of parallel code that require intensive forms of communication and synchronization,
will have become familiar with basic principles and techniques for the implementation and experimental study of distributed and parallel programs,
will be able to study and analyze the performance of distributed and parallel algorithms and computations executed over both multicore and message-passing systems,
will master the main methodologies for the analysis of parallel and distributed algorithms,
will be able to design, implement and analyze distributed data structures and data structures for shared memory systems; and
will be familiar with known correctness and progress conditions of parallel and distributed computation.
Student Performance Evaluation
Specific details on grading can be found on the course’ s website
The courses of the Computer Science Department are designated with the letters "CS" followed by three decimal digits. The first digit denotes the year of study during which students are expected to enroll in the course; the second digit denotes the area of computer science to which the course belongs.
First Digit
Advised Year of Enrollment
1,2,3,4
First, Second, Third and Fourth year
5,6
Graduate courses
7,8,9
Specialized topics
Second Digit
Computer Science Area
0
Introductory - General
1
Background (Mathematics, Physics)
2
Hardware Systems
3
Networks and Telecommunication
4,5
Software Systems
6
Information Systems
7
Computer Vision and Robotics
8
Algorithms and Theory of Computation
9
Special Projects
The following pages contain tables (one for each course category) summarizing courses offered by the undergraduate studies program of the Computer Science Department at the University of Crete. Courses with code-names beginning with "MATH" or "PHYS" are taught by the Mathematics Department and Physics Department respectively at the University of Crete.
Announcements
|
News
