ﻻ يوجد ملخص باللغة العربية
Theoreticians have studied distributed algorithms in the radio network model for close to three decades. A significant fraction of this work focuses on lower bounds for basic communication problems such as wake-up (symmetry breaking among an unknown set of nodes) and broadcast (message dissemination through an unknown network topology). In this paper, we introduce a new technique for proving this type of bound, based on reduction from a probabilistic hitting game, that simplifies and strengthens much of this existing work. In more detail, in this single paper we prove new expected time and high probability lower bounds for wake-up and global broadcast in single and multichann
Linials seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least $log^*(n)/2 - 1$ communication rounds. We give a new simpler proof of this theorem.
One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the alg
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful spars
In this paper, we study lower bounds for randomized solutions to the maximal independent set (MIS) and connected dominating set (CDS) problems in the dual graph model of radio networks---a generalization of the standard graph-based model that now inc
Given a graph $G = (V,E)$, an $(alpha, beta)$-ruling set is a subset $S subseteq V$ such that the distance between any two vertices in $S$ is at least $alpha$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $beta$