اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNoisy Beeping Networks
53
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce noisy beeping networks, where nodes have limited communication capabilities, namely, they can only emit energy or sense the channel for energy. Furthermore, imperfections may cause devices to malfunction with some fixed probability when sensing the channel, which amounts to deducing a noisy received transmission. Such noisy networks have implications for ultra-lightweight sensor networks and biological systems. We show how to compute tasks in a noise-resilient manner over noisy beeping networks of arbitrary structure. In particular, we transform any algorithm that assumes a noiseless beeping network (of size $n$) into a noise-resilient version while incurring a multiplicative overhead of only $O(log n)$ in its round complexity, with high probability. We show that our coding is optimal for some tasks, such as node-coloring of a clique. We further show how to simulate a large family of algorithms designed for distributed networks in the CONGEST($B$) model over a noisy beeping network. The simulation succeeds with high probability and incurs an asymptotic multiplicative overhead of $O(Bcdot Delta cdot min(n,Delta^2))$ in the round complexity, where $Delta$ is the maximal degree of the network. The overhead is tight for certain graphs, e.g., a clique. Further, this simulation implies a constant overhead coding for constant-degree networks.
قيم البحث
اقرأ أيضاً
We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working
in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is $O(log^2 n)$, where $n$ is the size of the network. The total latency of our algorithm is $O(n log n)$ time steps. We observe that there exist families of network topologies for which both of these bounds are simultaneously optimal up to polylog factors, so any significant improvement will require additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present a decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog($n$) factor bigger that the optimum.
Given a set of $n$ points in a $d$-dimensional space, we seek to compute the skyline, i.e., those points that are not strictly dominated by any other point, using few comparisons between elements. We adopt the noisy comparison model [FRPU94] where co
mparisons fail with constant probability and confidence can be increased through independent repetitions of a comparison. In this model motivated by Crowdsourcing applications, Groz & Milo [GM15] show three bounds on the query complexity for the skyline problem. We improve significantly on that state of the art and provide two output-sensitive algorithms computing the skyline with respective query complexity $O(ndlog (dk/delta))$ and $O(ndklog (k/delta))$ where $k$ is the size of the skyline and $delta$ the expected probability that our algorithm fails to return the correct answer. These results are tight for low dimensions.
We study the problem of locating the source of an epidemic diffusion process from a sparse set of sensors, under noise. In a graph $G=(V,E)$, an unknown source node $v^* in V$ is drawn uniformly at random, and unknown edge weights $w(e)$ for $ein E$,
representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean $1$ and variance $sigma^2$. An algorithm then attempts to locate $v^*$ by picking sensor (also called query) nodes $s in V$ and being told the length of the shortest path between $s$ and $v^*$ in graph $G$ weighted by $w$. We consider two settings: static, in which all query nodes must be decided in advance, and sequential, in which each query can depend on the results of the previous ones. We characterize the query complexity when $G$ is an $n$-node path. In the static setting, $Theta(nsigma^2)$ queries are needed for $sigma^2 leq 1$, and $Theta(n)$ for $sigma^2 geq 1$. In the sequential setting, somewhat surprisingly, only $Theta(loglog_{1/sigma}n)$ are needed when $sigma^2 leq 1/2$, and $Theta(log log n)+O_sigma(1)$ when $sigma^2 geq 1/2$. This is the first mathematical study of source location under non-trivial amounts of noise.
The noisy broadcast model was first studied in [Gallager, TranInf88] where an $n$-character input is distributed among $n$ processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor b
roadcasts a single character, and each reception is corrupted independently at random with some probability $p$. [Gallager, TranInf88] gave an algorithm for all processors to learn the input in $O(loglog n)$ rounds with high probability. Later, a matching lower bound of $Omega(loglog n)$ was given in [Goyal, Kindler, Saks; SICOMP08]. We study a relaxed version of this model where each reception is erased and replaced with a `? independently with probability $p$. In this relaxed model, we break past the lower bound of [Goyal, Kindler, Saks; SICOMP08] and obtain an $O(log^* n)$-round algorithm for all processors to learn the input with high probability. We also show an $O(1)$-round algorithm for the same problem when the alphabet size is $Omega(mathrm{poly}(n))$.
We introduce NoisyNet, a deep reinforcement learning agent with parametric noise added to its weights, and show that the induced stochasticity of the agents policy can be used to aid efficient exploration. The parameters of the noise are learned with
gradient descent along with the remaining network weights. NoisyNet is straightforward to implement and adds little computational overhead. We find that replacing the conventional exploration heuristics for A3C, DQN and dueling agents (entropy reward and $epsilon$-greedy respectively) with NoisyNet yields substantially higher scores for a wide range of Atari games, in some cases advancing the agent from sub to super-human performance.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
