Conflict Checkable and Decodable Codes and Their Applications

Let C be an error-correcting code over a large alphabet q of block length n, and assume that, a possibly corrupted, codeword c is distributively stored among n servers where the ith entry is being held by the ith server. Suppose that every pair of servers publicly announce whether the corresponding coordinates are “consistent” with some legal codeword or “conflicted”. What type of information about c can be inferred from this consistency graph? Can we check whether errors occurred and if so, can we find the error locations and effectively decode? We initiate the study of conflict-checkable and conflict-decodable codes and prove the following main results: