We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: -- We present a @math round deterministic algorithm for @math -edge-coloring, where @math denotes the maximum degree. Modulo the @math factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of @math -edge-coloring in @math rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. -- We show that sinkless orientation---i.e., orienting edges such that each node has at least one outgoing edge---on @math -regular graphs can be solved in @math rounds randomized and in @math rounds deterministically. These prove the corresponding lower bounds by [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of for @math -coloring @math -regular trees. -- We present a randomized @math round algorithm for orienting @math -arboricity graphs with maximum out-degree @math . This can be also turned into a decomposition into @math forests when @math and into @math pseduo-forests when @math . Obtaining an efficient distributed decomposition into less than @math forests was stated as the 10th open problem in the book by Barenboim and Elkin.
Throughout, we work with the standard distributed model called @math , due to Linial @cite_12 : The network is abstracted as a graph @math . There is one processor on each vertex, which initially knows only its neighbors. Per round, each processor can send one message to each of its neighbors.
@cite_12
2949310786 2068322213 1582638066 2045376554
In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the widely studied GOSSIP model of communication. In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round. This model contrasts with the much less restrictive LOCAL model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In this paper, we give an algorithm that solves the information dissemination problem in at most @math rounds in a network of diameter @math , withno dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of @math , which applies even in the LOCAL model. In fact, we prove that something stronger is true: any algorithm that requires @math rounds in the LOCAL model can be simulated in @math rounds in the GOSSIP model. We thus prove that these two models of distributed computation are essentially equivalent. In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the GOSSIP model of communication. In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round. This model contrasts with the much less restrictive LOCAL model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In the LOCAL model, this is quite simple: each node broadcasts all of its information in each round, and the number of rounds required will be equal to the diameter of the underlying communication graph. In the GOSSIP model, each node must independently choose a single neighbor to contact, and the lack of global information makes it difficult to make any sort of principled choice. As such, researchers have focused on the uniform gossip algorithm, in which each node independently selects a neighbor uniformly at random. When the graph is well-connected, this works quite well. In a string of beautiful papers, researchers proved a sequence of successively stronger bounds on the number of rounds required in terms of the conductance φ and graph size n, culminating in a bound of O(φ-1 log n). In this paper, we show that a fairly simple modification of the protocol gives an algorithm that solves the information dissemination problem in at most O(D + polylog (n)) rounds in a network of diameter D, with no dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of D, which applies even in the LOCAL model. In fact, we prove that something stronger is true: any algorithm that requires T rounds in the LOCAL model can be simulated in O(T + polylog(n)) rounds in the GOSSIP model. We thus prove that these two models of distributed computation are essentially equivalent. We study the problem of computing the diameter of a network in a distributed way. The model of distributed computation we consider is: in each synchronous round, each node can transmit a different (but short) message to each of its neighbors. We provide an Ω(n) lower bound for the number of communication rounds needed, where n denotes the number of nodes in the network. This lower bound is valid even if the diameter of the network is a small constant. We also show that a (3 2 − e)-approximation of the diameter requires Ω (√n + D) rounds. Furthermore we use our new technique to prove an Ω (√n + D) lower bound on approximating the girth of a graph by a factor 2 − e. In this paper, we prove a lower bound on the number of rounds required by a deterministic distributed protocol for broadcasting a message in radio networks whose processors do not know the identities of their neighbors. Such an assumption captures the main characteristic of mobile and wireless environments [3], i.e., the instability of the network topology. For any distributed broadcast protocol II, for any n and for any D ≤ n 2, we exhibit a network G with n nodes and diameter D such that the number of rounds needed by H for broadcasting a message in G is Ω(D log n). The result still holds even if the processors in the network use a different program and know n and D. We also consider the version of the broadcast problem in which an arbitrary number of processors issue at the same time an identical message that has to be delivered to the other processors. In such a case we prove that, even assuming that the processors know the network topology, Ω(n) rounds are required for solving the problem on a complete network (D=1) with n processors.