Explosionen i de volymer data som lagras online har lett till att distribuerade lagringssystem har gått över till raderingsbaserade kodningssystem. Men de koder som används i praktiken är ganska korta. I detta arbete tar vi itu med vad vi ser som den huvudsakliga kodningsteoretiska barriären för att lägga ut längre koder i lager: i stora längder är misslyckanden inte oberoende och korrelerade misslyckanden är oundvikliga. Detta motiverar utformning av koder som möjliggör snabb dataåterställning även efter stora korrelerade fel, och som har effektiv kodning och avkodning. Vi föreslår att koddesign för distribuerad lagring ska ses som en tvåstegsprocess. Det första steget är att välja en topologi av koden, som innehåller kunskap om de korrelerade fel som måste hanteras, och säkerställer lokal återhämtning från sådana misslyckanden. I det andra steget anger man en kod med den valda topologin genom att välja koefficienter från ett ändligt fält F q. I detta steg försöker man balansera tillförlitlighet (vilket är bättre över större fält) med kodning och avkodning effektivitet (vilket är bättre över mindre fält). Detta arbete initierar en fördjupad studie av denna avvägning mellan tillförlitlighet och effektivitet. Vi anser att den fältstorlek som behövs för att uppnå maximal återhämtningsförmåga: den starkaste tillförlitlighet som är möjlig med en given topologi. Vi föreslår en familj av topologier som kallas rutnätsliknande topologier som förenar ett antal topologier som beaktas både i teori och praktik, och bevisar följande resultat om koder för sådana topologier: • Den första superpolynomet lägre gräns på den fältstorlek som behövs för att uppnå maximal återvinning i en enkel rutnätsliknande topologi. Så vitt vi vet fanns det ingen superlinjär nedre gräns som var känd tidigare, för någon topologi. • En kombinatorisk karakterisering av raderingsmönster som kan korrigeras med Maximalt återvinningsbara koder för en topologi som motsvarar tensering av MDS-koder med en paritetskontrollkod. Denna topologi används i praktiken (t.ex. [MLR + 14]). Vi förmodar att en liknande karakterisering för Maximalt Återvinnbara koder omedelbart inlöser godtyckliga tensor produkt topologier. • En ny asymptotiskt optimal familj av Maximalt återvinningsbara koder för en viss grundläggande topologi som avslutar arbetslinjen i [BHH13, GHJY14] arXiv:1605.05412v1 [cs.IT]
Koder för korrelerade misslyckanden: Mycket nyligen, Gopalan et al. REF presenterade en klass av maximalt återvinningsbara (MR) koder för rutnätsliknande topologier.
Maximally Recoverable Codes for Grid-like Topologies
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}