We consider the distributed message-passing model and the Local Computational Algorithms (LCA) model. In both models a network is represented by an n -vertex graph G = ( V , E ) . We focus on labeling problems, such as vertex-coloring, edge-coloring, maximal independent set (MIS) and maximal matching. In the distributed model the vertices of v perform computations in parallel in order to compute their own solution for solving the problem for G . In contrast, in the LCA model probes are performed on certain vertices in order to compute their labels in a solution to a given problem. In this work we study the possibility of estimating a solution produced by an algorithm, much before the algorithm terminates. This estimation not only allows for size approximation of a solution, but also for early detection of failure in randomized algorithms. We do this such that a correcting procedure can be executed. To this end, we propose a sampling technique, in which the labels in the sampling are distributed proportionally to the distribution in the algorithm's output. However, the sampling running time is significantly smaller than that of the algorithm in hand. We achieve the following results, in terms of the maximum degree Δ and the arboricity a of the input graph. The running time of our procedures is O ( log ⁡ a + log ⁡ log ⁡ n ) , for sampling vertex-coloring, edge-coloring, maximal matching and MIS. This significantly improves upon previous sampling techniques, which incur additional dependency on the maximum degree Δ that can be much higher than the arboricity, as well as more significant dependency on n . Not only that, we also show that our technique extends naturally for the power graph G r for any constant integer r > 1 for the problems of MIS and coloring. Our techniques for sampling in the distributed model provide a powerful and general tool for estimation in the LCA model. In this setting the goal is estimating the size of a solution to a given problem, by making as few vertex probes as possible. For the above-mentioned problems, we achieve estimations with probe complexity d O ( log ⁡ a + log ⁡ log ⁡ n ) , where d = m i n ( Δ , a ⋅ p o l y ( log ⁡ ( n ) ) . Our results extend as well to power graphs for the coloring and MIS problems.

We obtain improved distributed algorithms in the CONGEST message-passing setting for problems on power graphs of an input graph G. This includes Coloring, Maximal Independent Set, and related problems. For R = f(Δ^k,n), we develop a general deterministic technique that transforms R-round LOCAL model algorithms for G^k with certain properties into O(R ⋅ Δ^{k/2-1})-round CONGEST algorithms for G^k. This improves the previously-known running time for such transformation, which was O(R⋅Δ^{k-1}). Consequently, for problems that can be solved by algorithms with the required properties and within polylogarithmic number of rounds, we obtain quadratic improvement for G^k and exponential improvement for G². We also obtain significant improvements for problems with larger number of rounds in G. Notable implications of our technique are the following deterministic distributed algorithms: - We devise a distributed algorithm for O(Δ⁴)-coloring of G² whose number of rounds is O(log Δ + log^* n). This improves exponentially (in terms of Δ) the best previously-known deterministic result of Halldorsson, Kuhn and Maus.[M. M. Halldorson et al., 2020] that required O(Δ + log^{*}n) rounds, and the standard simulation of Linial [N. Linial, 1992] algorithm in G^k that required O(Δ ⋅ log^* n) rounds. - We devise an algorithm for O(Δ²)-coloring of G² with O(Δ ⋅ log Δ + log^*n) rounds, and (Δ²+1)-coloring with O(Δ^{1.5} ⋅ log Δ + log^*n) rounds. This improves quadratically, and by a power of 4/3, respectively, the best previously-known results of Halldorsson, Khun and Maus. [M. M. Halldorson et al., 2020]. - For k > 2, our running time for O(Δ^{2k})-coloring of G^k is O(k⋅Δ^{k/2-1}⋅log Δ⋅log^* n). Our running time for O(Δ^k)-coloring of G^k is Õ(k⋅Δ^{k-1}⋅log^* n). This improves best previously-known results quadratically, and by a power of 3/2, respectively. - For constant k > 2, our upper bound for O(Δ^{2k})-coloring of G^k nearly matches the lower bound of Fraigniaud, Halldorsson and Nolin. [P. Fraigniaud et al., 2020] for checking the correctness of a coloring in G^k.

