We present a deterministicdistributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers o...
详细信息
ISBN:
(纸本)9781538634646
We present a deterministicdistributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2(O(root log n)) by Panconesi and Srinivasan [STOC' 92] and (O) over tilde (root Delta) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS' 16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2 Delta - 1)-edgecoloring to poly(log log n) rounds. The key technical ingredient is a deterministicdistributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Delta, this algorithm computes a maximal matching in O(r(5) log(6+log r) Delta . log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministicdistributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a ((log Delta/epsilon)(O(log 1/epsilon)) - round deterministic algorithm for (1 + epsilon)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministicdistributed algorithm for orienting lambda-arboricity graphs with out-degree at most inverted right perpendicular (1 + epsilon)lambda inverted left perpendicular, for any constant epsilon > 0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.
Leader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs leader and all...
详细信息
Leader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs leader and all other nodes output non-leader, or in a strong way, where all nodes must also learn which node is the leader. If the nodes of the network have distinct identifiers, then such an agreement means that all nodes have to output the identifier of the elected leader. For anonymous networks, the strong version of leader election requires that all nodes must be able to find a path to the leader, as this is the only way to identify it. In this paper, we study variants of deterministic leader election in arbitrary anonymous networks. Leader election is impossible in some anonymous networks, regardless of the allocated amount of time, even if nodes know the entire map of the network. This is due to possible symmetries in the network. However, even in networks in which it is possible to elect a leader knowing the map, the task may be still impossible without any initial knowledge, regardless of the allocated time. On the other hand, for any network in which leader election (weak or strong) is possible knowing the map, there is a minimum time, called the election index, in which this can be done. We consider four formulations of leader election discussed in the literature in the context of anonymous networks: one is the weak formulation, and the three others specify three different ways of finding the path to the leader in the strong formulation. Our aim is to compare the amount of initial information needed to accomplish each of these "four shades" of leader election in minimum time. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire network. The length of this string is called the size of advice. We show that the size of advice required to accomplish lea
In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique O(log n)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time di...
详细信息
In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique O(log n)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributedalgorithms) do not need such identifiers: a port numbering and orientation is sufficient. Our result holds for so-called simple PO-checkable graph optimisation problems;this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks. As a corollary of our result, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem. By prior work, there is a deterministic local algorithm that achieves the approximation factor of 4 -1/left perpendicular Delta/2right perpendicular in graphs of maximum degree Delta. This approximation ratio is known to be optimal in the port-numbering model-our main theorem implies that it is optimal also in the standard model in which each node has a unique identifier. Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is (alpha, r)-homogeneous if its nodes are linearly ordered so that an alpha fraction of nodes have pairwise isomorphic radius-r neighbourhoods. We show that there exists a finite (alpha, r)-homogeneous 2k-regular graph of girth at least g for any alpha < 1 and any r, k, and g.
暂无评论