Seth Gilbert

2017

 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 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

2016

 A Secure Sharding Protocol For Open Blockchains by Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek SaxenaProceedings of the Conference on Computer and Communications Security (CCS), October, 2016 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 A New Approach to Incremental Cycle Detection and Related Problems by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. TarjanACM Trans. Algorithms, 12(2)2016

2015

 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 On Differentially Private Online Collaborative Recommendation Systems by Seth Gilbert, Xiao Liu, and Haifeng YuProceedings of the International Conference on Information Security and Cryptology (ICISC), Pages: 210–226November, 2015 Smoothed Analysis of Dynamic Networks by Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin C. NewportProceedings of the Symposium on Distributed Computing (DISC), Pages: 513–527October, 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 Cost-Oblivious Reallocation for Scheduling and Planning by Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth GilbertProceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages: 143–154June, 2015 Reallocation Problems in Scheduling by Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth GilbertAlgorithmica, 73(2):389–409, 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

2014

 Making Sense of Relativistic Distributed Systems by Seth Gilbert and Wojciech M. GolabProceedings of the Symposium on Distributed Computing (DISC), Pages: 361–375October, 2014 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 Cost-oblivious storage reallocation by Michael A. Bender, Martin Farach-Colton, Sandor P. Fekete, Jeremy T. Fineman, and Seth GilbertProceeding of the Symposium on Principles of Database Systems (PODS), June, 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 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 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 Tight Bounds for Asynchronous Renaming by Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid GuerraouiJ. ACM, 61(3):18:1–18:51, 2014

2013

 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 Reallocation problems in scheduling by Michael A. Bender, Martin Farach-Colton, Sandor P. Fekete, Jeremy T. Fineman, and Seth GilbertProceeding of the Symposium on Parallelism in Algorithms and Architectures (SPAA), 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 Asynchronous Gossip by Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. KowalskiJournal of the ACM, 60(2)April, 2013

2012

 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 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 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 Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin TraversAlgorithmica, 62(1-2):595-629, February, 2012 Perspectives on the CAP Theorem by Seth Gilbert and Nancy A. LynchIEEE Computer, 45(2):30-36, 2012

2011

 Meeting the deadline: On the complexity of fault-tolerant continuous gossip by Chryssis Georgiou, Seth Gilbert, and Dariusz R. KowalskiDistributed Computing, 24(5):223–244, December, 2011Abstract: In this paper, we introduce the problem of Continuous Gossip in which rumors are continually and dynamically injected throughout the network. Each rumor has a deadline, and the goal of a continuous gossip protocol is to ensure good quality of delivery, i.e., to deliver every rumor to every process before the deadline expires. Thus, a trivial solution to the problem of Continuous Gossip is simply for every process to broadcast every rumor as soon as it is injected. Unfortunately, this solution has a high per-round message complexity. Complicating matters, we focus our attention on a highly dynamic network in which processes may continually crash and recover. In order to achieve good per-round message complexity in a dynamic network, processes need to continually form and reform coalitions that cooperate to spread their rumors throughout the network. The key challenge for a Continuous Gossip protocol is the ongoing adaptation to the ever-changing set of active rumors and non-crashed process. In this work we show how to address this challenge; we develop randomized and deterministic protocols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal. 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 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 Confidential Gossip by Chryssis Georgiou, Seth Gilbert, and Dariusz KowalskiProceedings of the International Conference on Distributed Computing Systems (ICDCS), June, 2011Abstract: Epidemic gossip has proven a reliable and efficient technique for sharing information in a distributed network. Much of the reliability and efficiency derives from processes collaborating, sharing the work of distributing information. As a result of this collaboration, processes may receive information that was not originally intended for them. For example, a process may act as an intermediary, aggregating and forwarding messages from some set of sources to some set of destinations. But what if rumors are confidential? In that case, only processes that were originally intended to receive a rumor should be allowed to learn the rumor. This blatantly contradicts the basic premise of epidemic gossip, which assumes that processes can collaborate. In fact, if only processes in a rumor's "destination set" participate in gossiping that rumor, we show that high message complexity is unavoidable. In this paper, we propose a scheme in which each rumor is broken into multiple fragments using a very simple coding scheme: any given fragment provides no information about the rumor, while together, the fragments can be reassembled into the original rumor. The processes collaborate in disseminating the rumor fragments in such a way that no process outside of a rumor's destination set ever receives all the fragments of a rumor, while every process in the destination set eventually learns all the fragments. Notably, our solution operates in an environment where rumors are dynamically and continuously injected into the system and processes are subject to crashes and restarts. In addition, the scheme presented can tolerate a moderate amount of collusion among curious processes without too large an increase in cost. 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 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 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

