In the renaming problem, a set of n nodes, each with a unique identity from a large namespace [N], needs to obtain new unique identities in a smaller namespace [M]. A renaming algorithm is strong if M = n. There exist many time-efficient solutions for fault-tolerant renaming in synchronous message-passing systems. However, all previous algorithms send Ω(n2) messages, and many of them also send large messages each containing Ω(n) bits. Moreover, most algorithms' performance do not scale with the actual number of failures. These limitations restrict their practical performance.

Contention resolution is a problem that captures the difficulty of coordinating multiple processes to access a shared resource. A common way to model this problem is to assume n nodes arrive over time, each with a messages that it intends to transmit. In each round, every node can try to broadcast its message, and a node succeeds if it broadcasts alone. Nodes that do not broadcast can listen on the channel to obtain feedback regarding whether a successful transmission has occurred. Under above assumptions, recent results show that all n nodes can succeed within Θ(n) rounds, which is optimal; moreover, each node attempts broadcast at most O(polylog(n)) times before succeeding. However, all previous work attaining such strong guarantees assume channel feedback is free, and it remains unknown whether similar results can be obtained when listening cost are also taken into consideration. Such algorithms would be beneficial for distributed systems in which querying channel feedback incurs non-negligible cost, such as wireless networks.

Contention resolution on a multiple-access communication channel is a classical problem in distributed and parallel computing. In this problem, a set of nodes arrive over time, each with a message it intends to send. Time proceeds in synchronous slots, and in each slot each node can broadcast its message or remain idle. If in a slot one node broadcasts alone, it succeeds; otherwise, if multiple nodes broadcast simultaneously, messages collide and none succeeds. Nodes can differentiate collision and silence (that is, no node broadcasts) only if a collision detection mechanism is available. Ideally, a contention resolution algorithm should satisfy at least three criteria: (a) low time complexity (i.e., high throughput), meaning it does not take too long for all nodes to succeed; (b) low energy complexity, meaning each node does not make too many broadcast attempts before it succeeds; and (c) strong robustness, meaning the algorithm can maintain good performance even if interference is present. Such interference is often modeled by jamming---a jammed slot always generates collision. Previous work has shown, with collision detection, there are "perfect" contention resolution algorithms satisfying all three criteria. On the other hand, without collision detection, it was not until 2020 that an algorithm was discovered which can achieve optimal time complexity and low energy cost, assuming there is no jamming. More recently, the trade-off between throughput and robustness was studied. However, an intriguing and important question remains unknown: without collision detection, are there "perfect" contention resolution algorithms? In other words, when collision detection is absent and jamming is present, can we achieve both low total time complexity and low per-node energy cost? In this paper, we answer the above question affirmatively. Specifically, a new randomized algorithm for robust contention resolution is developed, assuming collision detection is not available. Lower bound results demonstrate it achieves both optimal time complexity and optimal energy complexity. If all nodes start execution simultaneously---which is often referred to as the "static case" in literature---another algorithm is developed that runs even faster. The separation on time complexity suggests, for robust contention resolution without collision detection, "batch" instances (that is, nodes start simultaneously) are inherently easier than "scattered" ones (that is, nodes arrive over time).

In this paper, we study gossip algorithms in communication models that describe the peer-to-peer networking functionality included in most standard smartphone operating systems. We begin by describing and analyzing a new synchronous gossip algorithm in this setting that features both a faster round complexity and simpler operation than the bestknown existing solutions. We also prove a new lower bound on the rounds required to solve gossip that resolves a minor open question by establishing that existing synchronous solutions are within logarithmic factors of optimal. We then adapt our synchronous algorithm to produce a novel gossip strategy for an asynchronous model that directly captures the interface of a standard smartphone peer-to-peer networking library (enabling algorithms described in this model to be easily implemented on real phones). Using new analysis techniques, we prove that this asynchronous strategy efficiently solves gossip. This is the first known efficient asynchronous information dissemination result for the smartphone peer-to-peer setting. We argue that our new strategy can be used to implement effective information spreading subroutines in real world smartphone peer-to-peer network applications, and that the analytical tools we developed to analyze it can be leveraged to produce other broadly useful algorithmic strategies for this increasingly important setting.

In this paper, we consider contention resolution on a multiple-access communication channel. In this problem, a set of nodes arrive over time, each with a message it intends to send. In each time slot, each node may attempt to broadcast its message or remain idle. If a single node broadcasts in a slot, the message is received by all nodes; otherwise, if multiple nodes broadcast simultaneously, a collision occurs and none succeeds. If collision detection is available, nodes can differentiate collision and silence (i.e., no node broadcasts). Performance of contention resolution algorithms is often measured by throughput---the number of successful transmissions within a period of time; whereas robustness is often measured by jamming resistance---a jammed slot always generates a collision. Previous work has shown, with collision detection, optimal constant throughput can be attained, even if a constant fraction of all slots are jammed. The situation when collision detection is not available, however, remains unclear.

Broadcasting in wireless networks is vulnerable to adversarial jamming. To thwart such behavior, \emph{resource competitive analysis} is proposed. In this framework, sending, listening, or jamming on one channel for one time slot costs one unit of energy. The adversary can employ arbitrary strategy to disrupt communication, but has a limited energy budget $T$. The honest nodes, on the other hand, aim to accomplish broadcast while spending only $o(T)$. Previous work has shown, in a $C$-channels network containing $n$ nodes, for large $T$ values, each node can receive the message in $\tilde{O}(T/C)$ time, while spending only $\tilde{O}(\sqrt{T/n})$ energy. However, these multi-channel algorithms only work for certain values of $n$ and $C$, and can only tolerate an oblivious adversary. In this work, we provide new upper and lower bounds for broadcasting in multi-channel radio networks, from the perspective of resource competitiveness. Our algorithms work for arbitrary $n,C$ values, require minimal prior knowledge, and can tolerate a powerful adaptive adversary. More specifically, in our algorithms, for large $T$ values, each node's runtime is $O(T/C)$, and each node's energy cost is $\tilde{O}(\sqrt{T/n})$. We also complement algorithmic results with lower bounds, proving both the time complexity and the energy complexity of our algorithms are optimal or near-optimal (within a poly-log factor). Our technical contributions lie in using "epidemic broadcast" to achieve time efficiency and resource competitiveness, and employing coupling techniques in the analysis to handle the adaptivity of the adversary. At the lower bound side, we first derive a new energy complexity lower bound for 1-to-1 communication in the multi-channel setting, and then apply simulation and reduction arguments to obtain the desired result.

Broadcasting in wireless networks is vulnerable to adversarial jamming. To thwart such behavior, researchers have proposed resource competitive analysis. In this framework, sending, listening, or jamming on one channel for one time slot costs one unit of energy. The adversary can employ arbitrary strategy to disrupt communication, but has a limited energy budget T. The honest nodes, on the other hand, aim to accomplish broadcast while spending only o(T). Previous work has shown, in a C-channels network containing n nodes, each node can receive the message in roughly O(T/C) time, while spending only roughly [EQUATION] energy. However, these algorithms only work for C = O(n), and can only tolerate an oblivious adversary. We improve the result by considering an adaptive adversary and arbitrary values of n and C. In our algorithms, for large T values, each node's runtime is O(T/C), and each node's energy cost is [EQUATION]. The time complexity is asymptotically optimal, while the energy complexity is near optimal in some cases. We use "epidemic broadcast" with proper working probabilities to achieve time efficiency and resource competitiveness, and leverage coupling arguments in the analysis to handle the adaptivity of the adversary.

Consider a single-hop, multi-channel, synchronous radio network in which a source node needs to disseminate a message to all other $n-1$ nodes. An adversary called Eve, which captures environmental noise and potentially malicious interference, aims to disrupt this process via jamming. Assume sending, listening, or jamming on one channel for one time slot costs unit energy. The question is, if Eve spends T units of energy on jamming, can we devise broadcast algorithms in which each node's cost is o(T) Previous results show such resource competitive algorithms do exist in the single-channel setting: each node can receive the message within ~O(T+n) time slots while spending only ~O(√T/n+1) energy. In this paper, we show that when Eve is oblivious, the existence of multiple channels allows even faster message dissemination, while preserving resource competitiveness. Specifically, we have identified an efficient "epidemic broadcast" scheme in the multi-channel setting that is robust against jamming. Extending this scheme leads to a randomized algorithm called MultiCast which uses n/2 channels, and accomplishes broadcast in ~O(T/n+1) time slots while costing each node only ~O(√T/n+1) energy. When the value of n is unknown, we further propose MultiCastAdv, in which each node's running time is ~O(T/(n1-2α)+n2α), and each node's cost is ~O(√T/ (n1-2α) +n2α). Here, 0<α<1/4 is a tunable parameter affecting the constant hiding behind the big-O notation. To handle the issue of limited channel availability, we have also devised variants for both MultiCast and MultiCastAdv that can work in networks in which only C channels are available, for any C≥1. These variants remain to be resource competitive, and have (near) optimal time complexity in many cases.

For many distributed algorithms, neighborhood size is an important parameter. In radio networks, however, obtaining this information can be difficult due to ad hoc deployments and communication that occurs on a collision-prone shared channel. This paper conducts a comprehensive survey of the approximate neighbor counting problem, which requires nodes to obtain a constant factor approximation of the size of their network neighborhood. We produce new lower and upper bounds for three main variations of this problem in the radio network model: (a) the network is single-hop and every node must obtain an estimate of its neighborhood size; (b) the network is multi-hop and only a designated node must obtain an estimate of its neighborhood size; and (c) the network is multi-hop and every node must obtain an estimate of its neighborhood size. In studying these problem variations, we consider solutions with and without collision detection, and with both constant and high success probability. Some of our results are extensions of existing strategies, while others require technical innovations. We argue this collection of results provides insight into the nature of this well-motivated problem (including how it differs from related symmetry breaking tasks in radio networks), and provides a useful toolbox for algorithm designers tackling higher level problems that might benefit from neighborhood size estimates.

Cognitive radio networks are a new type of multi-channel wireless network in which different nodes can have access to different sets of channels. By providing multiple channels, they improve the efficiency and reliability of wireless communication. However, the heterogeneous nature of cognitive radio networks also brings new challenges to the design and analysis of distributed algorithms. In this paper, we focus on two fundamental problems in cognitive radio networks: neighbor discovery, and global broadcast. We consider a network containing n nodes, each of which has access to c channels. We assume the network has diameter D, and each pair of neighbors have at least k≥1, and at most kmax≤c, shared channels. We also assume each node has at most Δ neighbors. For the neighbor discovery problem, we design a randomized algorithm CSeek which has time complexity Õ( (c2/k) + (kmax/k)*Δ ). CSeek is flexible and robust, which allows us to use it as a generic "filter" to find "well-connected" neighbors with an even shorter running time. We then move on to the global broadcast problem, and propose CGCast, a randomized algorithm which takes Õ( (c2/k) + (kmax/k)*Δ + D*Δ) time. CGCast uses CSeek to achieve communication among neighbors, and uses edge coloring to establish an efficient schedule for fast message dissemination.

Cryptocurrencies, such as Bitcoin and 250 similar alt-coins, embody at their core a blockchain protocol --- a mechanism for a distributed network of computational nodes to periodically agree on a set of new transactions. Designing a secure blockchain protocol relies on an open challenge in security, that of designing a highly-scalable agreement protocol open to manipulation by byzantine or arbitrarily malicious nodes. Bitcoin's blockchain agreement protocol exhibits security, but does not scale: it processes 3--7 transactions per second at present, irrespective of the available computation capacity at hand.

Devices in a cognitive radio network use advanced radios to identify pockets of usable spectrum in a crowded band and make them available to higher layers of the network stack. A core challenge in designing algorithms for this model is that different devices might have different views of the network. In this paper, we study two problems for this setting that are well-motivated but not yet well-understood: local broadcast and data aggregation. We consider a single hop cognitive radio network with n nodes that each has access to c channels. We assume each pair of nodes overlaps on at least 1<=k<=c channels.

Consider a scenario where many wireless users are attempting to download data from a single base station. While most of the users are honest, some users may be malicious and attempt to obtain more than their fair share of the bandwidth. One possible strategy for attacking the system is to simulate multiple fake identities, each of which is given its own equal share of the bandwidth. Such an attack is often referred to as a sybil attack. To counter such behavior, we propose SybilCast, a protocol for multichannel wireless networks that limits the number of fake identities, and in doing so, ensures that each honest user gets at least a constant fraction of their fair share of the bandwidth. As a result, each honest user can complete his or her data download in asymptotically optimal time. A key aspect of this protocol is balancing the rate at which new identities are admitted and the maximum number of fake identities that can co-exist, while keeping the overhead low. Besides sybil attacks, our protocol can also tolerate spoofing and jamming.