Abstract-Vi anser ett kommunikationsproblem där en uppdatering av källmeddelandet måste förmedlas till en eller flera avlägsna mottagare som är intresserade av att upprätthålla specifika linjära funktioner i källmeddelandet. Inställningen är en där uppdateringarna är glesa i naturen, och där varken källan eller mottagaren eller mottagaren är medvetna om den exakta skillnaden vektor, men bara vet hur mycket gleshet som finns i skillnaden vektorn. Under denna ram är vi intresserade av att utforma linjär kodning och avkodningssystem som minimerar kommunikationskostnaderna. Vi visar att den optimala lösningen på detta problem hänger nära samman med begreppet maximal återvinningskod (MRC), som ursprungligen infördes i samband med kodning för lagringssystem. I samband med lagring garanterar MRCs optimalt raderingsskydd när systemet delvis begränsas till att ha lokala paritetsrelationer mellan lagringsnoder. I vårt problem, visar vi att optimala lösningar finns om och endast om MRCs av vissa slag (identifieras av de önskade linjära funktionerna) finns. Vi anser att punkt-till-punkt- och sändningsversioner av problemet och identifiera anslutningar till MRCs under båda dessa inställningar. För point-to-point-inställningen visar vi att vårt linjära kodsystem är optimalt även när icke-linjär kodning är tillåten. Teorin illustreras i samband med uppdatering av raderingskodade lagringsnoder. Vi presenterar exempel baserade på moderna lagringskoder, såsom minsta bandbredd regenererande koder.
I avsnitt II granskar vi de nödvändiga resultaten från REF för funktionsuppdateringar för point-to-point-inställningen.
Communication Cost for Updating Linear Functions When Message Updates are Sparse: Connections to Maximally Recoverable Codes
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}