For synchronization purposes, most applications require data to be transferred onto a cloud or shared with other edge devices. Transferring data between edge devices using wireless connectivity consumes power and bandwidth; therefore it is crucial to transmit a minimal amount of data. This poster presents an efficient method and preliminary analysis for minimizing data flow between edge devices and experimental results on the amount of transmitted data with radio use of [EQUATION], where n is the maximum difference between wake-up times and m is the number of devices that wake up at arbitrary time points. Besides the amount of data, our approach also focuses on the radio use of each device.

We consider graph coloring and related problems in the distributed message-passing model.Locally-iterative algorithmsare especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its1-hop-neighborhood. In STOC’93 Szegedy and Vishwanathan showed that any locally-iterative Δ + 1-coloring algorithm requires Ω (Δ log Δ + log*n) rounds, unless there exists “a very special type of coloring that can be very efficiently reduced” [ 44 ]. No such special coloring has been found since then. This led researchers to believe that Szegedy-Vishwanathan barrier is an inherent limitation for locally-iterative algorithms and to explore other approaches to the coloring problem [ 2 , 3 , 19 , 32 ]. The latter gave rise to faster algorithms, but their heavy machinery that is of non-locally-iterative nature made them far less suitable to various settings. In this article, we obtain the aforementioned special type of coloring. Specifically, we devise a locally-iterative Δ + 1-coloring algorithm with running timeO(Δ + log*n), i.e.,belowSzegedy-Vishwanathan barrier. This demonstrates that this barrier is not an inherent limitation for locally-iterative algorithms. As a result, we also achieve significant improvements for dynamic, self-stabilizing, and bandwidth-restricted settings. This includes the following results: We obtain self-stabilizing distributed algorithms for Δ + 1-vertex-coloring, (2Δ - 1)-edge-coloring, maximal independent set, and maximal matching withO(Δ + log*n) time. This significantly improves previously known results that haveO(n)or larger running times [ 23 ]. We devise a (2Δ - 1)-edge-coloring algorithm in the CONGEST model withO(Δ + log*n) time andO(Δ)-edge-coloring in the Bit-Round model withO(Δ + logn) time. The factors of log*nand lognare unavoidable in the CONGEST and Bit-Round models, respectively. Previously known algorithms had superlinear dependency on Δ for (2Δ - 1)-edge-coloring in these models. We obtain an arbdefective coloring algorithm with running timeO(√ Δ + log*n). Such a coloring is not necessarily proper, but has certain helpful properties. We employ it to compute a proper (1 + ε)Δ-coloring withinO(√ Δ + log*n) time and Δ + 1-coloring withinO(√ Δ log Δ log*Δ + log*n) time. This improves the recent state-of-the-art bounds of Barenboim from PODC’15 [ 2 ] and Fraigniaud et al. from FOCS’16 [ 19 ] by polylogarithmic factors. Our algorithms are applicable to the SET-LOCAL model [ 25 ] (also known as the weak LOCAL model). In this model a relatively strong lower bound of Ω (Δ1/3) is known for Δ + 1-coloring. However, most of the coloring algorithms do not work in this model. (In Reference [ 25 ] only Linial’sO(Δ2)-time algorithm and Kuhn-WattenhoferO(Δ log Δ)-time algorithms are shown to work in it.) We obtain the first linear-in-Δ Δ + 1-coloring algorithms that work also in this model.

In this paper we provide a deterministic scheme for solving any decidable problem in the distributed sleeping model. The sleeping model [Valerie King et al., 2011; Soumyottam Chatterjee et al., 2020] is a generalization of the standard message-passing model, with an additional capability of network nodes to enter a sleeping state occasionally. As long as a vertex is in the awake state, it is similar to the standard message-passing setting. However, when a vertex is asleep it cannot receive or send messages in the network nor can it perform internal computations. On the other hand, sleeping rounds do not count towards awake complexity. Awake complexity is the main complexity measurement in this setting, which is the number of awake rounds a vertex spends during an execution. In this paper we devise algorithms with worst-case guarantees on the awake complexity. We devise a deterministic scheme with awake complexity of O(log n) for solving any decidable problem in this model by constructing a structure we call Distributed Layered Tree. This structure turns out to be very powerful in the sleeping model, since it allows one to collect the entire graph information within a constant number of awake rounds. Moreover, we prove that our general technique cannot be improved in this model, by showing that the construction of distributed layered trees itself requires Ω(log n) awake rounds. This is obtained by a reduction from message-complexity lower bounds, which is of independent interest. Furthermore, our scheme also works in the CONGEST setting where we are limited to messages of size at most O(log n) bits. This result is shown for a certain class of problems, which contains problems of great interest in the research of the distributed setting. Examples for problems we can solve under this limitation are leader election, computing exact number of edges and average degree. Another result we obtain in this work is a deterministic scheme for solving any problem from a class of problems, denoted O-LOCAL, in O(log Δ + log^*n) awake rounds. This class contains various well-studied problems, such as MIS and (Δ+1)-vertex-coloring. Our main structure in this case is a tree as well, but is sharply different from a distributed layered tree. In particular, it is constructed in the local memory of each processor, rather than distributively. Nevertheless, it provides an efficient synchronization scheme for problems of the O-LOCAL class.

