OPTIMAL INFORMATION-DISPERSAL FOR INCREASING THE RELIABILITY OF A DISTRIBUTED SERVICE

This paper investigates the (m,n) information dispersal scheme (IDS) u sed to support fault-tolerant distributed servers in a distributed sys tem. In an (m, n)-IDS, a file M is broken into n pieces such that any m pieces collected suffice for reconstructing M. The reliability of an (m, n)-IDS is primarily determined by 3 important factors: n = inform ation dispersal degree (IDD), n/m = information expansion ratio (IER), P-a = success-probability of acquiring a correct piece. It is difficu lt to determine the optimal IDS with the highest reliability from very many choices. Our analysis shows: several novel features of (m, n)-ID S which can help reduce the complexity of finding the optimal IDS with the highest reliability; that an IDS with a higher IER might not have a higher reliability, even when P-s-->1. Based on the theorems given herein, we have developed a method that reduces the complexity for com puting the highest reliability from, O(v) [v = number of servers] to O (1) when the 'upper bound of the IER' = 1, orO(v(2)) to O(1) when the 'upper bound of the IER' > 1.