I . I N TRODUC T ION

D I S T R I BU T ED s t o r a g e s y s t em s h a v e b e e n t r a d i t i o n a l l y r e p l i c a t i n g d a t a o v e r m u l t i p l e n o d e s t o g u a r a n t e e r e l i a b i l -M a n u s c r i p t r e c e i v e d D e c em b e r 5 , 2 0 1 7 ; r e v i s e d D e c em b e r 2 8 , 2 0 1 8 ; a c c e p t e d A p r i l 2 2 , 2 0 1 9 . D a t e o f p u b l i c a t i o n M a y 8 , 2 0 1 9 ; d a t e o f c u r r e n t v e r s i o n A u g u s t 1 6 , 2 0 1 9 . I . D u u r sm a w a s s u p p o r t e d i n p a r t b y t h e S im o n s F o u n d a t i o n u n d e r G r a n t 2 8 0 1 0 7 a n d i n p a r t b y N S F u n d e r G r a n t C C F -1 6 1 9 1 8 9 . A . S p r i n t s o n w a s s u p p o r t e d b y t h e N a t i o n a l S c i e n c e F o u n d a t i o n u n d e r G r a n t 1 7 1 8 6 5 8 a n d G r a n t 1 6 4 2 9 8 3 . T h i s p a p e r w a s p r e s e n t e d i n p a r t a t t h e 2 0 1 6 5 4 t h A n n u a l A l l e r t o n C o n f e r e n c e o n C omm u n i c a t i o n , C o n t r o l , a n d C om p u t i n g . S . K a d h e w a s w i t h t h e E C E D e p a r tm e n t , T e x a s A&M U n i v e r s i t y , C o l l e g e S t a t i o n , TX 7 7 8 4 3 U SA . H e i s n o w w i t h t h e D e p a r tm e n t o f E l e c t r i c a l E n g i n e e r i n g a n d C om p u t e r S c i e n c e s , U n i v e r s i t y o f C a l i f o r n i a a t B e r k e l e y , B e r k e l e y , CA 9 4 7 2 0 U SA ( e -m a i l : sw a n a n d . k a d h e@ b e r k e l e y . e d u ) . S . E l R o u a y h e b i s w i t h t h e D e p a r tm e n t o f E l e c t r i c a l a n d C om p u t e r E n g i n e e r i n g , R u t g e r s U n i v e r s i t y-T h e S t a t e U n i v e r s i t y o f N e w J e r s e y , N e w B r u n sw i c k , N J 0 8 9 0 1 -8 5 5 4 U SA ( e -m a i l : s a l im . e l r o u a y h e b@ r u t g e r s . e d u ) . I . D u u r sm a i s w i t h t h e D e p a r tm e n t o f M a t h em a t i c s , U n i v e r s i t y o f I l l i n o i s U r b a n a -C h am p a i g n , C h am p a i g n , I L 6 1 8 0 1 U SA ( e -m a i l : d u u r sm a@ i l l i n o i s . e d u ) . A . S p r i n t s o n i s w i t h t h e D e p a r tm e n t o f E l e c t r i c a l a n d C om p u t e r E n g in e e r i n g , T e x a s A&M U n i v e r s i t y , C o l l e g e S t a t i o n , TX 7 7 8 4 3 U SA ( e -m a i l : s p a l e x@ t am u . e d u ) . C omm u n i c a t e d b y P . G o p a l a n , A s s o c i a t e E d i t o r f o r C o d i n g T h e o r y . C o l o r v e r s i o n s o f o n e o r m o r e o f t h e fi g u r e s i n t h i s p a p e r a r e a v a i l a b l e o n l i n e a t h t t p : / / i e e e x p l o r e . i e e e . o r g . D i g i t a l O b j e c t I d e n t i fi e r 1 0 . 1 1 0 9 / T I T . 2 0 1 9 . 2 9 1 5 5 3 9 i t y a g a i n s t f a i l u r e s a n d p r o t e c t t h e d a t a f r om b e i n g l o s t [ 1 ] , [ 2 ] .

