Beeping Network (BN) is a popular graph-based model of wireless computation, which applies the OR operation to one-bit messages sent simultaneously by neighbors. It admits fast (polylogarithmic in the number of nodes n) randomized solutions to many graph problems, but all known deterministic algorithms for non-trivial graph problems are at least polynomial in the maximum node degree Δ. We improve known results for deterministic algorithms by showing that this polynomial can be as low as Õ(Δ²). More precisely, we show how to simulate a single round of any CONGEST algorithm in any network in O(Δ² polylog n) beeping rounds, each accommodating at most one beep per node, even if the nodes intend to send different messages to different neighbors. This upper bound reduces polynomially the time for a deterministic simulation of CONGEST in a Beeping Network, comparing to the best known algorithms, and nearly matches the time obtained recently using randomization (up to a poly-logarithmic factor) as well as the lower bound. Specifically, any algorithm designed for the CONGEST networks can be run in BNs with O(Δ² polylog n) multiplicative overhead, e.g., we can now deterministically compute an MIS in any BN in O(Δ² polylog n) beeping rounds, improving the previous best Θ(Δ³)-round solution. For h-hop simulations, we prove a lower bound Ω(Δ^{h+1}), and we design a nearly matching algorithm that is able to "pipeline" the node-to-node information in a faster way than beeping layer-by-layer.

We consider a fundamental problem for communication in multi-hop wireless networks, called Distributed Link Scheduling (DLS): each node may have packet(s) addressed to some of its reachable neighbors and the goal is to deliver all packets to their destinations. The challenge in distributed realization of DLS is the interference between simultaneous transmissions.All efficiently scalable DLS solutions so far relied heavily on substantial amount of true randomness, which is, however, intrinsically difficult to get in wireless devices. Therefore, in this work we focus on deterministic solutions, their worst-case complexity measured in the number of communication rounds, and whether it could be improved for some classes of wireless network topologies. We first prove that, in general, deterministic solutions could be even nearly-quadratically (i.e., up to a polylogarithmic factor) worse than the best randomized ones. On the other hand, we show that deterministic solutions could be efficient if the underlying wireless network topology is defined by a metric of small growth. More precisely, we show nearly-tight upper and lower bounds on the length of the schedules, constructed and run in a distributed way by wireless nodes located in a metric space. These bounds depend on both the wireless interference of the set of links on each other, called affectance, and the growth parameter of the underlying metric space. In particular, for metrics of constant growth (so called, bounded growth metrics, e.g., constant-dimension Euclidean spaces, even with some obstacles, or sparse graphs), the length of our deterministic schedule is almost as short as the best known randomized ones.

Radio Networks (RN) is one of the fundamental models for network communication where nodes can broadcast messages locally but their simultaneous transmissions can interfere with each other at their shared neighbors. This work focuses on performing the very fundamental primitive of Local Broadcast, in spite of the interferences. We investigate to what extent local knowledge, called advice, relating to the 2-local domination number γ₂ may speed up Local Broadcast. Specifically for each node and some dominating set, knowledge about some neighboring dominating node and the local number among the neighbors of that dominating node. We show that such advice is sufficient to build an efficient oblivious transmission schedule. Along those lines, we present three algorithms trading the level of adaptiveness (from oblivious to adaptive) for bits of advice per node (from O(log (Δγ₂)) to 1). All our algorithms complete Local Broadcast in Õ(Δγ₂²) rounds, where Δ is the maximum degree of the network. On the side of lower bounds, we show that, for each quasi-adaptive deterministic Local Broadcast algorithm, there is some RN that requires Ω(min{(min{Δ,γ₂}/log n)²,n}) communication rounds, where n is the number of network nodes. In quasi-adaptive protocols nodes may stop executing once its computational task is completed. To the best of our knowledge, this is the first (nearly) quadratic Local Broadcast (same message for all neighbors) lower bound in the RN model. Our lower bound is stronger than previous works in multiple ways: i) it is nearly quadratically better than the best known general lower bound for this class of algorithms, ii) it applies to a wider class of algorithms than previous work for fully oblivious, iii) it achieves similar time lower bound than previous work proved for a much more demanding Local Broadcast where each node sends a possibly different message to each neighbor, and iv) it takes into account the local domination parameter γ₂.

