# Seth Gilbert

## Home · Projects · Publications · CV

### Wireless Networks

 Who are you? Secure identities in single hop ad hoc networks by Seth Gilbert, Calvin Newport, and Chaodong ZhengDistributed Computing, 30(2):103–125, 2017 Contention Resolution on a Fading Channel by Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, and Calvin NewportProceeding of the Symposium on Principles of Distributed Computing (PODC), July, 2016 PSync: Visible Light-Based Time Synchronization for Internet of Things by Xiangfa Guo, Mobashir Mohammad, Sudipta Saha, Mun Choon Chan, Seth Gilbert, and Derek LeongProceedings of INFOCOM, April, 2016 How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell YoungProceedings of the Symposium on Discrete Algorithms (SODA), Pages: 636–654January, 2016 QProbe: Locating the Bottleneck in Cellular Communication by Nimantha Baranasuriya, Vishnu Navda, Venkat Padmanabhan, and Seth GilbertProceedings of the Conference on emerging Networking EXperiments and Technologies (CoNEXT), December, 2015 The Computational Power of Beeps by Seth Gilbert and Calvin C. NewportProceedings of the Symposium on Distributed Computing (DISC), Pages: 31–46October, 2015 Efficient Communication in Cognitive Radio Networks by Seth Gilbert, Fabian Kuhn, Calvin Newport, and Chaodong ZhengProceedings of the Symposium on Principles of Distributed Computing (PODC), Pages: 119–128July, 2015 Resource-Competitive Algorithms by Michael A. Bender, Jeremy T. Fineman, Mahnush Movahedi, Jared Saia, Varsha Dani, Seth Gilbert, Seth Pettie, and Maxwell YoungSIGACT News, 46(3):57–71, 2015 SybilCast: Broadcast on the Open Airwaves by Seth Gilbert and Chaodong ZhengTOPC, 2(3):16, 2015 Who Are You? Secure Identities in Ad Hoc Networks by Seth Gilbert, Calvin Newport, and Chaodong ZhengProceeding of the International Symposium on Distributed Computing (DISC), October, 2014 (Near) optimal resource-competitive broadcast with jamming by Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, and Maxwell YoungProceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages: 257–266June, 2014 Aggregation in Smartphone Sensor Networks by Nimantha Thushan Baranasuriya, Seth Lewis Gilbert, Calvin C. Newport, and Jayanthi RaoProceedings of the Conference on Distributed Computing in Sensor Systems (DCOSS), Pages: 101–110May, 2014 Structuring unreliable radio networks by Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy A. Lynch, and Calvin C. NewportDistributed Computing, 27(1):1–19, 2014 Broadcast in the Ad Hoc SINR Model by Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. NewportProceeding of the International Conference on Distributed Computing (DISC), October, 2013 Maximal independent set in multichannel radio networks by Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn, and Calvin C. NewportProceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2013 SybilCast: broadcast on the open airwaves by Seth Gilbert and Chaodong ZhengProceeding of the Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2013 Optimal Broadcast in Shared Spectrum Radio Networks by Mohsen Ghaffari, Seth Gilbert, Calvin Newport, and Henry TanProceedings of the Conference On Principles Of Distributed Systems (OPODIS), December, 2012 Aggregation in dynamic networks by Alejandro Cornejo, Seth Gilbert, and Calvin C. NewportProceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2012 Leader election in shared spectrum radio networks by Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. NewportProceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2012 Making evildoers pay: resource-competitive broadcast in sensor networks by Seth Gilbert and Maxwell YoungProceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2012 Resource-competitive analysis: a new perspective on attack-resistant distributed computing by Seth Gilbert, Jared Saia, Valerie King, and Maxwell YoungProceedings of the Workshop on Foundations of Mobile Computing (FOMC), July, 2012 Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast by Shlomi Dolev, Seth Gilbert, Majid Khabbazian, and Calvin NewportProceedings of the Symposium on Distributed Computing (DISC), September, 2011Abstract: This paper addresses two primary questions: (i) How much faster can we disseminate information in a large wireless network if we have multiple communication channels available (as compared to relying on only a single communication channel)? (ii) Can we still disseminate information reliably, even if some subset of the channels are disrupted? In answer to the first question, we reduce the cost of broadcast to O(log log n) rounds/hop, approximately, for sufficiently many channels.We answer the second question in the affirmative, presenting two different algorithms, while at the same time proving a lower bound showing that disrupted channels have unavoidable costs. To download the paper: pdf format Structuring Unreliable Radio Networks by Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, and Calvin NewportProceedings of the International Conference on Principles of Distributed Computing (PODC), June, 2011Abstract: In this paper we study the problem of building a connected dominating set with constant degree (CDS) in the dual graph radio network model. This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. If processes u and v are connected by a reliable (resp. unreliable) link, we say that they are reliable (resp. unreliable) neighbors. We first prove that without topology knowledge, every randomized CDS algorithm requires Ω(Δ) rounds, where Δ is the degree of the reliable communication graph. We then prove that even if we provide each process with a set containing the id of every reliable neighbor, the possible additional inclusion of a single unreliable neighbor in this set is enough to maintain the Ω(Δ) lower bound, regardless of message size. Notice, these bounds demonstrate a separation with the classic radio network model (which has only reliable links), where the CDS problem has been shown in concurrent work to be solvable in polylogarithmic time without topology knowledge. We continue by presenting a randomized upper bound that leverages accurate knowledge of reliable neighbors to solve the CDS problem in O(Δlog2n/b + log3n) rounds, w.h.p., where n is the network size and b is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in log3n time, and then using a novel path finding technique that leverages the topology knowledge to efficiently connect nearby MIS processes. We conjecture that this upper bound is tight, and as as evidence for this conjecture, we show a reduction to the CDS problem from a new communication complexity problem. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time. To download the paper: pdf format Trusted Computing for Fault-Prone Wireless Networks by Seth Gilbert and Dariusz KowalskiProceedings of the International Symposium on Distributed Computing (DISC), September, 2010Abstract: We consider a fault-prone wireless network in which communication may be subject to wireless interference. There are many possible causes for such interference: other applications may be sharing the same bandwidth; malfunctioning devices may be creating spurious noise; or malicious devices may be actively jamming communication. In all such cases, communication may be rendered impossible. In other areas of networking, the paradigm of "trusted computing" has proved an effective tool for reducing the power of unexpected attacks. In this paper, we ask the question: can some form of trusted computing enable devices to communicate reliably? In answering this question, we propose a simple "wireless trusted platform module" that limits the manner in which a process can access the airwaves by enabling and disabling the radio according to a pre-determined schedule. Unlike prior attempts to limit disruption via scheduling, the proposed "wireless trusted platform module" is general-purpose: it is independent of the application being executed and the topology of the network. In the context of such a "wireless trusted platform module," we develop a communication protocol that will allow any subset of devices in a region to communicate, despite the presence of other disruptive (possibly malicious) devices: up to k processes can exchange information in the presence of t malicious attackers in O(max(t3, k2)log2n) time. We also show a lower bound: when t < k, any such protocol requires Ω(min(k2, n)logkn) rounds; in general, at least Ω(min(t3, n2)) rounds are needed, when k ≥ 2. To download the paper: pdf format Securing Your Every Bit: Reliable Broadcast in Byzantine Wireless Networks by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Zarko Milosevic, and Calvin NewportProceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), June, 2010Abstract: This paper presents a reliable broadcast protocol for multihop radio networks subject to Byzantine faults. The protocol is optimal in terms of resilience and asymptotically optimal in terms of running time. It runs in O(beta*D + log|Sigma|) rounds, where beta is the maximum number of broadcasts that can be issued by Byzantine devices in a single neighborhood, D is the network diameter, and Sigma is the set of possible messages. In contrast to previous results, we do not assume that a bound on beta is known in advance. Instead, our protocol adapts to the actual amount of interference experienced during a given execution. We evaluate the protocol using the WSNet simulator in the context of three different types of malicious adversary: a silent adversary that refuses to participate; a jamming adversary that attempts to delay the protocol for as long as possible; and a lying adversary that attempts to propagate false information. In doing so, we observe the inherent trade-off between Byzantine-resilience and deployment density as well as convey the robustness of the protocol against malicious jamming. To download the paper: pdf format The Wireless Synchronization Problem by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, and Calvin NewportProceeding of the 28th Symposium on Principles of Distributed Computing (PODC), August, 2009Abstract: In this paper, we study the problem of wireless round synchronization in which devices activated at different times on a congested single-hop radio network attempt to synchronize their round numbering. We assume a collection of n synchronous devices with access to a shared band of the radio spectrum, divided into f narrowband frequencies. We assume that the communication medium suffers from unpredictable, perhaps even malicious interference, which we model by an adversary that can disrupt up to t frequencies per round. Devices begin executing in different rounds and the exact number of participants is not known in advance. We first prove a lower bound on the number of rounds needed to solve the round synchronization problem. We then describe two algorithms. The first almost matches the lower bound, yielding a running time of O((f/(f-t))log^2(n) + (ft/(f - t))log(n)) rounds, with high probability. The second algorithm is adaptive, terminating in O(t'log^3(n)) rounds, with high probability, in good executions, that is, when the devices begin executing at the same time, and there are never more than t' frequencies disrupted in any given round, for some t' &le t. In all executions, even those that are not good, it terminates in O(f log^3(n)) rounds. To download the paper: pdf format Interference-Resilient Information Exchange by Seth Gilbert, Rachid Guerraoui, Dariusz Kowalski, and Calvin NewportProceedings of INFOCOM, April, 2009Abstract: This paper presents an efficient protocol for reliably exchanging information in a single-hop, multi-channel radio network subject to unpredictable interference. We model the interference by an adversary that can simultaneously disrupt up to t of the C available channels. We assume no shared secret keys or third-party infrastructure. The running time of our protocol depends on the gap between C and t: when the number of channels C =Omega(t^2), the running time is linear; when only C = t+1 channels are available, the running time is exponential. We prove that exponential-time is unavoidable in the latter case. At the core of our protocol lies a combinatorial function, possibly of independent interest, described for the first time in this paper: the multi-selector. A multi-selector generates a sequence of channel assignments for each device such that every sufficiently large subset of devices is partitioned onto distinct channels by at least one of these assignments. To download the paper: pdf format Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks by Seth Gilbert, Rachid Guerraoui, and Calvin NewportTheoretical Computer Science, 410(6–7):546–569, February, 2009 Secure Communication over Radio Channels by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin NewportProceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008Abstract: We study the problem of secure communication in a multi-channel, single-hop radio network with a malicious adversary that can cause collisions and spoof messages. We assume no pre-shared secrets or trusted-third-party infrastructure. The main contribution of this paper is f-AME: a randomized (f)ast-(A)uthenticated (M)essage (E)xchange protocol that enables nodes to exchange messages in a reliable and authenticated manner. It runs in O(|E| t^2 log n) time and has optimal resilience to disruption, where E is the set of pairs of nodes that need to swap messages, n is the total number of nodes, C the number of channels, and t the number of channels on which the adversary can participate in each round. We show how to use f-AME to establish a shared secret group key, which can be used to implement a secure, reliable and authenticated long-lived communication service. By contrast, existing solutions rely on pre-shared secrets, trusted third-party infrastructure, and/or the assumption that all interference is non-malicious. To download the paper: pdf format Consensus and Collision Detectors in Radio Networks by Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Tina NolteDistributed Computing, 21(1):55–84, June, 2008Abstract: We consider the fault-tolerant consensus problem in radio networks with crash-prone nodes. Specifically, we develop lower bounds and matching upper bounds for this problem in single-hop radio networks, where all nodes are located within broadcast range of each other. In a novel break from existing work, we introduce a collision-prone communication model in which each node may lose an arbitrary subset of the messages sent by its neighbors during each round. This model is motivated by behavior observed in empirical studies of these networks. To cope with this communication unreliability, we augment nodes with receiver-side collision detectors and present a new classification of collision detectors in terms of accuracy and completeness. This classification is motivated by practical realities and allows us to determine, roughly speaking, how much collision detection capability is enough to solve the consensus problem efficiently in this setting. We consider nine different combinations of completeness and accuracy properties in total, determining for each whether consensus is solvable, and, if it is, a lower bound on the number of rounds required. Furthermore, we distinguish anonymous and non-anonymous protocols—where "anonymous" implies that devices do not have unique identifiers—determining what effect (if any) this extra information has on the complexity of the problem. In all relevant cases, we provide matching upper bounds. Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference) by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin NewportProceedings of the the 21st International Symposium on Distributed Computing (DISC), September, 2007Abstract: We study oblivious deterministic gossip algorithms for multi-channel radio networks with a malicious adversary. In a multi-channel network, each of the n processes in the system must choose, in each round, one of the c channels of the system on which to participate. Assuming the adversary can disrupt one channel per round, preventing communication on that channel, we establish a tight bound on the number of rounds needed to solve the \epsilon-gossip problem, a parameterized generalization of the all-to-all gossip problem that requires (1-\epsilon)n of the "rumors" to be successfully disseminated. Underlying our lower bound proof lies an interesting connection between \epsilon-gossip and extremal graph theory. Specifically, we make use of Turan's theorem, a seminal result in extremal combinatorics, to reason about an adversary's optimal strategy for disrupting an algorithm of a given duration. We then show how to generalize our upper bound to cope with an adversary that can simultaneously disrupt t channels. Our generalization makes use of selectors: a combinatorial tool that guarantees that any subset of processes will be selected'' by some set in the selector. We prove this generalized algorithm optimal if a maximum number of values is to be gossiped. We conclude by extending our algorithm to tolerate traditional Byzantine corruption faults. To download the paper: pdf format  To download talk slides: ppt format Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks by Seth Gilbert, Rachid Guerraoui, and Calvin NewportProceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS), December, 2006Abstract: How efficiently can a malicious device disrupt a single-hop wireless network? Imagine a game involving two honest players, Alice and Bob, who want to exchange information, as well as a malicious adversary, Collin, who wants to prevent them from communicating. Previous work assumes that the adversary cannot induce collisions in the network. By contrast, we allow Collin a budget of beta broadcasts, which he can use to arbitrarily disrupt communication. We show that Alice and Bob can be delayed for exactly 2beta+Theta(lg|V|) communication rounds, where V is the set of values that Alice and Bob may transmit. From this we derive bounds on Collin's efficiency, showing an inherent "jamming gain" of 2, and "disruption-free complexity" of Theta(lg|V|). The trials and tribulations of Alice and Bob in fact capture something fundamental about how efficiently malicious devices can disrupt wireless communication. We derive—via reduction to the 3-player game—round complexity lower bounds for several classical n-player problems: 2beta + Theta(lg|V|) for reliable broadcast, 2beta + Omega(logn/k) for leader election among k contenders, and 2beta + Omega(klg|V|/k) for static k-selection. Then, we consider an extension of our adversary model that also includes up to t crash failures. We study binary consensus as the archetypal problem for this environment and show a bound of 2beta + Theta(t) rounds. These results imply immediate bounds on jamming gain and disruption-free complexity. We provide tight, or nearly tight, upper bounds for all four problems. To download the paper: pdf format Contention Resolution with Heterogeneous Job Sizes by Michael A. Bender, Jeremy T. Fineman, and Seth GilbertProceedings of the 14th Annual European Symposium on Algorithms (ESA), September, 2006Abstract: We study the problem of contention-resolution for different-sized jobs on a simple channel. When a job makes a run attempt on a simple channel, it learns only whether the attempt succeeds or fails. We first analyze the binary exponential backoff protocol, and show that it achieves a makespan of V2^\Theta(\sqrtlog n), where V is the total work of all the contending jobs. This bound is significantly larger than when all jobs are constant-sized. We then analyze a variant of exponential backoff that achieves makespan O(Vlog V). Finally, we introduce a new protocol, called size-hashed backoff, specifically designed for jobs of multiple sizes that achieves makespan O(Vlog^3log V). To download the paper: pdf format  To download talk slides: ppt format Communication-Efficient Probabilistic Quorum Systems by Gregory Chockler, Seth Gilbert, and Boaz Patt-ShamirProceedings of the International Workshop on Foundations and Algorithms for Wireless Networking (FAWN), March, 2006Abstract: Communication-efficiency is of key importance when constructing robust services in limited bandwidth environments, such as sensor networks. We focus on communication-efficiency in the context of quorum systems, which are useful primitives for building reliable distributed systems. To this end, we exhibit a new probabilistic quorum construction in which every node transmits at most O(log^2 n) bits per quorum access, where n is the number of nodes in the system. Our implementation, in addition to being communication efficient, is also robust in the face of communication failures. In particular, it guarantees consistency (with high probability) in the face of network partitions. To the best of our knowledge, no existing probabilistic quorum systems achieve polylogarithmic communication complexity and are resilient to network partitions. To download the paper: pdf format A Middleware Framework for Robust Applications in Wireless Ad Hoc Networks by Gregory Chockler, Murat Demirbas, Seth Gilbert, and Calvin NewportProceeding of the 43rd Allerton Conference on Communication, Control, and Computing, September, 2005 (Invited) Abstract: Wireless ad hoc networks are becoming an increasingly common platform for bringing computation to environments with minimal infrastructure. However, developing algorithms and services for wireless networks is challenging due to unreliable hardware, loss-prone communication, and ad hoc deployment patterns. Most existing wireless ad hoc network applications offer only best-effort correctness guarantees, relying on randomization and heuristics like gossiping to produce solutions that work often, but not always. Although this approach is adequate for simple tasks such as message flooding or data aggregation, it is nevertheless, not appropriate for applications requiring well-defined fault-tolerance guarantees (e.g., agreement protocols, software version management, coordinated actuator control, etc.). In this paper, we introduce a new middleware framework for wireless ad hoc networks to aid the development of algorithms with strict consistency requirements. Our framework is based on the following three components: (1) receiver-side collision detection, used for identifying inconsistencies caused by unreliable communication; (2) robust round synchronization, used for emulating a strictly synchronized multi-hop network using only basic timeliness assumptions about the environment; and (3) contention management, used for reducing message collision and supporting eventually reliable message delivery. We demonstrate the utility of our framework by showing how it can be used to implement global agreement using local agreement as a building block, and experimentally illustrate its practicality using Mica 2 motes and the ns-2 network simulator. To download the paper: pdf format Consensus and Collision Detectors in Wireless Ad Hoc Networks by Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport, and Tina Nolte24th Annual Symposium on the Principles of Distributed Computing (PODC), July, 2005Abstract: We consider the fault-tolerant consensus problem in wireless ad hoc networks with crash-prone nodes. We develop consensus algorithms for single-hop wireless networks, where the nodes are located within broadcast range of each other. Our algorithms tolerate a highly unpredictable network model, in which messages may be lost due to collisions, electromagnetic interference, or other anomalies. Accordingly, each node may receive a different set of messages in the same round. In order to minimize collisions, we design adaptive algorithms that attempt to minimize the broadcast contention. To cope with unreliable communication, we augment the nodes with collision detectors and present a new classification of collision detectors in terms of accuracy and completeness, based on practical realities. We show in which cases consensus can be solved, and thus determine the requirements for a useful collision detector. Our algorithms, and the underlying wireless model, are validated with simulations based on a realistic 802.11 MAC layer implementation and a detailed radio propagation model. We analyze the performance of our algorithms under varying sized deployments, varying densities of deployment, and varying MAC layer parameters. We use our single-hop consensus protocol as the basis for solving consensus in a multi-hop network, demonstrating the resilience of our protocol to a challenging and noisy environment.To download the paper: pdf format  To download talk slides: ppt format Reconciling the Theory and Practice of UnReliable Wireless Broadcast by Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Tina NolteInternational Workshop on Assurance in Distributed Systems and Networks (ADSN), June, 2005Abstract: Theorists and practitioners have quite different perspectives on how wireless broadcast works. Theorists think about synchrony; practitioners think about backoff. Theorists assume reliable communication; practitioners worry about collisions. The examples are endless. Our goal is to begin to reconcile the theory and practice of wireless broadcast, in the presence of failures. We propose new models for wireless broadcast and use them to examine what makes a broadcast model good. In the process, we pose some interesting questions that will help to bridge the gap.To download the paper: pdf format

### Data Structures for Multiprocessor Shared-Memory Machines

 File Maintenance: When in Doubt, Change the Layout! by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, and Pablo MontesProceedings of the Symposium on Discrete Algorithms, (SODA), 2017 Dynamic task allocation in asynchronous shared memory by Dan Alistarh, James Aspnes, Michael Bender, Rati Gelashvili, and Seth GilbertProceedings of the Symposium on Discrete Algorithms (SODA), January, 2014 Asynchronous Gossip by Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. KowalskiJournal of the ACM, 60(2)April, 2013 How to Allocate Tasks Asynchronously by Dan Alistarh, Michael Bender, Seth Gilbert, and Rachid GuerraouiProceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2012 Mutual Exclusion with $O(\log^2\log n)$ Amortized Work by Michael A. Bender and Seth GilbertProceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2011Abstract: This paper presents a new algorithm for mutual exclusion in which each passage through the critical section costs amortized O(log2logn) RMRs with high probability. The algorithm operates in a standard asynchronous, local spinning, shared-memory model with an oblivious adversary. It guarantees that every process enters the critical section with high probability. The algorithm achieves its efficient performance by exploiting a connection between mutual exclusion and approximate counting. To download the paper: pdf format The Complexity of Renaming by Dan Alistarh, James Aspnes, Seth Gilbert, and Rachid GuerraouiProceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2011Abstract: We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove a \emphlocal lower bound of Ω(k) process steps for deterministic renaming into any namespace of size sub-exponential in k, where k is the number of participants. This bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic fetch-and-increment registers, queues and stacks. The proof of the bound is interesting in its own right, for it relies on the first reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement our local bound with a \emphglobal lower bound of Ω(klog(k/c)) on the total step complexity of renaming into a namespace of size ck, for any c ≥1. This applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter and fetch-and-increment implementations, all tight within logarithmic factors.To download the paper: pdf format Optimal-Time Adaptive Strong Renaming, with Applications to Counting by Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Morteza ZadimoghaddamProceedings of the International Conference on Principles of Distributed Computing (PODC), June, 2011Abstract: We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log3n. The second transforms any sorting network into a tight adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a tight adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such tight renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor). To download the paper: pdf format Generating Fast Indulgent Algorithms by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin TraversProceedings of the International Conference On Distributed Computing and Networking (ICDCN), January, 2011Abstract: Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficiently transform an algorithm that relies on synchronization into an algorithm that tolerates asynchronous executions. We introduce a transformation technique from synchronous algorithms to indulgent algorithms, which induces only a constant overhead in terms of time complexity in well-behaved executions. Our technique is based on a new abstraction we call an asynchrony detector, which the participating processes implement collectively. The resulting transformation works for a large class of colorless tasks, including consensus and set agreement. Interestingly, we also show that our technique is relevant for colored tasks, by applying it to the renaming problem, to obtain the first indulgent renaming algorithm. To download the paper: pdf format Fast Randomized Test-and-Set and Renaming by Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid GuerraouiProceedings of the International Symposium on Distributed Computing (DISC), September, 2010Abstract: This paper studies the read-write complexity of randomized renaming in an asynchronous environment. At the heart of our results stands a new adaptive implementation of a randomized test-and-set object, that requires polylogarithmic work per operation, with high probability. Interestingly, our implementation is anonymous, as it does not require process identifiers. Based on this object, we present a new renaming algorithm that ensures a tight namespace of n names using O( n log n log2 log n) total reads and writes, with high probability. This improves on the best previously known result by almost a quadratic factor. Our second application is the first adaptive randomized renaming protocol: it guarantees a namespace of size k (1 + ε) using O( k log4 k / log2 (1 + ε)) work, both with high probability. The protocol improves on existing deterministic solutions by providing a smaller namespace, and significantly lowering complexity. Both our renaming protocols are within logarithmic factors from the immediate Ω(n) lower bound on total work. To download the paper: pdf format Extensible Encoding of Type Hierarchies by Hamed S. Alavi, Seth Gilbert, and Rachid GuerraouiProceedings of the Symposium on Principles of Programming Languages (POPL), January, 2008Abstract: The subtyping test consists of checking whether a type t is a descendant of a type r (Agrawal et al. 1989). We study how to perform such a test efficiently, assuming a dynamic hierarchy when new types are inserted at run-time. The goal is to achieve time and space efficiency, even as new types are inserted. We propose an extensible scheme, named ESE, that ensures (1) efficient insertion of new types, (2) efficient subtyping tests, and (3) small space usage. On the one hand ESE provides comparable test times to the most efficient existing static schemes (e.g., Zibin et al. 2001). On the other hand, ESE has comparable insertion times to the most efficient existing dynamic scheme (Baehni et al. 2007), while ESE outperforms it by a factor of 2-3 times in terms of space usage. To download the paper: pdf format Concurrent Cache-Oblivious B-Trees by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. KuszmaulProceedings of the Seventeenth Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2005Abstract: The B-tree is the classic data structure for maintaining searchable data in external memory. Recent experiments have shown, however, that cache-oblivious (CO) B-trees can outperform traditional B-trees. Before CO B-trees can replace traditional B-trees in industrial applications, they must support concurrent operations. This paper presents the first study of concurrent cache-oblivious B-trees. We extend the cache-oblivious model to apply to a parallel or distributed setting. We transform both serial CO B-tree designs into concurrent data structures, and we consider both lock-based and lock-free approaches to concurrency. We develop three concurrent CO B-trees. The exponential CO B-tree uses write-locks but also supports nonblocking reads. This data structure supports insertions and searches/successor queries. Our second and third data structures are lock-based and lock-free variations on the packed-memory CO B-tree. These data structures support range queries and deletions in addition to the other operations. Each data structure achieves the same serial performance as the original data structure on which it is based. In a concurrent setting, we show that these data structures are linearizable, meaning that completed operations appear to an outside viewer as though they occurred in some serialized order. The lock-based data structures are also deadlock-free, and the lock-free data structure guarantees forward progress by at least one process.To download the paper: pdf format On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Charles E. LeisersonProceedings of the Sixteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2004Abstract: A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships on the fly'' for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan's functional inverse of Ackermann's function. By combining SP-order with Feng and Leiserson's serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T_1 work, and a critical-path length of T_\infty. When executed on P processors, we prove that SP-hybrid runs in O((T_1/P + PT_\infty)log n) expected time.To download the paper: pdf format