H ow e v e r , t h e e n o rm o u s g r ow t h o f d a t a b e i n g s t o r e d o r c omp u t e d o n l i n e h a s m o t i v a t e d p r a c t i c a l s y s t em s t o em p l o y e r a s u r e c o d e s f o r h a n d l i n g f a i l u r e s ( e . g . , [ 3 ] , [ 4 ] ) . T h i s h a s g a l v a n i z e d s i g n i fi c a n t i n t e r e s t i n t h e p a s t f e w y e a r s o n n o v e l e r a s u r e c o d e s t h a t e f fi c i e n t l y h a n d l e n o d e f a i l u r e s i n d i s t r i b u t e d s t o r a g e s y s t em s . O n e o f t h e m a i n f am i l i e s o f c o d e s t h a t h a s r e c e i v e d p r im a r y r e s e a r c h a t t e n t i o n i sl o c a l l y r e p a i r a b l e c o d e s ( L R C s ) -t h a t m i n im i z e l o c a l i t y ,i . e . , t h e n um b e r o f n o d e s p a r t i c i p a t i n g i n t h e r e p a i r p r o c e s s ( s e e , e . g . , [ 5 ] -[ 9 ] ) . A lm o s t a l l t h e w o r k i n t h e l i t e r a t u r e o n L R C s h a s c o n s i d e r e d b l o c k c o d e s u n d e r t h e H amm i n g m e t r i c . I n t h i s w o r k , w e fi r s t f o c u s o u r a t t e n t i o n t o c o d e s w i t h l o c a l i t y c o n s t r a i n t s i n t h e r a n k m e t r i c . L e tF q b e t h e fi n i t e fi e l d o f s i z eq . C o d e w o r d s o f a r a n k -m e t r i c c o d e ( a l s o k n ow n a s a n a r r a y c o d e ) a r em×nm a t r i c e s o v e rF q ,w h e r e t h e r a n k d i s t a n c e b e tw e e n tw o m a t r i c e s i s t h e r a n k o f t h e i r d i f f e r e n c e [ 1 0 ] -[ 1 2 ] . W e a r e i n t e r e s t e d i n r a n k -m e t r i c c o d e s w i t h l o c a l i t y c o n s t r a i n t s . T o q u a n t i f y t h e r e q u i r em e n t o f l o c a l i t y u n d e r t h e r a n k m e t r i c , w e i n t r o d u c e t h e n o t i o n o f r a n k -l o c a l i t y . W es a y t h a t t h e i -t h c o l um n o f a n m×na r r a y c o d e h a s( r , δ )r a n kl o c a l i t y i f t h e r e e x i s t s a s e t ( i ) o fr +δ -1 c o l um n s c o n t a i n i n g is u c h t h a t t h e a r r a y c o d e f o rm e d b y d e l e t i n g t h e c o l um n s o u t s i d e ( i )f o r e a c h c o d e w o r d h a s r a n k d i s t a n c e a t l e a s tδ . W e s a y t h a t a n m×na r r a y c o d e h a s( r , δ )r a n k -l o c a l i t y i f e v e r y c o l um n h a s( r , δ ) r a n k -l o c a l i t y . O u r m o t i v a t i o n o f c o n s i d e r i n g r a n k -l o c a l i t y i s t o d e s i g n c o d e s t h a t c a n l o c a l l y r e c o v e r f r omr a n k e r r o r s a n d e r a s u r e s . R a n k -e r r o r s a r e t h e e r r o r p a t t e r n s s u c h t h a t t h e r a n k o f t h e e r r o r m a t r i x i s l im i t e d . ) O u r g o a l i s t o i n v e s t i g a t e c o d e s t h a t c a nl o c a l l y r e c o v e r f r om c r i s s c r o s s e r a s u r e s ( a n d r a n k -e r r o r s ) . W e n o t e t h a t c r i s s c r o s s e r r o r s (w i t h n o l o c a l i t y ) h a v e b e e n s t u d i e d p r e v i o u s l y i n t h e l i t e r a t u r e [ 1 2 ] , [ 1 3 ] , m o t i v a t e d b y a p p l i c at i o n s i n m em o r y c h i p a r r a y s a n d m u l t i -t r a c k m a g n e t i c t a p e s . 0123456789 a n d t h e e x t e n s i o n fi e l d F q m o fF q . I n p a r t i c u l a r , b y fi x i n g a b a s i s f o rF q m a s a n m-d im e n s i o n a l v e c t o r s p a c e o v e r F q , a n y e l em e n t o f F q m c a n b e r e p r e s e n t e d a s a l e n g t h -m v e c t o r o v e rF q . S im i l a r l y , a n y l e n g t h -nv e c t o r o v e rF q m c a n b e r e p r e s e n t e d a s a nm × n m a t r i x o v e r F q . T h e r a n k o f a v e c t o r a∈ F n q m i s t h e r a n k o f t h e c o r r e s p o n d i n gm × nm a t r i x A o v e rF q . T h i sr A s w e w i l l s e e i n S e c t i o n V , t h e( r , δ ) -r a n k -l o c a l i t y a l l ow s u s t o r e p a i r a n y c r i s s c r o s s e r a s u r e p a t t e r n o fw e i g h tδ -1 i n C| ( i ) , ∀ i ∈

