Abstract—THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. Motivated by distributed algorithms for fuzzy joins, the concept of edge-covering codes is defined. This definition is a generalization of the well-known concept of covering codes. Basic properties and bounds for the new concept with comparison to the associated properties and bounds for covering codes, are provided. In particular, the sphere covering bound and normal codes are generalized to this new concept