We study algorithms in the distributed message-passing model that produce secured output, for an input graph $G$. Specifically, each vertex computes its part in the output, the entire output is correct, but each vertex cannot discover the output of other vertices, with a certain probability. This is motivated by high-performance processors that are embedded nowadays in a large variety of devices. In such situations, it no longer makes sense, and in many cases it is not feasible, to leave the whole processing task to a single computer or even a group of central computers. As the extensive research in the distributed algorithms field yielded efficient decentralized algorithms for many classic problems, the discussion about the security of distributed algorithms was somewhat neglected. Nevertheless, many protocols and algorithms were devised in the research area of secure multi-party computation problem (MPC or SMC). However, the notions and terminology of these protocols are quite different than in classic distributed algorithms. As a consequence, the focus in those protocols was to work for every function $f$ at the expense of increasing the round complexity, or the necessity of several computational assumptions. In this work, we present a novel approach, which rather than turning existing algorithms into secure ones, identifies and develops those algorithms that are inherently secure (which means they do not require any further constructions). This approach yields efficient secure algorithms for various locality problems, such as coloring, network decomposition, forest decomposition, and a variety of additional labeling problems. Remarkably, our approach does not require any hardness assumption, but only a private randomness generator in each vertex. This is in contrast to previously known techniques in this setting that are based on public-key encryption schemes.

We consider the distributed synchronous message passing model, also known as theLOCALmodel. In this model the input graphGrepresents a network, where each vertex in the graph is a processor and each edge is a communication line between two processors. Symmetry-breaking problems are among the most studied problems in this model [4], [7], [9]-[11], [13], [17], [18], [23], [24], [26]. In this paper we devise a general method for solving symmetry breaking problems in graphs with boundeddiversity. Roughly speaking, the diversity of a graph is the maximum number of maximal cliques a vertex belongs to. This general method uses a new approach which utilizes a structure calleda connector. We build a series of such connectors, each of which simplifies the previous one by decreasing maximum clique size. Eventually, cliques becomes sufficiently small and have some additional properties that allow us to bound the maximum degree of the connectors. Then it becomes possible to employ efficient symmetry-breaking algorithms for bounded-degree graphs and extend the results to all the connectors in the series in backward order, until we reach a solution for the original graph. We use the ideas of this general method to achieve the following results. First, we devise an improved algorithm for maximal matching with running time ofO(log(S)(D(G) + log*n)), whereD(G) is the diversity ofGandS(G) is the maximum clique size. The best currently-known deterministic result for general graphs isO(log2Δlogn) [13]. This result is also the best currently-known for graphs with bounded diversity, hence our result constitutes an improvement for graphs withD(G) =o(log Δ logn). Another algorithm of ours for the same problem has a running time ofO(D(G)2+ log*n). For graphs withD(G) =O(1) this shows a separation of complexities between the maximal matching problem and the maximal independent set problem. Indeed, in such graphs our algorithm computes a maximal matching withinO(log*n) time, while computing a maximal independent set requires Ω(√(logn/ log logn)) time. This is the first result for any family of graphs that shows that maximal matching is provably easier than maximal independent set in the distributed setting. Moreover, using the same methods, we devise improved algorithms for ruling sets in graphs with bounded diversity. We also obtain an improved result for the wider family of graphs with bounded neighborhood independence ℓ. Specifically, we compute a maximal matching withinO(ℓ log Δ + log*n) time in such graphs.

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. Often this is a reasonable measure, but 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 \citeFeuilloley2017. In this measure, the running time is the worst-case average of rounds over the number of vertices. Feuilloley \citeFeuilloley2017 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 O (log* n) [9]. 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 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. For example, for general graphs, we devise an O(a^2 )-vertex-coloring algorithm with vertex-averaged complexity of O(loglog n), 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 \citeBarenboim2008.