We study the Distributed Wireless Link Scheduling (DWLS) problem: there is a set ofnautonomous stations, called senders, each with a message to be delivered to some other station, called receiver. The names and locations of all stations are arbitrarily selected and unknown to each other, to mirror an arbitrary scenario that may occur in mobile communication. Each pair ((sender,receiver),message) is called a request, and the event of successfully delivering the message is called the realization of the request. In the DWLS problem, the requests are realized through wireless communication links (which is a conceptual notion of two nodes being capable of direct wireless delivery of a message) between the stations. The decision to transmit a message is made locally by each station. We consider networks where communication links may interfere with each other, where the interference is an arbitrary input function of each pair of links, customarily called affectance; if the total affectance of other links whose senders are currently transmitting is above a given threshold, the considered transmission is not successful. In the above context, we study the impact of the number of truly random bits used by each link/sender, on the length of the transmission schedules. Specifically, for any setLofnrequests with maximum average affectance$A(L)$, we present a deterministic algorithm (i.e., 0 random bits) and a randomized algorithm using$O(\log A(L)\log n)$random bits per link. (In this abstract we present formulas in simplified forms, for brevity.) The lengths of their transmission schedules are$O(A(L)^{2}\log ^{3} n)$and$O(A(L)\log n)$, respectively. We then combine both approaches to get a randomized solution using$O(\log W \log n)$truly random bits per station with schedules of length$O\left ({{\frac {A(L)^{2}}{W}\log n}}\right)$, for any$W\le A(L)$. To the best of our knowledge, our study is a first step towards understanding the trade-offs between randomness and time complexity of Link Scheduling under arbitrary interference. It is particularly important as currently used (in practice) wireless protocols are either deterministic or use a very small random seed of (truly) random bits.

We study the Distributed Wireless Link Scheduling (DWLS) problem: there is a set of n autonomous stations, called senders, each with a packet to be delivered to some other station, called receiver. The names and locations of all stations are arbitrarily selected and unknown to each other, to mirror an arbitrary scenario that may occur in mobile communication. Each pair sender-receiver and the message to be sent is called a request, and the event of successfully delivering the message is called the realization of the request.In the DWLS problem, the requests are realized through wireless communication links (which is a conceptual notion of two nodes being capable of direct wireless delivery of a message) between the stations. The decision to transmit a message is made locally by each station. We consider networks where communication links may interfere with each other, where the interference is an arbitrary input function of each pair of links, customarily called affectance; if the total affectance of other links whose senders are currently transmitting is above a given threshold, the considered transmission is not successful.In the above context, we study the impact of algorithms’ min-entropy, measured as the number of truly random bits used by each link/sender, on the length of the transmission schedules. Specifically, for any set L of n requests with maximum average affectance A(L), we present a deterministic algorithm (i.e., 0 random bits) and a randomized algorithm using O(logA(L)logn) random bits per link. (In this abstract we present formulas in simplified forms, for brevity.) The lengths of their transmission schedules are O(A(L)2log3n) and O(A(L)logn), respectively. We then combine both approaches to get a randomized solution with min-entropy O(logW logn) per station that uses schedules of length $O\left( {\frac{{A{{(L)}^2}}}{W}\log n} \right)$, for any W ≤ A(L).To the best of our knowledge, our study is a first step towards understanding the trade-offs between randomness and time complexity of Link Scheduling under arbitrary interference. It is particularly important as currently used (in practise) wireless protocols are either deterministic or use a very small random seed of (truly) random bits.

Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, since they can be used to order the results of queries. However, these ranking functions are famously subject to attacks by spammers, who modify the web graph in order to give their own pages more rank.

