A Classification of Locality in Network Research

摘要

Limiting the knowledge of individual nodes is a major concern for the design of distributed algorithms. With the LOCAL model, theoretical research already established a common model of locality that has gained little practical relevance. As a result, practical research de facto lacks any common locality model. The only common denominator among practitioners is that a local algorithm is distributed with a restricted scope of interaction. This article closes the gap by introducing four practically motivated classes of locality that successively weaken the strict requirements of the LOCAL model. These classes are applied to categorize and survey 36 local algorithms from 12 different application domains. A detailed comparison shows the practicality of the classification and provides interesting insights. For example, the majority of algorithms limit the scope of interaction to at most two hops, independent of their locality class. Moreover, the application domain of algorithms tends to influence their degree of locality.