Considering their independent and environmentally-varied work-fashion, one of the most important factors in WSN applications is fault-tolerance. Due to the fact that the possibilities of an absent sensor node, damaged communication link or missing data are unavoidable in wireless sensor networks, fault-tolerance becomes a key-issue. Among the causes of these constant failures are environmental factors, battery exhaustion, damaged communications links, data collision, wear-out of memory and storage units and overloaded sensors.

Energy efficiency is a crucial performance metric in sensor networks, directly determining the network lifetime. Consequently, a key factor in WSN is to improve overall energy efficiency to extend the network lifetime. Although many algorithms have been presented to optimize the energy factor, energy efficiency is still one of the major problems of WSNs, especially when there is a need to sample an area with different types of loads. Unlike other energy-efficient schemes for hierarchical sampling, our hypothesis is that it is achievable, in terms of prolonging the network lifetime, to adaptively re-modify CHs sensing rates (the processing and transmitting stages in particular) in some specific regions that are triggered significantly less than other regions. In order to do so we introduce the Adaptive Distributed Hierarchical Sensing (ADHS) algorithm. This algorithm employs a homogenous sensor network in a distributed fashion and changes the sampling rates of the CHs based on the variance of the sampled data without damaging significantly the accuracy of the sensed area.

In the distributed message-passing setting a communication network is represented by a graph whose vertices represent processors that perform local computations and communicate over the edges of the graph. In the distributed edge-coloring problem the processors are required to assign colors to edges, such that all edges incident on the same vertex are assigned distinct colors. The previously-known deterministic algorithms for edge-coloring employed at least (2Δ - 1) colors, even though any graph admits an edge-coloring with Δ + 1 colors [36]. Moreover, the previously-known deterministic algorithms that employed at most O(Δ) colors required superlogarithmic time [3,6,7,17]. In the current paper we devise deterministic edge-coloring algorithms that employ only Δ + o(Δ) colors, for a very wide family of graphs. Specifically, as long as the arboricity a of the graph is a = O(Δ1 - ε), for a constant ε > 0, our algorithm computes such a coloring within polylogarithmic deterministic time. We also devise significantly improved deterministic edge-coloring algorithms for general graphs for a very wide range of parameters. Specifically, for any value κ in the range [4Δ, 2o(log Δ) ⋅ Δ], our κ-edge-coloring algorithm has smaller running time than the best previously-known κ-edge-coloring algorithms. Our algorithms are actually much more general, since edge-coloring is equivalent to vertex-coloring of line graphs. Our method is applicable to vertex-coloring of the family of graphs with bounded diversity that contains line graphs, line graphs of hypergraphs, and many other graphs. We significantly improve upon previous vertex-coloring of such graphs, and as an implication also obtain the improved edge-coloring algorithms for general graphs.

Memory and storage are often assumed to be unsophisticated, flat resources, with simple properties, such as a constant access time. Over the years this assumption has been proven to be wrong, and understanding of the memory hierarchy could be useful in order to enhance the performance of an algorithm or a data structure [1]. For example, the Storage Class Memory (SCM) is a new technology which represents a new hybrid form of storage and memory with uniqe characteristics, meaning a memory which is non-volatile, cheap in per bit cost, has fast access times for both read and writes using cache line access, and is solid state. Also, the SCM is supposed to have different versions with different access speeds and volumes, meaning that it might be possible to add different SCM devices to the memory hierarchy as an extension of the RAM, and manage this enlarged main memory complex using special algorithms [2].

