Ett datornätverk betjänar distribuerade program genom att kommunicera meddelanden mellan sina fjärr ändar. Många sådana program önskar minimal fördröjning för sina meddelanden. Utöver detta effektivitetsmål omfattas tilldelningen av nätkapaciteten också av kravet på rättvisa villkor att inte stänga av kommunikationen för något enskilt meddelande. Processor Sharing (PS) är en de facto-standard för rättvisa men ger betydligt högre genomsnittlig fördröjning än Shortest Resting Processing Time (SRPT), som är en optimal men orättvis algoritm. I den här artikeln utforskar vi effektiva rättvisa algoritmer för meddelandekommunikation där rättvisa innebär att inget meddelande levereras senare än under PS. Först introducerar vi ett slack system för att karakterisera rättvisa algoritmer helt och utveckla effektiva rättvisa algoritmer som kallas Pessimistic Fair Sojourn Protocol (PFS), Optimistic Fair Sojourn Protocol (OFSP) och Shortest Fair Sojourn (SFS). Då bevisar vi att en rättvis online-algoritm inte garanterar minimal genomsnittlig fördröjning uppnåelig med rättvisa. Vår analys avslöjar också lägre gränser på värsta fall ineffektivitet av rättvisa algoritmer. Vi utför omfattande simuleringar för olika distributioner av meddelandestorlekar och ankomsttider. Under antingen tillfällig överbelastning eller stationär drift stöder SFS och andra nyligen föreslagna rättvisa algoritmer SRPT-lik effektivitet och ger konsekvent mycket mindre genomsnittlig fördröjning än PS.
Gorinsky m.fl. ge det teoretiska beviset REF att deras kortaste Fair Sojourn (SFS), Optimistic Fair Sojourn Protocol (OFSP) och Shortest Fair Sojourn (SFS) schemaläggning politik är rättvisa utan att svälta några flöden.
Efficient fair algorithms for message communication
{'venue': 'Simul. Model. Pract. Theory', 'journal': 'Simul. Model. Pract. Theory', 'mag_field_of_study': ['Computer Science']}