TU Darmstadt / ULB / TUbiblio

A Classification of Locality in Network Research

Stein, Michael and Fischer, Mathias and Schweizer, Immanuel and Mühlhäuser, Max (2017):
A Classification of Locality in Network Research.
In: ACM Computing Surveys, p. 37, 50, (4), DOI: 10.1145/3092693,
[Online-Edition: http://doi.acm.org/10.1145/3092693],
[Article]

Abstract

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.

Item Type: Article
Erschienen: 2017
Creators: Stein, Michael and Fischer, Mathias and Schweizer, Immanuel and Mühlhäuser, Max
Title: A Classification of Locality in Network Research
Language: English
Abstract:

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.

Journal or Publication Title: ACM Computing Surveys
Volume: 50
Number: 4
Uncontrolled Keywords: Local algorithms, localized algorithms
Divisions: 20 Department of Computer Science > Telecooperation
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > A: Construction Methodology > Subproject A1: Modelling
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > A: Construction Methodology
20 Department of Computer Science
DFG-Collaborative Research Centres (incl. Transregio)
Date Deposited: 10 Sep 2017 14:41
DOI: 10.1145/3092693
Official URL: http://doi.acm.org/10.1145/3092693
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item