Distributed symmetry-breaking with improved vertex-averaged complexity

Leonid Barenboim, Yaniv Tzur

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


We study the distributed message-passing model in which a communication network is represented by a graph G = (V, E). Usually, the measure of complexity that is considered in this model is the worst-case complexity, which is the largest number of rounds performed by a vertex v ∈ V. While often this is a reasonable measure, in some occasions it does not express sufficiently well the actual performance of the algorithm. For example, an execution in which one processor performs r rounds, and all the rest perform significantly less rounds than r, has the same running time as an execution in which all processors perform the same number of rounds r. On the other hand, the latter execution is less efficient in several respects, such as energy efficiency, task execution efficiency, local-neighborhood efficiency and simulation efficiency. Consequently, a more appropriate measure is required in these cases. Recently, the vertex-averaged complexity was proposed by [13]. In this measure, the running time is the worst-case average of rounds over the number of vertices. Feuilloley [13] showed that leader-election admits an algorithm with significantly better vertex-averaged complexity than worst-case complexity. On the other hand, for O(1)-coloring of rings, the worst-case and vertex-averaged complexities are the same. This complexity is Θ (log n) [13]. It remained open whether the vertex-averaged complexity of symmetry-breaking in general graphs can be better than the worst-case complexity. In this paper we devise symmetry-breaking algorithms with significantly improved vertex-averaged complexity for both general graphs, as well as specific graph families. Some algorithms of ours have significantly better vertex-averaged complexity than the best-possible worst case complexity. In particular, for general graphs, we devise an O(a)-forests-decomposition algorithm with a vertex-averaged complexity of O(1) rounds, where the arboricity a is the minimum number of forests that the graph's edges can be partitioned into. In the worst-case, this requires Ω(log n) rounds [10]. In addition, for graphs with constant arboricity a, we compute (∆ + 1)-vertex-coloring, Maximal Independent Set, Maximal Matching and (2∆ − 1)-edge-coloring, deterministically, with O (log n) vertex-averaged complexity. The best known deterministic algorithms for (∆ + 1)-coloring have time complexity Õ (√∆ + log n ) in the worst case [3, 14], and the best known Maximal Independent Set and Maximal Matching algorithms on these graphs have worst-case complexity at least plog n [10, 18]. In addition to deterministic algorithms, we devise randomized algorithms, in which the vertex-averaged bounds hold with high probability. In particular, we show that (∆ + 1)-coloring of general graphs requires O(1) vertex-averaged complexity, with high probability. This is in contrast to the worst case complexity, which is Ω (log n) even on rings [19].

שפה מקוריתאנגלית
כותר פרסום המארחICDCN 2019 - Proceedings of the 2019 International Conference on Distributed Computing and Networking
מוציא לאורAssociation for Computing Machinery
מספר עמודים10
מסת"ב (אלקטרוני)9781450360944
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 4 ינו׳ 2019
אירוע20th International Conference on Distributed Computing and Networking, ICDCN 2019 - Bangalore, הודו
משך הזמן: 4 ינו׳ 20197 ינו׳ 2019

סדרות פרסומים

שםACM International Conference Proceeding Series


כנס20th International Conference on Distributed Computing and Networking, ICDCN 2019

הערה ביבליוגרפית

Publisher Copyright:
© 2019 Association for Computing Machinery.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Distributed symmetry-breaking with improved vertex-averaged complexity'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי