Beräkningskomplexitet: undre gränser för jämförelsebaserad sortering och sökning, hashtabeller kontra träd, avvägningar mellan utrymme och noggrannhet vid strömmande data (Bloom-filter), P mot NP och konsekvenser för systemdesign, stopproblemet.
Lagringshierarki: minnesväggen (DRAM-latens, SRAM, TCAM), IO-kostnader över olika substrat (elektriska, magnetiska, fotoniska), skrivoptimerade kontra läsoptimerade strukturer (LSM-träd kontra B-träd).
Arkitektur och maskinvarugränser: Amdahls lag, Moores lag och Dennard-skalning (effektväggen, mörkt kisel), sidokanalsattacker via spekulativ exekvering (Spectre, Meltdown).
Operativsystem, schemaläggning och samtidighet: dödlägen (Coffmans villkor), kostnader för kontextväxling, framstegsgarantier (obstruktionsfri, låsfri, väntefri), schemaläggningsoptimalitet (SJF/SRTF), avvägningar mellan batch- och interaktiv schemaläggning, prioritetsinversion.
Distribuerade system och feltolerans: FLP-omöjlighet, CAP och PACELC, Bysantinsk feltolerans (2f+1- och 3f+1-gränser), svanslatens i stor skala, bandbreddsfördröjningsprodukt.
Kvantmekaniska realiteter: icke-kommunikationsteoremet, sammanflätning och samordningseffektivitet, dekoherens som systemproblem.
Efter godkänd kurs ska studenten kunna
- förklara fundamentala omöjlighetsresultat och undre gränser för beräkning och kommunikation samt resonera om deras konsekvenser för vad datorsystem kan och inte kan göra
- jämföra algoritmer, datastrukturer och lagringsstrukturer med avseende på deras inneboende avvägningar mellan tid, utrymme, noggrannhet och ordningsgarantier samt välja en lämplig algoritm, datastruktur eller lagringsstruktur utifrån kraven i en given tillämpning
- beskriva minnes- och lagringshierarkin och analysera hur maskinvarans fysikaliska egenskaper begränsar prestandan hos algoritmer och datastrukturer
- förklara de fysikaliska och arkitekturmässiga gränserna för processorprestanda och analysera de avvägningar mellan prestanda, energieffektivitet och isolering som följer av dem i moderna parallella och heterogena arkitekturer
- analysera schemaläggnings-, synkroniserings- och resursdelningsproblem i operativsystem och samtidiga program samt resonera om avvägningarna mellan genomströmning, svarstid, rättvisa, framstegsgarantier och overhead
- förklara de fundamentala gränserna för konsistens, tillgänglighet, latens, genomströmning och feltolerans i distribuerade system och nätverk samt tillämpa dem för att resonera om storskaliga systems utformning och beteende
- beskriva vad fysikens lagar, inklusive kvantmekaniken, tillåter och omöjliggör när det gäller kommunikation, samordning och beräkning samt bedöma vilka möjligheter och begränsningar detta medför för utformning av system
- tillämpa omöjlighetsresultat, undre gränser och fundamentala avvägningar för att analysera och kritiskt värdera utformningen av ett befintligt datorsystem
- avgöra när en föreslagen systemdesign står i konflikt med en fundamental gräns och göra välgrundade avvägningar vid utformning av datorsystem.