We study the distributed (Δ + 1)-vertex-coloring and (2Δ − 1)-edge-coloring problems. These problems are among the most important and intensively studied problems in distributed computing. Despite very intensive research in the last 30 years, no deterministic algorithms for these problems with sublinear (in Δ) time have been known so far. Moreover, for more restricted scenarios and some related problems there are lower bounds of Ω(Δ) [Göös et al. 2014; Hirvonen and Suomela 2012; Kuhn and Wattenhofer 2006; Szegedy and Vishwanathan 1993]. The question of the possibility to devise algorithms that overcome this challenging barrier is one of the most fundamental questions in distributed symmetry breaking [Barenboim and Elkin 2009, 2011; Göös et al. 2014; Hirvonen and Suomela 2012; Kuhn 2009; Panconesi and Rizzi 2001]. In this article, we settle this question for (Δ + 1)-vertex-coloring and (2Δ − 1)-edge-coloring by devising deterministic algorithms that require O (Δ 3/4 log Δ + log * n ) time in the static, dynamic, and faulty settings. (The term log * n is unavoidable in view of the lower bound of Linial [1987].) Moreover, for (1 + o (1))Δ-vertex-coloring and (2 + o (1))Δ-edge-coloring we devise algorithms with Õ(√Δ + log * n ) deterministic time. This is roughly a quadratic improvement comparing to the state-of-the-art that requires O (Δ + log * n ) time [Barenboim and Elkin 2009; Kuhn 2009; Panconesi and Rizzi 2001]. Our results are actually more general than that since they apply also to a variant of the list-coloring problem that generalizes ordinary coloring. Our results are obtained using a novel technique for coloring partially colored graphs (also known as fixing ). We partition the uncolored parts into a small number of subgraphs with certain helpful properties. Then we color these subgraphs gradually using a technique that employs constructions of polynomials in a novel way. Our construction is inspired by the algorithm of Linial [1987] for ordinary O (Δ 2 )-coloring. However, it is a more sophisticated construction that differs from that of Linial [1987] in several important respects. These new insights in using systems of polynomials allow us to significantly speed up the O (Δ)-coloring algorithms. Moreover, they allow us to devise algorithms with the same running time also in the more complicated settings of dynamic and faulty networks.

Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following: —An MIS algorithm running in O (log 2 Δ + 2 o (√log log n ) ) time, where Δ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when log n ≪ Δ ≪ 2√log n , and comes close to the Ω(log Δ / log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer. —A maximal matching algorithm running in O (log Δ + log 4 log n ) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on Δ is nearly optimal . —A (Δ + 1)-coloring algorithm requiring O (log Δ + 2 o (√log log n ) time, improving on an O (log Δ + √log n )-time algorithm of Schneider and Wattenhofer. —A method for reducing symmetry-breaking problems in low arboricity/degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O (√log n )-time maximal matching algorithm for graphs with arboricity up to 2√log n and an O (log 2/3 n )-time MIS algorithm for graphs with arboricity up to 2 (log n )1/3 . Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetry-breaking task to a corresponding deterministic one on a poly(log n )-size graph.

In the distributed message passing model a communication network is represented by an n-vertex graph G = (V,E) of maximum degree Δ. Computation proceeds in discrete synchronous rounds consisting of sending and receiving messages and performing local computations. The running time of an algorithm is the number of rounds it requires. In the static setting the network remains unchanged throughout the entire execution. In the dynamic setting the topology of the network changes, and a new solution has to be computed after each change. In the faulty setting the network is static, but some vertices or edges may lose the computed solution as a result of faults. The goal of an algorithm in this setting is fixing the solution. The problems of (Δ + 1)-vertex-coloring and (2Δ - 1)-edge-coloring are among the most important and intensively studied problems in distributed computing. Despite a very intensive research in the last 30 years, no deterministic algorithms for these problems with sublinear (in Δ) time have been known so far. Moreover, for more restricted scenarios and some related problems there are lower bounds of Ω(Δ) [13, 14, 20, 27]. The question of the possibility to devise algorithms that overcome this challenging barrier is one of the most fundamental questions in distributed symmetry breaking [4, 6, 13, 14, 19, 24]. In this paper we settle this question for (Δ + 1)-vertex-coloring and (2Δ - 1)-edge-coloring by devising deterministic algorithms that require O(Δ3/4 log Δ + log* n) time in the static, dynamic and faulty settings. (The term log* n is unavoidable in view of the lower bound of Linial [21]. Moreover, for (1 + o(1))Δ-vertex-coloring and (2 + o(1))Δ-edge-coloring we devise algorithms with Õ(√Δ + log* n) deterministic time. This is roughly a quadratic improvement comparing to the state-of-the-art that requires O(Δ + log* n) time [4, 19, 24]. Our results are actually more general than that since they apply also to a variant of the list-coloring problem that generalizes ordinary coloring.

The distributed $(\Delta + 1)$-coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of gradually improving algorithms has been published. The state-of-the-art running time, prior to our work, is $O(\Delta \log \Delta + \log^* n)$, due to Kuhn and Wattenhofer [Proceedings of the $25$th Annual ACM Symposium on Principles of Distributed Computing, Denver, CO, 2006, pp. 7--15]. Linial [Proceedings of the $28$th Annual IEEE Symposium on Foundation of Computer Science, Los Angeles, CA, 1987, pp. 331--335] proved a lower bound of $\frac{1}{2} \log^* n$ for the problem, and Szegedy and Vishwanathan [Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, 1993, pp. 201--207] provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve a running time smaller than $\Theta(\Delta \log \Delta)$. We present a deterministic $(\Delta + 1)$-coloring distributed algorithm with running time $O(\Delta) + \frac{1}{2} \log^* n$. We also present a trade-off between the running time and the number of colors, and devise an $O(\lambda\cdot\Delta)$-coloring algorithm, with running time $O(\Delta / \lambda + \log^* n)$, for any parameter $\lambda > 1$. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan and achieves running time which is linear in the maximum degree $\Delta$. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm does not belong to the family of locally iterative algorithms. On the way to this result we study a generalization of the notion of graph coloring, which is called defective coloring [L. Cowen, R. Cowen, and D. Woodall, J. Graph Theory, 10 (1986), pp. 187--195]. In an $m$-defective $p$-coloring the vertices are colored with $p$ colors so that each vertex has up to $m$ neighbors with the same color. We show that an $m$-defective $p$-coloring with reasonably small $m$ and $p$ can be computed very efficiently in the distributed setting. We also develop a technique to employ multiple defective colorings of various subgraphs of the original graph $G$ for computing a $(\Delta+1)$-coloring of $G$. We believe that these techniques are of independent interest.

We consider the problem of clock synchronization in a wireless setting where processors must minimize the number of times their radios are used to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited, as occurs in sensor and ad hoc networks, and in many other settings. The problem of clock synchronization is fundamental and intensively studied in the field of distributed algorithms. In the current setting, the problem is to synchronize clocks of m processors that wake up in arbitrary time points, such that the maximum difference between wake-up times is bounded by a positive integer n . (Time intervals are appropriately discretized to allow communication of all processors that are awake in the same discrete time unit.) Currently, the best-known results for synchronization for single-hop networks of m processors is a randomized algorithm due to Bradonjic et al. [2009] of O (√ n / m ⋅ poly - log ( n )) radio use times per processor, and a lower bound of Ω (√ n / m ). The main open question left in their work is to close the poly-log gap between the upper and the lower bound, and to derandomize their probabilistic construction and eliminate error probability. This is exactly what we do in this article. That is, we show a deterministic algorithm with radio use of Θ (√ n / m ), which exactly matches the lower bound proven in Bradonjic et al. [2009] to a small multiplicative constant. Therefore, our algorithm is optimal in terms of energy efficiency and completely resolves a long sequence of works in this area [Bradonjic et al. 2009; Moscribroda et al. 2006; McGlynn and Borbash 2001; Polastre et al. 2004]. Moreover, our algorithm is optimal in terms of running time as well. To achieve these results, we devise a novel adaptive technique that determines the times when devices power their radios on and off. This technique may be of independent interest. In addition, we prove several lower bounds on the energy efficiency of algorithms for multihop networks. Specifically, we show that any algorithm for multihop networks must have radio use of Ω (√ n ) per processor. Our lower bounds hold even for specific kinds of networks, such as networks modeled by unit disk graphs and highly connected graphs. Our results imply that the simple deterministic algorithm devised for two-processor networks in Bradonjic et al. [2009] with efficiency O (√ n ) can be used in multihop networks, and it is the most efficient solution in terms of energy use.

We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. A sampling of the results include 1) A randomized algorithm for computing a maximal matching (MM) in O(log Δ + (log log n)4) rounds, where Δ is the maximum degree. This improves a 25-year old randomized algorithm of Israeli and Itai that takes O(log n) rounds and is provably optimal for all log Δ in the range [(log log n)4, √log n]. 2) A randomized maximal independent set (MIS) algorithm requiring O(log Δ√log n) rounds, for all Δ, and only 2O(√log log n) rounds when Δ = poly(log n). These improve on the 25-year old O(log n)-round randomized MIS algorithms of Luby and Alon, Babai, and Itai when log Δ ≫ √log n. 3) A randomized (Δ + 1)-coloring algorithm requiring O(log Δ + 2O((√log log n)) rounds, improving on an algorithm of Schneider and Wattenhofer that takes O(log Δ + √log n) rounds. This result implies that an O(Δ)-coloring can be computed in 2O(√log log n)rounds for all Δ, improving on Kothapalli et al.'s O(√log n)-round algorithm. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e.g., planar graphs and graphs that exclude any fixed minor) requiring O(√log n) and O(log2/3n) rounds w.h.p., respectively.

We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2Δ-1)-edge-coloring requires O(Δ) + log* n time [23], where Δ is the maximum degree of the input graph. Also, recent results of [5] for vertex-coloring imply that one can get an O(Δ)-edge-coloring in O(Δµ" log n) time, and an O(Δ1 + µ)-edge-coloring in O(log Δ log n) time, for an arbitrarily small constant µ > 0.

Consider an n -vertex graph G = ( V , E ) of maximum degree Δ , and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G . The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color G with Δ + 1, or slightly more than Δ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time .) Efficient randomized algorithms for this problem are known for more than twenty years [Alon et al. 1986; Luby 1986]. Specifically, these algorithms produce a ( Δ + 1)-coloring within O (log n ) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O ( Δ 2 ) colors. This algorithm was devised in a seminal FOCS’87 paper by Linial [1987]. Its running time is O (log * n ). In the same article, Linial asked whether one can color with significantly less than Δ 2 colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area. In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ 1+ o (1) colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O ( f ( Δ )log Δ log n ), for an arbitrarily slow-growing function f ( Δ ) = ω (1). We can also produce an O ( Δ 1+ η )-coloring in O (log Δ log n )-time, for an arbitrarily small constant η > 0, and an O ( Δ )-coloring in O ( Δϵ log n ) time, for an arbitrarily small constant ϵ > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity a , our algorithm produces an O ( a 1+ η )-coloring, for an arbitrarily small constant η > 0, in time O (log a log n ).

