A random code has, with high probability, constant rate and distance, but locality that is proportional to the length. This is true even for random LDPC codes [1]}, and a priori the mere existence of codes with constant locality is not obvious. The first LTCs appear implicitly in works on program checking [2]} and on probabilistically checkable proofs (PCPs) [3]}, [4]}, [5]}, [6]}, [7]}. A formal definition of an LTC appeared simultaneously in several places [5]}, [9]}, [10]}, [11]} (see [12]} for a detailed history).
