Stein, Michael ; Fischer, Mathias ; Schweizer, Immanuel ; Mühlhäuser, Max (2017)
A Classification of Locality in Network Research.
In: ACM Computing Surveys, 50 (4)
doi: 10.1145/3092693
Artikel, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2017 |
| Autor(en): | Stein, Michael ; Fischer, Mathias ; Schweizer, Immanuel ; Mühlhäuser, Max |
| Art des Eintrags: | Bibliographie |
| Titel: | A Classification of Locality in Network Research |
| Sprache: | Englisch |
| Publikationsjahr: | November 2017 |
| Verlag: | ACM |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | ACM Computing Surveys |
| Jahrgang/Volume einer Zeitschrift: | 50 |
| (Heft-)Nummer: | 4 |
| DOI: | 10.1145/3092693 |
| Kurzbeschreibung (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. |
| Freie Schlagworte: | Local algorithms, localized algorithms |
| Zusätzliche Informationen: | Art.No.: 53 |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Telekooperation DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > A: Konstruktionsmethodik DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > A: Konstruktionsmethodik > Teilprojekt A1: Modellierung |
| Hinterlegungsdatum: | 10 Sep 2017 14:41 |
| Letzte Änderung: | 19 Aug 2021 10:49 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum