Abstract-Vi anser att problemet med att beräkna konvolution av två långa vektorer med hjälp av parallella processorer i närvaro av "stragglers". Stragglare avser den lilla delen av felaktiga eller långsamma processorer som fördröjer hela beräkningen i tidskritiska distribuerade system. Vi visar först att dela vektorerna i mindre bitar och använda en linjär kod för att koda dessa bitar ger förbättrad motståndskraft mot stragglers än replikation-baserade system under en enkel, värsta fall straggler analys. Vi visar sedan att enligt vanliga modeller av beräkningstid, kodning kan dramatiskt förbättra sannolikheten för att avsluta beräkningen inom en mål "deadline" tid. I motsats till den mer allmänt använda tekniken för förväntad beräkningstid analys, kvantifierar vi exponenter för sannolikheten för misslyckande i gränsen för stora deadlines. Vår exponent metrisk fångar sannolikheten för att misslyckas med att avsluta innan en angiven deadline tid, dvs beteendet hos "tail". Dessutom möjliggör vår teknik även enkla slutna formuttryck för mer generella modeller av beräkningstid, t.ex. skiftade Weibull modeller istället för bara skiftade exponentiella. Således, genom detta problem av kodad convolution, vi etablera nyttan av en ny asymptotic fel exponent analys för distribuerade system.
Kodad beräkning av konvolution av två långa vektorer fördelade i närvaro av stragglers föreslås i REF.
Coded convolution for parallel and distributed computing within a deadline
{'venue': '2017 IEEE International Symposium on Information Theory (ISIT)', 'journal': '2017 IEEE International Symposium on Information Theory (ISIT)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}