Vi överväger en variation av snabbköpsmodellen där servrarna kan kommunicera med sina grannar och där relationerna i grannskapet beskrivs i form av en lämplig graf. Uppgifter med enhetsexponentiella servicetid fördelningar anländer till varje vertex som oberoende Poisson processer med hastighet λ, och varje uppgift är oåterkalleligen tilldelas den kortaste kön bland den som den först visas och dess d - 1 slumpmässigt utvalda grannar. Denna modell har studerats ingående när den underliggande grafen är en klick i vilket fall den minskar till den välkända power-of-d systemet. I synnerhet resultaten av Mitzenmacher (1996) och Vvedenskaya et al. (1996) visar att eftersom storleken på klicken blir stor, konvergerar beläggningsprocessen i samband med kölängderna på de olika servrarna till en deterministisk gräns som beskrivs av ett oändligt system av vanliga differentialekvationer (ODE). I detta arbete tar vi hänsyn till inställningar där den underliggande grafen inte behöver vara en klick och tillåts vara lämpligt gles. Vi visar att om minimigraden närmar sig oändligheten (dock långsamt) när antalet servrar N närmar sig oändligheten, och förhållandet mellan den maximala graden och minimigraden i varje ansluten komponent närmar sig 1 enhetligt, konvergerar beläggningsprocessen till samma system av ODE som den klassiska snabbköpsmodellen. Särskilt är det asymptotiska beteendet hos beläggningsprocessen okänsligt för den exakta nätverkstopologin. Vi studerar också fallet där grafsekvensen är slumpmässig, med N-th grafen ges som en Erdős-Rényi slumpmässig graf på N hörn med genomsnittlig grad c(N). Annealiserad konvergens av beläggningsprocessen till samma deterministiska gräns är etablerad under villkoret c(N) → ∞, och under ett starkare villkor c(N)/ ln N → ∞, konvergens (i sannolikhet) visas för nästan varje förverkligande av den slumpmässiga grafen.
På liknande sätt, Budhiraja et al. REF studerade den lokala power-of-d schemat på grafer, och visade att så länge den minsta graden av grafen skiljer sig, och den grad-viktade adjacen matrisen av grafen är asymptotiskt dubbel-stochastic, beläggningsprocessen konvergerar till samma system av ODEs som det på den fullständiga grafen.
PR ] 1 2 Se p 20 18 Supermarket Model on Graphs