Technische Samenvatting: Generatief Markov-model voor gedistribueerde computersystemen

Probleemstelling

Opkomende paradigma's voor gedistribueerde computing, zoals de computing continuum, worden gekenmerkt door inherente heterogeniteit, stochasticiteit en complexiteit. Hoewel cloud computing voordelen biedt zoals on-demand provisioning, brengt het opschalen van AI-inferentie-infrastructuur om aan de groeiende vraag te voldoen aanzienlijke kosten en milieu-impact met zich mee. Alternatieve paradigma's zoals volunteer computing en de computing continuum (de integratie van gebruikersapparaten, edge en cloud) bieden potentieel voor efficiëntiewinsten. Deze systemen worstelen echter met het bieden van stabiele Quality-of-Service (QoS) garanties vanwege de heterogeniteit van resources en de intermitterende beschikbaarheid van gebruikers.

De kernuitdaging die wordt geïdentificeerd, is het gebrek aan een verenigd formeel model dat in staat is om rekening te houden met de heterogeniteit van resources, de stochastische beschikbaarheid en de hoge dimensionaliteit van systeemtoestanden. Zonder een dergelijk model blijft het redeneren over prestatieafwegingen en het optimaliseren van beslissingsbeleid op schaal moeilijk, wat grootschalige implementaties belemmert.

Methodologie

De auteurs stellen een Generatief Markov-model (GMM) framework voor om gedistribueerde computersystemen te modelleren. De methodologie steunt op een gestructureerde, gefactoriseerde representatie van de systeemtoestand om tractabiliteit te waarborgen.

1. Theoretisch Kader

De systeemtoestand op tijdstip $t$, aangeduid als $s_t$, wordt gedefinieerd als een tuple van $N$ hoogdimensionale variabelen. Om de complexiteit van de gezamenlijke distributie over toestandssequenties te beheersen, legt het model de Markov-eigenschap op en maakt het gebruik van een twee-niveau ijle factorisatie (sparse factorization):

• Variabele Factorisatie: De gezamenlijke distributie $p(s_t | s_{t-1})$ wordt gedecomposeerd in conditionele distributies (factoren) voor elke hoogwaardige variabele $v_t$, geconditioneerd op een specifieke subset van ouder-variabelen $Pa(v_t)$ uit de huidige en voorgaande toestanden.
• Element Factorisatie: Elke hoogdimensionale variabele $v_t$ wordt verder gefactoriseerd over zijn individuele elementen $v_t \in v_t$. Dit maakt gebruik van de ijle afhankelijkheidsstructuur die inherent is aan gedistribueerde systemen, waarbij componenten (bijv. nodes, taken) evolueren op basis van lokale informatie in plaats van de globale toestand.

Deze factorisatie levert een tractabel model op dat simulatie, inferentie en beleersoptimalisatie mogelijk maakt over systeemtoestanden die anders computationeel onhaalbaar zouden zijn.

2. Casestudy: Collaboratieve Gedistribueerde AI-inferentie

Het framework wordt geïnstantieerd voor een scenario van collaboratieve AI-inferentie bestaande uit een dedicated server ($v_0$) en een verzameling gebruikersnodes ($I$).

• Systeemtoestand: De toestandsvector $s_t$ bevat gebruikersbeschikbaarheid ($o_t$), aanvraagtoestanden ($q_t$), resource-allocaties ($a_t$), gereedheidstoestanden ($x_t$), executietoestanden ($y_t$), resourceverbruik ($c_t$) en duur-variabelen ($d_t$).
• Afhankelijkheden: Het model legt complexe afhankelijkheden vast, zoals de autocorrelatie van resources (behandeld via history buffers) en de koppeling tussen de dataoverdrachtfase en de executiefase.
• Beleid (Policies): Besluitvorming wordt gestuurd door twee beleidsfactoren:
  • Scheduler ($\pi$): Draait op de server en beslist over het downloaden van subtaken en de toewijzing van executie.
  • Executor ($\varsigma$): Draait op elke node en handhaaft lokale resource-restricties (bijv. aborts, pauzes).
• Optimalisatieproblemen:
  • Optimalisatie van het Scheduler-beleid: Geformuleerd als een average-reward Reinforcement Learning (RL) probleem om de lange-termijn QoS te maximalen (minimaliseren van latentie).
  • Optimalisatie van Dedicated Resources: Een chance-constrained optimalisatieprobleem om de minimale nominale serverresources te vinden die nodig zijn om specifieke latentiedrempels voor verschillende typen taken te halen, gegeven vaste policies.

Belangrijkste Bijdragen

1. Generatieve Markov-modellering: Het artikel introduceert een framework dat het gehele gedistribueerde computersysteem modelleert als een generatief Markov-model. In tegenstelling tot eerder werk dat specifieke beslissingsproblemen als MDP's formuleert, modelleert deze aanpak de systeemdynamiek zelf, waardoor de brug wordt geslagen tussen gedistribueerde computing en Markov-ketentheorie en RL.
2. Nieuwe Factorisatiestructuur: Het framework maakt gebruik van een nieuwe twee-niveau ijle factorisatie (variabele- en elementniveau) en een modulaire structuur. Dit maakt het mogelijk om conditionele distributies onafhankelijk te schatten met technieken die geschikt zijn voor specifieke systeemvariabelen, waardoor het model tractabel blijft ondanks de hoge dimensionaliteit.
3. Praktische Instantiatie: De auteurs bieden een concrete instantiatie voor collaboratieve AI-inferentie, waarbij wordt aangetoond hoe het model de interactie tussen dedicated serverresources en vrijwillige gebruikersresources afhandelt.

Resultaten

Het framework werd geëvalueerd via een simulatie van een gedistribueerd inferentiesysteem met tot 10.000 gebruikers en variërende servercapaciteiten. Twee scheduling-policies werden vergeleken: Centralized (alle subtaken op de server) en Distributed (subtaken gelijkmatig verdeeld over de server en online gebruikers).

• Latentieprestaties: Naarmate het aantal gebruikers toenam, werd de centralized policy een bottleneck, wat leidde tot aanzienlijk hogere P99-latenties. In tegenstelling hiertoe presteerde de distributed policy progressief beter dan de centralized aanpak, waarbij zelfs met naïeve distributiestrategieën lagere latenties werden behaald.
• Resource-efficiëntie: De distributed policy behaalde consistent lager CPU- en geheugengebruik op de server vergeleken met de centralized policy. Opvallend genoeg behaalden beide policies bij 1.000 gebruikers vergelijkbare P99-latenties, maar deed de distributed policy dit met aanzienlijk lagere serverresourceconsumptie.
• Schaalbaarheid: De resultaten wijzen erop dat het distribueren van computation over gebruikersapparaten zowel de latentie als het serverresourceverbruik vermindert, wat de effectiviteit van adaptieve besluitvorming in dergelijke omgevingen valideert.

Betekenis en Claims

Het artikel claimt dat het voorgestelde framework een noodzakelijk formeel model biedt voor het redeneren over prestatieafwegingen en het optimaliseren van besluitvorming in complexe, heterogene gedistribueerde systemen. Door de systeemtoestand tractabel te maken via ijle factorisatie, maakt het framework het volgende mogelijk:

• Simulatie en Evaluatie: De mogelijkheid om systeemgedrag te simuleren onder variërende omstandigheden (bijv. belasting, beschikbaarheid van resources) zonder dat een volledige fysieke deployment vereist is.
• Beleidsoptimalisatie: Een directe brug naar RL-methoden voor het leren van optimale scheduling-policies (zoals gedefinieerd in de optimalisatieproblemen).
• Modulariteit: De capaciteit om het model uit te breiden naar nieuwe types resources, taakstructuren of node-gedrag zonder het gehele framework te herontwerpen.

De auteurs concluderen dat terwijl gecentraliseerde scheduling op schaal faalt, het distribueren van computation over gebruikersapparaten aanzienlijke efficiëntiewinsten oplevert. Zij benadrukken dat het ontwikkelen en optimaliseren van dergelijke adaptieve beslissingsstrategieën onhaalbaar is zonder de verenigde probabilistische structuur die hun framework biedt. Toekomstig werk zal zich richten op validatie in echte omgevingen, schaalbaarheidsonderzoeken en verdere optimalisatie van de scheduler- en resource-allocatie-policies.