2009

 Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin TraversProceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), December, 2009Abstract: Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. The complexity of set agreement in synchronous networks has also been a significant research challenge. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. In this paper, we analyze the complexity of set agreement in a such a "partially synchronous" setting, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. We also present an asymptotically matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony. By relating environments with differing degrees of synchrony, our simulation technique is of independent interest. In particular, it allows us to obtain a new lower bound on the complexity of early deciding k-set agreement complementary to that of Gafni et al. (2005), and to re-derive the combinatorial topology lower bound of Guerraoui et al. (2006) in an algorithmic way. 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 A New Approach to Incremental Topological Ordering by Michael A. Bender, Jeremy T. Fineman, and Seth GilbertProceedings of the Symposium on Discrete Algorithms (SODA), January, 2009Abstract: Let G=(V,E) be a directed acyclic graph (dag) with n = |V| and m=|E|. We say that a total ordering &le' on vertices V is a topological ordering if for every edge (u,v) in E, we have (u &le v). In this paper, we consider the problem of maintaining a topological ordering subject to dynamic changes to the underlying graph. That is, we begin with an empty graph G = (V, ) consisting of n nodes. The adversary adds m edges to the graph G, one edge at a time. Throughout this process, we maintain an online topological ordering of the graph G. In this paper, we present a new algorithm that has a total cost of O(n^2 log n) for maintaining the topological ordering throughout all the edge additions. At the heart of our algorithm is a new approach for maintaining the ordering. Instead of attempting to place the nodes in an ordered list, we assign each node a label that is consistent with the ordering, and yet can be updated efficiently as edges are inserted. When the graph is dense, our algorithm is more efficient than existing algorithms. By way of contrast, the best known prior algorithms achieve only O(min(m^1.5, n^2.5)) cost.To download the paper: pdf format Reconfigurable Distributed Storage for Dynamic Networks by Gregory Chockler, Seth Gilbert, Vincent C. Gramoli, Peter M. Musial, and Alex A. ShvartsmanJournal of Parallel and Distributed Computing, 69(1):100–116, January, 2009Abstract: This paper presents a new algorithm, RDS (Reconfigurable Distributed Storage), for implementing a reconfigurable DSM (distributed shared memory) in an asynchronous dynamic network. The algorithm guarantees atomic consistency (linearizability) in all asynchronous executions in the presence of arbitrary crash failures of processors and message loss and delays. The algorithm incorporates a classic quorum-based read/write algorithm and an optimized consensus protocol, based on Paxos. RDS achieves the design goals of: (i) allowing read and write operations to complete rapidly, and (ii) providing long-term fault tolerance through reconfiguration, a process that evolves the quorum configurations used by the read and write operations. The new algorithm improves on previously developed alternatives by using a more efficient reconfiguration protocol, thus guaranteeing better fault tolerance and faster recovery from network instability. This paper presents RDS, a formal proof of correctness, conditional performance analysis, and experimental results. 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

2007

 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 On the Message Complexity of Indulgent Consensus by Seth Gilbert, Rachid Guerraoui, and Dariusz KowalskiProceedings of the the 21st International Symposium on Distributed Computing (DISC), September, 2007Abstract: It is often best to plan for the worst and hope for the best. In this paper we devise efficient indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well-behaved, synchronous executions with few failures. We present two such algorithms: In synchronous executions, the first has optimal message complexity, using only O(n) messages, but runs in superlinear time of O(n^1+\epsilon). The second has a message complexity of O(n polylog n), but has an optimal running time, completing in O(f) rounds in synchronous executions with at most f failures. Both of these results improve significantly over the most message-efficient of previous indulgent consensus algorithms which have a message complexity of at least Omega(n^2) in well-behaved executions.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

2004

 The Quorum Deployment Problem by Seth Gilbert and Grzegorz MalewiczProceedings of the 8th International Conference on Principles of Distributed Systems (OPODIS), December, 2004Abstract: Quorum systems are commonly used to maintain the consistency of replicated data in a distributed system. Much research has been devoted to developing quorum systems with good theoretical properties, such as fault tolerance and high availability. However, even given a theoretically good quorum system, it is not obvious how to efficiently deploy such a system in a real network. This paper introduces a new combinatorial optimization problem, the Quorum Deployment Problem, and studies its complexity. We demonstrate that it is NP-hard to approximate the Quorum Deployment Problem within any factor of n^\delta, where n is the number of nodes in the distributed network and \delta>0. The problem is NP-hard in even the simplest possible distributed network: a one-dimensional line with metric cost. We begin to study algorithms for variants of the problem. Some variants can be solved optimally in polynomial time and some NP-hard variants can be approximated to within a constant factor.To download the paper: pdf format  To download talk slides: ppt format 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 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 RamboNodes for the Metropolitan Ad Hoc Network by Jake Beal and Seth GilbertProceedings of DIWANS Workshop, International Conference on Dependable Systems and Networks (DSN), July, 2004Abstract: We present an algorithm to store data robustly in a large, geographically distributed network. It depends on localized regions of data storage that move in response to changing conditions. For example, data may migrate away from failures or toward regions of high demand. The PersistentNode algorithm of Beal provides this service robustly, but with limited safety guarantees. We use the Rambo framework to transform PersistentNode into RamboNode, an algorithm that guarantees atomic consistency in exchange for increased cost and decreased liveness. A half-life analysis of RamboNode shows that it is robust against continuous low-rate failures. Finally, we provide experimental simulations for the algorithm on 2000 nodes, demonstrating how it services requests and examining how it responds to failures.To download the paper: pdf format  To download talk slides: ppt format