Consider an n-vertex graph G = (V,E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, i.e., it proceeds in discrete rounds.

The distributed ( ∆ + 1)-coloring problem is one of most fundamental and well-studied problems of Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current state-of-the-art running time is O(∆log ∆ + log ∗ n), due to Kuhn and Wattenhofer, PODC’06. Linial (FOCS’87) has proved a lower bound of 1 2 log ∗ n for the problem, and Szegedy and Vishwanathan (STOC’93) provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve running time smaller than Θ(∆log ∆). We present a deterministic (∆+1)-coloring distributed algorithm with running time O(∆)+ 1 2 log ∗ n. We also present a tradeoff between the running time and the number of colors, and devise an O( ∆ 1+ǫ)-coloring algorithm with running time O( ∆ 1−ǫ +log ∗ n), for any constant ǫ, 0 < ǫ ≤ 1/4. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan, and achieves running time which is linear in the maximum degree ∆. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm is not from the family of locally iterative algorithms. On the way to this result we introduce a generalization of the notion of graph coloring, which we call relaxed coloring. In an m-relaxed p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-relaxed p-coloring with reasonably small m and p can be computed very efficiently. We also develop a technique to employ multiple relaxed colorings of various subgraphs of the original graph G for computing a ( ∆ + 1)-coloring of G. We believe that these techniques and the notion of relaxed coloring are of independent interest.

We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.