. T h o u g h t h i s p a t t e r n c o r r u p t s h a l f t h e b i t s , i t s r a n k o v e r t h e b i n a r y fi e l d i s o n l y o n e . N o t e t h a t i t i s n o t p o s s i b l e t o c o r r e c t s u c h a n e r r o r p a t t e r n u s i n g a c o d e e q u i p p e d w i t h t h e H amm i n g m e t r i c . O n t h e o t h e

( 5 )

T

T h e r e f o r e , w e h a v e

T L emm a 1 . T h e n e v a l u a t i o n p o i n t s g i v e n i n C o n s t r u c t i o n 1 , P= α i β j , 1≤i ≤r+δ -1 , 1≤ j ≤µ , a r e l i n e a r l y i n d ep e n d e n t o v e rF q .

P r o o f : S u p p o s e , f o r c o n t r a d i c t i o n , t h a t t h e e v a l u at i o n p o i n t s a r e l i n e a r l y d e p e n d e n t o v e rF q . T h e n , w e h a v e µ j =1

r +δ -1 i =1 ω i j α i β j = 0 w i t h c o e f fi c i e n t s ω i j ∈ F q s u c h t h a t n o t a l lω i j ' s a r e z e r o . W e c a n w r i t e t h e l i n e a r d e p e n d e n c e c o n d i t i o n a s µ j =1 r +δ -1 i =1 ω i j α i β j =0 . N ow , f r om t h e l i n e a r i n d e p e n d e n c e o f t h e β j ' s o v e r F q r +δ -1 ,w eh a v e r +δ -1 i =1 ω i j α i =0 f o r e a c h 1≤ j ≤µ .H ow e v e r ,a s t h e α i ' s a r e l i n e a r l y i n d e p e n d e n t o v e r F q ,w eh a v ee v e r y ω i j =0 . T h i s i s a c o n t r a d i c t i o n .

N e x t , w e p r e s e n t a l emm a t h a t w i l l b e u s e d t o p r o v e t h e r a n k -l o c a l i t y f o r t h e p r o p o s e d c o n s t r u c t i o n . T ow a r d s t h i s , d e fi n eH( x ) = x q r +δ -1 -1 =x [ r +δ -1 ]-1 . W e n o t e t h a t ( 5 ) c a n b e w r i t t e n i n t h e f o l l ow i n g f o rm u s i n gH( x ) :

