ID2226 Fundamentals of Scalable Computing Systems 7.5 credits

Computational complexity: comparison-based sorting and searching lower bounds, hash tables vs. trees, space-accuracy trade-offs in streaming (Bloom filters), P vs. NP and consequences for system design, the Halting Problem. Storage hierarchy: the memory wall (DRAM latency, SRAM, TCAM), IO costs across substrates (electric, magnetic, photonic), write-optimized vs. read-optimized structures (LSM-trees vs. B-trees). Architecture and hardware limits: Amdahl’s law, Moore’s law and Dennard scaling (power wall, dark silicon), speculative execution side-channel attacks (Spectre, Meltdown). Operating systems, scheduling, and concurrency: deadlocks (Coffman conditions), context switching costs, progress guarantees (obstruction-free, lock-free, wait-free), scheduling optimality (SJF/SRTF), batch vs. interactive scheduling trade-offs, priority inversion. Distributed systems and fault tolerance: FLP impossibility, CAP and PACELC, Byzantine fault tolerance (2f+1, 3f+1 bounds), tail latency at scale, the bandwidth-delay product limit. Quantum realities: the no-communication theorem, entanglement and coordination efficiency, decoherence as a systems problem.

After passing the course, the student should be able to:

• explain fundamental impossibility results and lower bounds in computation and communication, and reason about their consequences for what computer systems can and cannot do
• compare algorithms, data structures and storage structures with respect to their inherent trade-offs between time, space, accuracy and ordering guarantees, and select an appropriate algorithm, data structure or storage structure for the requirements of a given application
• describe the memory and storage hierarchy and analyze how the physical properties of hardware substrates constrain the performance of algorithms and data structures
• explain the physical and architectural limits on processor performance and analyze the resulting trade-offs between performance, energy efficiency and isolation in modern parallel and heterogeneous architectures
• analyze scheduling, synchronization and resource-sharing problems in operating systems and concurrent programs, and reason about the trade-offs between throughput, response time, fairness, progress guarantees and overhead
• explain the fundamental limits on consistency, availability, latency, throughput and fault tolerance in distributed systems and networks, and apply them to reason about the design and behavior of large-scale systems
• describe what the laws of physics, including quantum mechanics, permit and forbid for communication, coordination and computation, and assess the resulting opportunities and limitations for system design
• apply impossibility results, lower bounds and fundamental trade-offs to analyze and critically evaluate the design of an existing computer system
• recognize when a proposed system design conflicts with a fundamental limit and make well-founded design trade-offs

Programming knowledge and skills corresponding to the completion of course DD1337/DD1310–DD1319/DD1321/DD1331/DD1333/DD100N/DD100V/ID1018/ID1022.

Knowledge of algorithms and data structures (6 credits) corresponding to the completion of course DD1338/DD1320–DD1328/DD2325/ID1020/ID1021, or the completion of the KONT and LABD examination components in DD1326.

• TEN1 - On-Campus Digital Exam, 4.0 credits, grading scale: A, B, C, D, E, FX, F
• PRO1 - Project, 3.5 credits, grading scale: P, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability. The examiner may apply another examination format when re-examining individual students. If the course is discontinued, students may request to be examined during the following two academic years.

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.