### Virtual Infrastructure for Ad Hoc Networks

 Self-Stabilizing Robot Formations over Unreliable Networks by Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina NolteTransactions on Autonomous and Adaptive Systems (TAAS), Special Issue on Self-Adaptive and Self-Organising Wireless Networking Systems, 4(3)2009 Self-Stabilizing Mobile Robot Formations with Virtual Nodes by Seth Gilbert, Nancy A. Lynch, Sayan Mitra, and Tina NolteProceedings of the Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), December, 2008To download the paper: pdf format Virtual Infrastructure for Collision-Prone Wireless Networks by Gregory Chockler, Seth Gilbert, and Nancy A. LynchProceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008Abstract: Wireless ad hoc networks pose several significant challenges: devices are unreliable; deployments are unpredictable; and communication is erratic. One proposed solution is Virtual Infrastructure, an abstraction in which unpredictable and unreliable devices are used to emulate reliable and predictable infrastructure. In this paper, we present a new protocol for emulating virtual infrastructure in collision-prone wireless networks. At the heart of our emulation is a convergent history agreement that tolerates lost messages and crash failures. It is designed specifically for ad hoc deployments, for example, the set of participants is a priori unknown. The convergent history agreement protocol is quite efficient, as each agreement instance completes in a constant number of communication rounds, and the size of the messages is constant, independent of the length of the execution. Building on the convergent history agreement protocol, our virtual infrastructure emulation introduces only constant overhead per virtual round emulated. We believe that the techniques developed in this paper help to bring virtual infrastructure one step closer to a reality. To download the paper: pdf format  To download talk slides: ppt format The Virtual Node Layer: A Programming Abstraction for Wireless Sensor Networks by Matthew Brown, Seth Gilbert, Nancy A. Lynch, Calvin Newport, Tina Nolte, and Michael SpindelProceedings of the the International Workshop on Wireless Sensor Network Architecture (WWSNA), April, 2007Abstract: The Virtual Node Layer programming abstraction provides programmable, predictable "virtual" nodes, emulated by unreliable mobile nodes. This simplifies the design and analysis of application for wireless sensor networks, as the layer can mask much of the uncertainty of the underlying network. In this paper, we describe a general VNLayer architecture, and then use this framework to implement a practical VNLayer prototype, optimized for real-world use. We then discuss our experience deploying this implementation on a testbed of hand-help computers, and in a custom-built packet-level simulator. We present a simple application (a virtual traffic light) to highlight the power and utility of our abstraction. We conclude with a survey of additional application that are well-suited to this abstraction. To download the paper: pdf format Virtual Infrastructure for Wireless Ad Hoc Networks by Seth Gilbert Ph. D. Thesis, MIT, 2007Abstract: One of the most significant challenges introduced by ad hoc networks is coping with the unpredictable deployment, uncertain reliability, and erratic communication exhibited by emerging wireless networks and devices. The goal of this thesis is to develop a set of algorithms that address these challenges and simplify the design of algorithms for ad hoc networks. In the first part of this thesis, I introduce the idea of Virtual Infrastructure, an abstraction that provides reliable and predictable components in an unreliable and unpredictable environment. This part assumes reliable communication, focusing primarily on the problems created by unpredictable motion and fault-prone devices. I introduce several types of virtual infrastructure, and present new algorithms based on the replicated-state-machine paradigm to implement these infrastructural components. In the second part of this thesis, I focus on the problem of developing virtual infrastructure for more realistic networks, in particular coping with the problem of unreliable communication. I introduce a new framework for modeling wireless networks based on the ability to detect collisions. I then present a new algorithm for implementing replicated state machines in wireless networks, and show how to use replicated state machines to implement virtual infrastructure even in an environment with unreliable communication.To download the paper: pdf format Timed Virtual Stationary Automata for Mobile Networks by Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy A. Lynch, and Tina Nolte9th International Conference on Principles of Distributed Systems (OPODIS), December, 2005Abstract: We define a programming abstraction for mobile networks called the Virtual Stationary Automata programming layer, consisting of mobile clients, virtual timed I/O automata called virtual stationary automata (VSAs), and a communication service connecting VSAs and client nodes. The VSAs are located at prespecified regions that tile the plane, defining a static virtual infrastructure. We present a self-stabilizing algorithm to emulate a timed VSA using the real mobile nodes that are currently residing in the VSA's region. We also describe examples of applications whose implementations benefit from the simplicity obtained through use of the VSA abstraction. To download the paper: pdf format GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer WelchDistributed Computing, 18(2):125–155, November, 2005Abstract: We present a new approach, the GeoQuorums approach, for implementing atomic read/write shared memory in mobile ad hoc networks. Our approach is based on associating abstract atomic objects with certain geographic locations. We assume the existence of focal points, geographic areas that are normally "populated" by mobile nodes. For example, a focal point may be a road junction, a scenic observation point, or a water resource in the desert. Mobile nodes that happen to populate a focal point participate in implementing a shared atomic object, using a replicated state machine approach. These objects, which we call focal point objects, are prone to occasional failures when the corresponding geographic areas are depopulated. The GeoQuorums algorithm uses the fault-prone focal point objects to implement atomic read/write operations on a fault-tolerant virtual shared object. The GeoQuorums algorithm uses a quorum-based strategy in which each quorum consists of a set of focal point objects. The quorums are used to maintain the consistency of the shared memory and to tolerate limited failures of the focal point objects, which may be caused by depopulation of the corresponding geographic areas. We present a mechanism for changing the set of quorums on the fly, thus improving efficiency. Overall, the new GeoQuorums algorithm efficiently implements read and write operations in a highly dynamic, mobile network. Autonomous Virtual Mobile Nodes by Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex A. Shvartsman, and Jennifer WelchProceeding of the 3rd Workshop on Foundations of Mobile Computing (DIAL-M-POMC), September, 2005Abstract: This paper presents a new abstraction for virtual infrastructure in mobile ad hoc networks. An Autonomous Virtual Mobile Node (AVMN) is a robust and reliable entity that is designed to cope with the inherent difficulties caused by processors arriving, leaving, and moving according to their own agendas, as well as with failures and energy limitations. There are many types of applications that may make use of the AVMN infrastructure: tracking, supporting mobile users, or searching for energy sources. The AVMN extends the focal point abstraction in DGLSW03 and the virtual mobile node abstraction in DGLSSW04. The new abstraction is that of a virtual general-purpose computing entity, an automaton that can make autonomous on-line decisions concerning its own movement. We describe a self-stabilizing implementation of this new abstraction that is resilient to the chaotic behavior of the physical processors and provides automatic recovery from any corrupted state of the system.To download the paper: pdf format Timed Virtual Stationary Automata for Mobile Networks by Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy A. Lynch, and Tina NolteProceeding of the 43rd Allerton Conference on Communication, Control, and Computing, September, 2005 (Invited) Abstract: We define a programming abstraction for mobile networks called the Virtual Stationary Automata programming layer, consisting of mobile clients, virtual timed I/O automata called virtual stationary automata (VSAs), and a communication service connecting VSAs and client nodes. The VSAs are located at prespecified regions that tile the plane, defining a static virtual infrastructure. We present a self-stabilizing algorithm to emulate a timed VSA using the real mobile nodes that are currently residing in the VSA's region. We also describe examples of applications whose implementations benefit from the simplicity obtained through use of the VSA abstraction. To download the paper: pdf format Brief Announcement: Virtual Stationary Automata for Mobile Networks by Shlomi Dolev, Limor Lahiani, Seth Gilbert, Nancy A. Lynch, and Tina NolteProceeding of the 24th Symposium on Principles of Distributed Computing (PODC), July, 2005 Virtual Mobile Nodes for Mobile Ad Hoc Networks by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, and Jennifer WelchProceeding of the 18th International Conference on Distributed Computing (DISC), October, 2004Abstract: One of the most significant challenges introduced by mobile networks is coping with the unpredictable motion and the unreliable behavior of mobile nodes. In this paper, we define the Virtual Mobile Node Abstraction, which consists of robust virtual nodes that are both predictable and reliable. We present the Mobile Point Emulator, a new algorithm that implements the Virtual Mobile Node Abstraction. This algorithm replicates each virtual node at a constantly changing set of real nodes, modifying the set of replicas as the real nodes move in and out of the path of the virtual node. We show that the Mobile Point Emulator correctly implements a virtual mobile node, and that it is robust as long as the virtual node travels through well-populated areas of the network. The Virtual Mobile Node Abstraction significantly simplifies the design of efficient algorithms for highly dynamic mobile ad hoc networks.To download the paper: pdf format  To download talk slides: ppt format Brief Announcement: Virtual Mobile Nodes for Mobile Ad Hoc Networks by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, and Jennifer WelchProceeding of the 23rd Symposium on Principles of Distributed Computing (PODC), July, 2004 GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer WelchProceeding of the 17th International Conference on Distributed Computing (DISC), October, 2003Abstract: We present a new approach, the GeoQuorums approach, for implementing atomic read/write shared memory in ad hoc networks. Our approach is based on abstract nodes associated with certain geographic locations. We assume the existence of focal points, geographic areas that are normally populated" by mobile hosts. For example, a focal point may be a road junction, a scenic observation point, or a water resource in the desert. Mobile hosts that happen to populate a focal point participate in implementing shared atomic put/get objects, using a replicated state machine approach. These objects are then used to implement atomic read/write operations. The GeoQuorums algorithm defines certain intersecting sets of focal points, known as quorums. The quorum systems are used to maintain the consistency of the shared memory. We present a mechanism for changing quorum systems on the fly, thus improving efficiency. Overall, the new GeoQuorums algorithm efficiently implements read and write operations in a highly dynamic, mobile network.To download the paper: pdf format  To download talk slides: ppt format