We study the problem of randomized Leader Election in synchronous distributed networks with indistinguishable nodes. We consider algorithms that work on networks of arbitrary topology in two settings, depending on whether the size of the network, i.e., the number of nodes$n$, is known or not. In the former setting, we present a new Leader Election protocol that improves over previous work by lowering message complexity and making it close to a lower bound by a factor in$\widetilde{O}(\sqrt{t_{mix}\sqrt{\Phi}})$, where$\Phi$is the conductance and$t_{mix}$is the mixing time of the network graph. We then show that lacking the network size no Leader Election algorithm can guarantee that the election is final with constant probability, even with unbounded communication. Hence, we further classify the problem as Leader Election (the classic one, requiring knowledge of$n$- as is our first protocol) or Revocable Leader Election, and present a new polynomial time and message complexity Revocable Leader Election algorithm in the setting without knowledge of network size. We analyze time and message complexity of our protocols in the CONGEST model of communication.

How to reach consensus on an average value in a dynamic crowd without revealing identity? In this work, we study the problem of Average Network Consensus in Anonymous Dynamic Networks (ADN). Network dynamicity is specified by the sequence of topology-graph isoperimetric numbers occurring over time, which we call the isoperimetric dynamicity of the network. The consensus variable is the average of values initially held by nodes, which is customary in the Network-consensus literature. Given that having an algorithm to compute the average one can compute the network size (i.e. the Counting problem) and viceversa, we further focus on the latter.

Starting with with work of Michail et al., the problem of Counting the number of nodes in Anonymous Dynamic Networks has attracted a lot of attention. The problem is challenging because nodes are indistinguishable (they lack identifiers and execute the same program), and the topology may change arbitrarily from round to round of communication, as long as the network is connected in each round. The problem is central in distributed computing, as the number of participants is frequently needed to make important decisions, including termination, agreement, synchronization, among others. A variety of distributed algorithms built on top of mass-distribution techniques have been presented, analyzed, and experimentally evaluated; some of them assumed additional knowledge of network characteristics, such as bounded degree or given upper bound on the network size. However, the question of whether Counting can be solved deterministically in sub-exponential time remained open. In this work, we answer this question positively by presenting M ethodical C ounting , which runs in polynomial time and requires no knowledge of network characteristics. Moreover, we also show how to extend M ethodical C ounting to compute the sum of input values and more complex functions without extra cost. Our analysis leverages previous work on random walks in evolving graphs, combined with carefully chosen alarms in the algorithm that control the process and its parameters. To the best of our knowledge, our Counting algorithm and its extensions to other algebraic and Boolean functions are the first that can be implemented in practice with worst-case guarantees.

Millimeter wave (mmWave) communication not only provides ultra-high speed radio access but is also ideally suited for efficient and flexible wireless backhauling. Specifically for dense deployments, a mmWave macro base station (MBS) that serves a large number of mmWave micro base stations (μBSs) is much more cost effective than legacy cellular architectures which connect μBSs to the core network through fibers. In addition, μBSs can cooperate with each other by acting as relay nodes. The directional nature of mmWave communication allows for spatial reuse, even in the presence of interference, which can be exploited to optimize mmWave wireless backhaul performance. The optimization opportunistically prioritizes the use of good connections at the MBS and further leverages compact and concurrent transmissions between μBS. Relays and directional antennas speed up communication, but increase the complexity of the scheduling problem. In this work, we study the mmWave backhaul scheduling problem and derive an MILP formulation for it as well as upper and lower bounds. We prove that the problem is NP-hard and can be approximated, but only if interference is negligible. By means of numerical simulations, we compare theoretical results with heuristics in small system sizes. Results validate the analysis and demonstrate the high performance of our heuristics in realistic cellular settings.

Counting the number of nodes in {Anonymous Dynamic Networks} is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [Michail et al., 2013], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [Dariusz R. Kowalski and Miguel A. Mosteiro, 2018]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them.