w h e r e G i ( x

. ( 1 0 )

T o s e e t h i s , o b s e r v e t h a t [ H( x ) ]

j -1 l =0 q ( r +δ -1 ) l +i = x q r +δ -1 -1 j -1 l =0 q ( r +δ -1 ) l +i = x j -1 l =0 q ( r +δ -1 ) ( l +1 ) +i -j -1 l =0 q ( r +δ -1 ) l +i = x q ( r +δ -1 ) j +i -q i .

(

N ow , u s i n g ( 1 1 ) i n ( 1 0 ) , w e g e t

T h e n , s u b s t i t u t i n g ( 1 2 ) i n t o ( 9 ) g i v e s u s ( 5

, w h e r e t h e l a s t e q u a l i t y f o l l ow s f r omα

N ow , w e u s e L emm a s 1 a n d 2 t o p r o v e t h e r a n k -l o c a l i t y a n d r a n k d i s t a n c e o p t im a l i t y o f t h e p r o p o s e d c o n s t r u c t i o n .

T h e o r em 2 . C o n s t r u c t i o n 1 g i v e s a l i n e a r ( m × n , k , d ) r a n k -m e t r i c c o d eC L o c w i t h( r , δ )r a n k -l o c a l i t y s u c h t h a t t h e m i n im um r a n k d i s t a n c e d i s e q u a l t o t h e u p p e r b o u n d g i v e n i n ( 3 ) .

P r o o f : W e b e g i n w i t h s h ow i n g t h e r a n k d i s t a n c e o p t im a l i t y o f C L o c . L emm a 1 a s s e r t s t h a tC L o c i s o b t a i n e d a s

t h e e v a l u a t i o n s o fG m ( x )o nnp o i n t s o fF q m t h a t a r e l i ne a r l y i n d e p e n d e n t o v e rF q . C om b i n i n g t h i s w i t h t h e s t r u c t u r e o fG m ( x )( s e e ( 5

) . T h i s s h ow s t h a t d R ( C L o c )a t t a i n s t h e u p p e r b o u n d ( 3 ) i n T h e o r em , a n d t h u s , t h e p r o p o s e d c o n s t r u c t i o n i s o p t im a l w i t h r e s p e c t t o r a n k d i s t a n c e . 4 S e c o n d , w e s h ow t h a tC L o c h a s( r , δ ) r a n k -l o c a l i t y . T ow a r d s t h i s , w e w a n t t o s h ow t h a t d R C j ≥δf o r e v e r y l o c a l c o d e C j , 1≤ j ≤µ .L e t γ∈P j a n d d e fi n e t h er e p a i r p o l y n om

( M o r e o v e r , w h e n e v a l u a t i n g R j ( x )i n λ∈P j ,w eg e t N e x t , w e p r e s e n t a n e x am p l e o f a n ( 9×9 , 4 )r a n k -m e t r i c c o d e w i t h( 2 , 2 ) r a n k -l o c a l i t y . W e n o t e t h a t t h e c o d e p r e s e n t e d i n t h i s e x am p l e s a t i s fi e s t h e c o r r e c t a b i l i t y c o n s t r a i n t s s p e c i fi e d i n t h e m o t i v a t i n g e x am p l e ( E x am p l e 1 ) i n t h e I n t r o d u c t i o n s e c t i o n . E x am p l e 2 . L e t n= 9 , k= 4 , r= 2 , δ= 2 .S e tq = 2a n d m=n . L e tωb e t h e p r im i t i v e e l em e n t o fF 2 9 w i t h r e s p e c t t o t h e p r im i t i v e p o l y n om i a l p ( x ) = x 9 +x 4 +1 . N o t e t h a t ω 7 3 g e n e r a t e sF 2 3 ,a sω 7 3 7 = 1 . C o n s i d e r A ={1 ,ω 7 3 ,ω 1 4 6 } a s a b a s i s f o rF 2 3 o v e rF 2 . W ev i e w F 2 9 a s a n e x t e n s i o n fi e l d o v e rF 2 3 c o n s i d e r i n g t h e i r r e d u c i b l e p o l y n om i a l p ( x ) =x 3 + x+ω 7 3 . I t i s e a s y t o v e r i f y t h a t ω 3 0 9 i s a r o o t o f p ( x ) , a n d t h u s , B= {1 ,ω 3 0 9 ,ω 1 0 7 } f o rm s a b a s i s o f F 2 9 o v e rF 2 3 . T h e n , t h e e v a l u a t i o n p o i n t s P a n d t h e i r p a r t i t i o n P i s a s f o l l o w s . P = P 1 = {1 ,ω 7 3 ,ω 1 4 6 } , P 2 = {ω 3 0 9 ,ω 3 8 2 ,ω 4 5 5 } , P 3 = {ω 1 0 7 ,ω 1 8 0 ,ω 2 5 3 }.

L e tm = ( m 0 0 ,m 0 1 ,m 1 0 ,m 1 1 )∈F G m ( x ) =m 0 0 x [ 0 ] +m 0 1 x [ 3 ] +m 1 0 x [ 1 ] +m 1 1 x [ 4 ] . R 1 ( x )= ( m 0 0 +m 0 1 ) x [ 0 ] +( m 1 0 +m 1 1 ) x [ 1 ] , R 2 ( x )= ( m 0 0 +ω 1 1 9 m 0 1 ) x [ 0 ] +( m 1 0 +ω 2 3 8 m 1 1 ) x [ 1 ] , R 3 ( x )= ( m 0 0 +ω 2 3 8 m 0 1 ) x [ 0 ] +( m 1 0 +ω 4 7 6 m 1 1 ) x [ 1 ] .

F o r i n s t a n c e , l e t t h e m e s s a g e v e c t o r b em =( ω , ω 2 ,ω 4 ,ω 8 ) . ω 4 4 0 ,ω 3 0 7 ,ω 8 1 ,ω 4 6 5 ,ω 1 1 ,ω 1 7 4 ,ω 2 3 6 ,ω 1 3 2 ,ω 3 9 9 ) .

O n e c a n e a s i l y c h e c k t h a t e v a l u a t i n g R 1 ( x )o n P 1 g i v e s c 1 = ( ω 4 4 0 ,ω 3 0 7 ,ω 8 1 ) , e v a l u a t i n g R 2 ( x )o n P 2 g i v e sc 2 = ( ω 4 6 5 ,ω 1 1 ,ω 1 7 4 ) , a n d e v a l u a t i n g R 3 ( x )o n P 3 g i v e sc 3 = ( ω 2 3 6 ,ω 1 3 2 ,ω 3 9 9 ) . T h i s im p l i e s t h a t t h e l o c a l c o d eC j ,1≤ j≤ 3 , c a n b e c o n s i d e r e d a s o b t a i n e d b y e v a l u a t i n g a l i n e a r i z e d p o l y n om i a l o f t h e f o rm R j ( x ) =m 0 x [ 0 ] +m 1 x [ 1 ] o n t h r e e p o i n t s t h a t a r e l i n e a r l y i n d e p e n d e n t o v e r F 2 . H e n c e , C j i s a G a b i d u l i n c o d e o f l e n g t h 3 a n d d im e n s i o n 2 , w h i c h g i v e s d R C j = 2 .T h i s s h o w s t h a tCh a s( 2 , 2 )r a n k -l o c a l i t y .

B . C om p a r i s o n W i t h T am o a n d B a r g [ 9 ]

T h e k e y i d e a i n T h e a u t h o r s s h ow t h a th ( x )= x r +δ -1 c a n b e u s e d a s a g o o d p o l y n om i a l , w h e n t h e e v a l u a t i o n p o i n t s a r e c o s e t s o f a m u l t i p l i c a t i v e s u b g r o u p o fF * q o f o r d e rr +δ -1 . I n t h i s c a s e , w e c a n w r i t eg m ( x )a s

( R em a r k 5 . I t i s w o r t h n o t i n g t h a t s e v e r a l r e s u l t s o n s u b s p a c e c o d e s a r e q -a n a l o g s [ 4 5 ] o f w e l l -k n o w n r e s u l t s o n c l a s s i c a l c o d e s i n t h e H amm i n g m e t r i c . F o r i n s t a n c e , G r a s sm a n n i a n c o d e s a r e q -a n a l o g s o f c o n s t a n t w e i g h t c o d e s , a n d t h e s u bs p a c e d i s t a n c e i s t h e q -a n a l o g o f t h e H amm i n g d i s t a n c e i n t h e H amm i n g s p a c e . F o r f u r t h e r d e t a i l s , w e r e f e r t h e r e a d e r t o [ 4 5 ] .

B . L o c a l i t y i n t h e S u b s p a c e M e t r i c I n t h i s s e c t i o n , w e e x t e n d t h e c o n c e p t o f l o c a l i t y t o t h a t o fs u b s p a c e -l o c a l i t y . W e b e g i n w i t h s e t t i n g u p t h e n e c e

N o t e t h a t t h e c o d e | S i s e s s e n t i a l l y o b t a i n e d b y t a k i n g a p r o j e c t i o n o f e v e r y s u b s p a c eU o f o n t h e s u b s p a c e f o rm e d b y t h e b a s i s v e c t o r s i n d e x e d b y t h e e l em e n t s i nS . N ow , w e d e fi n e t h e n o t i o n o f s u b s p a c e -l o c a l i t y i n t h e f o l l ow i n g .

D e fi n i t i o n 5( S u b s p a c e -L o c a l i t y ) . A G r a s sm a n n i a n c o d e ⊆ G q ( M, n )i s s a i d t o h a v e ( r , δ )s u b s p a c e -l o c a l i t y i f , f o r e a c h i ∈ [ n ] , t h e r e e x i s t s a s e t ( i ) ⊂

D e fi n i t i o n 6 ( L i f t i n g ) .C o n s i d e r t h e f o l l o w i n g m a p p i n g

w h e r e I i s t h e n×n i d e n t i t y m a t r i x . T h e s u b s p a c e ( X)i s c a l l e d t h e l i f t i n g o f t h e m a t r i x X . 6 S im i l a r l y , f o r a r a n k -m e t r i c c o d eC⊆ F m×n q , t h e s u b s p a c e c o d e ( C )= { ( X) : X∈C } i s c a l l e d t h e l i f t i n g o f C . a f am i l y o f d i s t a n c e -o p t im a l L R C s p r e s e n t e d i n [ 9 , C o n s t r u ct i o n 8 ] .foot_1 ( S e e S e c . IV -B f o r d e t a i l s . ) L e t Cb e a n( n , k )L R C f r om t h i s f am i l y w i t h( r , δ )l o c a l i t y . L e t µ= n / ( r+δ-1 ) , a n dC 1 , C 2 , . . . , C µ d e n o t e t h eµ l o c a l c o d e s w i t h d i s j o i n t c o o r d i n a t e sC 1 , C 2 , . . . , C µ , r e s p e c t i v e l y . T h e n , a l o c a l c o d e C j c a n c o r r e c tδ-1 o r l e s s e r a s u r e s i nC j b y a c c e s s i n g u n e r a s e d s ym b o l s o n l y f r omC j ( f o r e v e r y 1≤ j≤ µ ) . F u r t h e r ,Cc a n c o r r e c t a n yd-1 e r a s u r e s , w h e r edi s t h e m i n im um d i s t a n c e g i v e n i n t h e r i g h t h a n d s i d e o f ( 1 ) . A n M R C c a n c o r r e c t a n y e r a s u r e p a t t e r n t h a t i s i n f o rm a t i o n -t h e o r e t i c a l l y c o r r e c t a b l e b y a n y L R C w i t h t h e s am e p a r am e t e r s . H ow e v e r , t h e i r l o c a l i t y g u a r a n t e e s a r e s i g n i fi c a n t l y d i f f e r e n t . F o r i n s t a n c e , i f a n e n t i r e r ow ( o r l e s s t h a n br ow s ) i s e r a s e d ,

N o t e t h a t t h e l i f t i n g o p e r a t i o n X → ( X)i s a n i n j e c t i v e m a p p i n g , s i n c e e v e r y s u b s p a c e c o r r e s p o n d s t o a u n i q u e m a t r i x i n r e d u c e d c o l um n e c h e l o n f o rm ( R C E F ) . T h u s , w e h a v e |( C ) |= | C | . A l s o , a s u b s p a c e c o d e c o n s t r u c t e d b y l i f t i n g i s a G r a s sm a n n i a n c o d e , w i t h e a c h co d ew o r d h a v i n g d im e n s i o nn . T h e k e y f e a t u r e o f t h e l i f t i n g b a s e d c o n s t r u c t i o n i s t h a t t h e G r a s sm a n n i a n c o d e c o n s t r u c t e d b y l i f t i n g i n h e r i t s t h e d i s t a n c e p r o p e r t i e s o f i t s u n d e r l y i n g r a n k -m e t r i c c o d e . M o r e s p e c i fi c a l l y , w e h a v e t h e f o l l ow

N e x t , w e s h ow t h a t t h e l i f t i n g c o n s t r u c t i o n g i v e n i n ( 2 2 ) p r e s e r v e s t h e l o c a l i t y p r o p e r t y . 6 I t i s w o r t h n o t i n g t h a t t h e d e fi n i t i o n o f t h e l i f t i n g o p e r a t i o n i s a d a p t e d t o o u r n o t a t i o n . I n [ 3 7 ] , S i l v ae t a l .d e fi n e t h e l i f t i n g o f a nm×nm a t r i x Xa s t h e r o w s p a c e o f t h e m a t r i x[ I X ] , w h e r eIi s a nm×m i d e n t i t y m

c o d eCa s g i v e n i n C o n s t r u c t i o n 1 . T h e n , e a c h o f t h ens e r v e r s s t o r e s a c o l um n o f t h e c o d e w o r d m a t r i x . L e tC ( j -1 ) ( r +δ -1 ) +i d e n o t e t h e v e c t o r s t o r e d o n t h ei -t h s e r v e r i n t h ej -t h r a c k . L e t I l d e n o t e t h el -t h c o l um n o f t h en×ni d e n t i t y m a t r i x . T h e n , e a c h s e r v e rii n t h ej -t h r a c k s e n d s a p a c k e tX

L e t u s b e g i n w i t h t h e d e fi n i t i o n

o f l i n e a r i z e d p o l y n om i a l s . R e c a l l t h a tx q i =x [ i ] .

D e fi n i t i o n 7( L i n e a r i z e d P o l y n om i a l ) . ( [ 6 2 ] ) A p o l y n om i a l i n

i s c a l l e d a s a l i n e a r i z e d p o l y n om i a l o r a q -p o l y n om i a l o v e r F q m.F u r t h e r , m a x{ i ∈ [ n ] : a i =0 } i s s a i d t o b e t h e q -d e g r e e o f L ( x )d e n o t e d a sd e g q ( L ( x ) ) .

T h e n am e a r i s e s f r om t h e f o l l ow i n g p r o p e r t y o f l i n e a r i z e d p o l y n om i a l s , r e f e r r e d t o a sF q -l i n e a r i t y o v e r t h e fi n i t e fi e l dF q f o rq≥ ni s t h e s e t o f e v a l u a t i o n s o f a l l p o l y n om i a l s o f d e g r e e a t m o s tk-1 o v e rnd i s t i n c t e l em e n t s o fF q . M o r e s p e c i fi c a l l y , l e t P= {γ 1 , • • • , γ n }b e a s e t o f nd i s t i n c t e l em e n t s o fF q ( q≥n ) . C o n s i d e r p o l y n om i a l s g m ( x ) ∈F q [ x ] w i t h c o e f fi c i e n t sm = L emm a 5 . L e t P b e a s e t o f n e l em e n t s i nF q m t h a t a r e l i n e a r l y i n d e p e n d e n t o v e r F q (m ≥n ) . C o n s i d e r a l i n e a r i z e d p o l y n om i a l L m ( x ) ∈F q m[ x ] o f t h e f o l l o w i n g f o rm

w h e r e i j ' s a r e n o n -n e g a t i v e i n t e g e r s s u c h t h a t 0≤i 1 <i 2 < ( 4 1 ) B y u s i n g F q -l i n e a r i t y p r o p e r t y o f l i n e a r i z e d p o l y n om i a l s ( s e e ( 2 8 ) , ( 2 9 ) ) , t h e a b o v e s e t o f e q u a t i o n s ( 4 1 ) i s e q u i v a l e n t t o

c l j γ j +c l w r +1 γ w r +l ⎞ ⎠ =0 , f o r 1 ≤l ≤w-w r .

(

T h e r e f o r e , w r j =1 c l j γ j +c l w r +1 γ w r +l , 1≤l ≤w-w r a r e a l s o t h e r o o t s o fL m c ( x ) . T o g e t h e r w i t h { γ w+1 , . . . , γ n }a s i t s r o o t s ,L m c ( x )h a sn-w r > i k r o o t s . N o t e t h a t , s i n c eγ j ' s a r e l i n e a r l y i n d e p e n d e n t o v e rF q ,s oa r ea l lo ft h en-w r r o o t s . T h u s ,L m c ( x )h a s m o r e t h a ni k r o o t s t h a t a r e l i n e a r l y i n d e p e n d e n t o v e rF q , w h i c h i ACKNOWLEDGMENT P a r t o f t h i s w o r k w a s d o n e d u r i n g t h e a u t h o r s ' s t a y a t t h e I n s t i t u t H e n r i P o i n c a r é -C e n t r e Ém i l e B o r e l . T h e a u t h o r s t h a n k t h i s i n s t i t u t i o n f o r h o s p i t a l i t y a n d s u p p o r t .

RE F ER ENC E S

[ 1 ] A . R o w s t r o n a n d P . D r u s c h e l , " S t o r a g e m a n a g em e n t a n d c a c h i n g i n P A S T , a l a r g e -s c a l e , p e r s i s t e n t p e e r -t o -p e e r s t o r a g e u t i l i t y , "A CM S IGO P S O p e r . S y s t . R e v . , v o l .