Millimeter wave communication (mmWave) allows high-speed access to the radio channel. Given the highly-directional nature of mmWave, dense deployments can be implemented with a macro base station serving many micro base stations, rather than connecting micro base stations directly to the core network as in legacy cellular systems. Moreover, micro base stations may cooperate in relaying packets to other micro base stations. Relays and spatial reuse speed up communication, but increase the complexity of scheduling. In this work, we study the mmWave wireless backhaul scheduling problem in the described architecture, assuming stochastic arrival of packets at the macro base station to be delivered to micro base stations. We present various results concerning system stability, defined as a bounded expected queue sizes of macro base station and micro base stations, under different patterns of random traffic. In particular, that almost all admissible arrival patterns could be handled by some universally stable algorithms, while non-admissible arrival patterns do not allow stability for any algorithm.

Information dissemination protocols for ad-hoc wireless networks frequently use a minimal subset of the available communication links, defining a rooted "“broadcast"” tree. In this work, we focus on the core challenge of disseminating from one layer to the next one of such tree. We call this problem Layer Dissemination. We study Layer Dissemination under a generalized model of interference, called affectance. The affectance model subsumes previous models, such as Radio Network and Signal to Inteference-plus-Noise Ratio. We present randomized and deterministic protocols for Layer Dissemination. These protocols are based on a combinatorial object that we call Affectance-selective Families. Our approach combines an engineering solution with theoretical guarantees. That is, we provide a method to characterize the network with a global measure of affectance based on measurements of interference in the specific deployment area. Then, our protocols distributedly produce an ad-hoc transmissions schedule for dissemination. In the randomized protocol only the network characterization is needed, whereas the deterministic protocol requires full knowledge of affectance. Our theoretical analysis provides guarantees on schedule length. We also present simulations of a real network-deployment area contrasting the perform- ance of our randomized protocol, which takes into account affectance, against previous work for interference models that ignore some physical constraints. The striking improvement in performance shown by our simulations show the importance of utilizing a more physically-accurate model of interference that takes into account other effects beyond distance to transmitters.

We consider a computing system where a master processor assigns tasks for execution to worker processors through the Internet. We model the workers' decision of whether to comply (compute the task) or not (return a bogus result to save the computation cost) as a mixed extension of a strategic game among workers. That is, we assume that workers are rational in a game-theoretic sense, and that they randomize their strategic choice. Workers are assigned multiple tasks in subsequent rounds. We model the system as an infinitely repeated game of the mixed extension of the strategic game. In each round, the master decides stochastically whether to accept the answer of the majority or verify the answers received, at some cost. Incentives and/or penalties are applied to workers accordingly. Under the above framework, we study the conditions in which the master can reliably obtain tasks results, exploiting that the repeated game model captures the effect of long-term interaction. That is, workers take into account that their behavior in one computation will have an effect on the behavior of other workers in the future. Indeed, should a worker be found to deviate from some agreed strategic choice, the remaining workers would change their own strategy to penalize the deviator. Hence, being rational, workers do not deviate. We identify analytically the parameter conditions to induce a desired worker behavior, and we evaluate experimentally the mechanisms derived from such conditions. We also compare the performance of our mechanisms with a previously known multi-round mechanism based on reinforcement learning.

We study the problem of counting the number of nodes in a slotted-time communication network, under the challenging assumption that nodes do not have identifiers and the network topology changes frequently. That is, for each time slot links among nodes can change arbitrarily provided that the network is always connected. This network model has been motivated by the ongoing development of new communication technologies that enable the deployment of a massive number of devices with highly dynamic connectivity patterns. Tolerating dynamic topologies is clearly crucial in face of mobility and unreliable communication. Current communication networks do have node identifiers though. Nevertheless, in future massive networks, it might be suitable to avoid nodes IDs to facilitate mass production. Consequently, knowing what is the cost of anonymity is of paramount importance to understand what is feasible or not for future generations of Dynamic Networks. Counting is a fundamental task in distributed computing since knowing the size of the system often facilitates the desing of solutions for more complex problems. Also, the size of the system is usually used to decide termination in distributed algorithms. Currently, the best upper bound proved on the running time to compute the exact network size is double-exponential. However, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not. In this paper we make a significant step towards answering this question by presenting a distributed Counting protocol for Anonymous Dynamic Networks which has exponential time complexity. This algorithm, which we call Incremental Counting, ensures that eventually every node knows the exact size of the system and stops executing the protocol. Previous Counting protocols have either double-exponential time complexity, or they are exponential but do not terminate, or terminate but do not provide running-time guarantees, or guarantee only an exponential upper bound on the network size. Other protocols are heuristic and do not guarantee the correct count.

We consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of untrusted worker processors, and collects their responses. Examples of such computations are the "@homeâ' projects such as SETI. In this work, various worker behaviors are considered. Altruistic workers always return the correct result of the task, malicious workers always return an incorrect result, and rational workers act based on their self-interest. In a massive computation platform, such as the Internet, it is expected that all three type of workers coexist. Therefore, in this work, we study Internet-based master-worker computations in the presence of malicious, altruistic, and rational workers. A stochastic distribution of the workers over the three types is assumed. In addition, we consider the possibility that the communication between the master and the workers is not reliable, and that workers could be unavailable. Considering all the three types of workers renders a combination of game-theoretic and classical distributed computing approaches to the design of mechanisms for reliable Internet-based computing. Indeed, in this work, we design and analyze two algorithmic mechanisms to provide appropriate incentives to rational workers to act correctly, despite the malicious workers' actions and the unreliability of the communication. Only when necessary, the incentives are used to force the rational players to a certain equilibrium (which forces the workers to be truthful) that overcomes the attempt of the malicious workers to deceive the master. Finally, the mechanisms are analyzed in two realistic Internet-based master-worker settings, a SETI-like one and a contractor-based one, such as Amazon's mechanical turk. We also present plots that illustrate the tradeoffs between reliability and cost, under different system parameters.

SUMMARY We consider Internet‐based master–worker task computations, such as SETI@home, where a master process sends tasks, across the Internet, to worker processes; workers execute and report back some result. However, these workers are not trustworthy, and it might be at their best interest to report incorrect results. In such master–worker computations, the behavior and the best interest of the workers might change over time. We model such computations using evolutionary dynamics, and we study the conditions under which the master can reliably obtain task results. In particular, we develop and analyze an algorithmic mechanism based on reinforcement learning to provide workers with the necessary incentives to eventually become truthful. Our analysis identifies the conditions under which truthful behavior can be ensured and bounds the expected convergence time to that behavior. The analysis is complemented with illustrative simulations. Copyright © 2013 John Wiley & Sons, Ltd.

This work considers Internet-based task computations in which a master process assigns tasks, over the Internet, to rational workers and collect their responses. The objective is for the master to obtain the correct task outcomes. For this purpose we formulate and study the dynamics of evolution of Internet-based master-worker computations through reinforcement learning.

This work, using a game-theoretic approach, considers Internet-based computations, where a master processor assigns, over the Internet, a computational task to a set of untrusted worker processors, and collects their responses. The master must obtain the correct task result, while maximizing its benefit. Building on prior work, we consider a framework where altruistic, malicious, and rational workers co-exist. In addition, we consider the possibility that the communication between the master and the workers is not reliable, and that workers could be unavailable assumptions that are very realistic for Internet-based master-worker computations. Within this framework, we design and analyze two algorithmic mechanisms that provide, when necessary, appropriate incentives to rational workers to act correctly, despite the malicious' workers actions and the unreliability of the network. These mechanisms are then applied to two realistic Internet-based master-worker settings, a SETI-like one and a contractor-based one, such as Amazon's mechanical turk.

Recent work on shared-resource contention resolution has yielded fruitful results for local area networks and radio networks, although either the solution is suboptimal [2] or a (possibly loose) upper bound on the number of users needs to be known [5]. In this work, we present the first (two) protocols for contention resolution in radio networks that are asymptotically optimal (with high probability), work without collision detection, and do not require information about the number of contenders. In addition to the theoretical analysis, the protocols are evaluated and contrasted with the previous work by extensive simulations.

We consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of untrusted worker processors, and collects their responses; examples of such computations are the ¿@home¿ projects such as SETI. Prior work dealing with Internet-based task computations has either considered only rational, or only malicious and altruistic workers. Altruistic workers always return the correct result of the task, malicious workers always return an incorrect result, and rational workers act based on their self-interest. However, in a massive computation platform, such as the Internet, it is expected that all three type of workers coexist. Therefore, in this work we study Internet-based master-worker computations in the presence of Malicious, Altruistic, and Rational workers. A stochastic distribution of the workers over the three types is assumed. Considering all the three types of workers renders a combination of game-theoretic and classical distributed computing approaches to the design of mechanisms for reliable Internet-based computing. Indeed, in this work, such an algorithmic mechanism that makes use of realistic incentives to obtain the correct task result with a parametrized probability is designed. Only when necessary, the incentives are used to force the rational players to a certain equilibrium (which forces the workers to be truthful) that overcomes the attempts of the malicious workers to deceive the master. Finally, the mechanism is analyzed in two realistic Internet-based master-worker applications. This work is an example of how game theory can be used as a tool to formalize and solve a practical Distributed Computing problem such as Internet supercomputing.

In this paper, we study algebraic aggregate computations in Sensor Networks. The main contribution is the presentation of an early-stopping protocol that computes the average function under a harsh model of the conditions under which sensor nodes operate. This protocol is shown to be time-optimal in presence of unfrequent failures. The approach followed saves time and energy by relying the computation on a small network of delegate nodes that can be rebuilt fast in case of node failures and communicate using a collision-free schedule. Delegate nodes run simultaneously two protocols, namely, a collection/dissemination tree-based algorithm, which is shown to be optimal, and a mass-distribution algorithm. Both algorithms are analyzed under a model where the frequency of failures is a parameter. Other aggregate computation algorithms can be easily derived from this protocol. To the best of our knowledge, this is the first optimal early-stopping algorithm for aggregate computations in Sensor Networks.

Sensor nodes are very weak computers that get distributed at random on a surface. Once deployed, they must wake up and form a radio network. Sensor network bootstrapping research thus has three parts: One must model the restrictions on sensor nodes; one must prove that the connectivity graph of the sensors has a subgraph that would make a good network; and one must give a distributed protocol for finding such a network subgraph that can be implemented on sensor nodes. Although many particular restrictions on sensor nodes are implicit or explicit in many papers, there remain many inconsistencies and ambiguities from paper to paper. The lack of a clear model means that solutions to the network bootstrapping problem in both the theory and systems literature all violate constraints on sensor nodes. For example, random geometric graph results on sensor networks predict the existence of subgraphs on the connectivity graph with good route-stretch, but these results do not address the degree of such a graph, and sensor networks must have constant degree. Furthermore, proposed protocols for actually finding such graphs require that nodes have too much memory, whereas others assume the existence of a contention-resolution mechanism. We present a formal Weak Sensor model that summarizes the literature on sensor node restrictions, taking the most restrictive choices when possible. We show that sensor connectivity graphs have low-degree subgraphs with good hop-stretch , as required by the Weak Sensor model. Finally, we give a Weak Sensor model-compatible protocol for finding such graphs. Ours is the first network initialization algorithm that is implementable on sensor nodes.

In this work, using a game-theoretic approach, cost-sensitive mechanisms that lead to reliable Internet-based computing are designed. In particular, we consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of potentially untrusted worker processors and collects their responses. Several game-theoretic models that capture the nature of the problem are analyzed and mechanisms that, for each given set of cost and system parameters, achieve high reliability are designed. Additionally, two specific realistic system scenarios are studied. These scenarios are a system of volunteering computing like SETI, and a company that buys computing cycles from Internet computers and sells them to its customers in the form of a task-computation service. Notably, under certain conditions, non redundant allocation yields the best trade-off between cost and reliability.