Seth Gilbert
Department of Computer Science
National University of Singapore
Seth Gilbert
Department of Computer Science
|
|
|
|
File Maintenance: When in Doubt, Change the Layout!
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, and Pablo Montes Proceedings 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 Zheng Distributed Computing, 30(2):103–125, 2017 |
|
A Secure Sharding Protocol For Open Blockchains
by Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena Proceedings 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 Newport Proceeding 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 Leong Proceedings 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 Young Proceedings of the Symposium on Discrete Algorithms (SODA), Pages: 636–654 January, 2016 |
|
A New Approach to Incremental Cycle Detection and Related Problems
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan ACM Trans. Algorithms, 12(2)2016 |
|
QProbe: Locating the Bottleneck in Cellular Communication
by Nimantha Baranasuriya, Vishnu Navda, Venkat Padmanabhan, and Seth Gilbert Proceedings 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 Yu Proceedings of the International Conference on Information Security and Cryptology (ICISC), Pages: 210–226 November, 2015 |
|
Smoothed Analysis of Dynamic Networks
by Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin C. Newport Proceedings of the Symposium on Distributed Computing (DISC), Pages: 513–527 October, 2015 |
|
The Computational Power of Beeps
by Seth Gilbert and Calvin C. Newport Proceedings of the Symposium on Distributed Computing (DISC), Pages: 31–46 October, 2015 |
|
Efficient Communication in Cognitive Radio Networks
by Seth Gilbert, Fabian Kuhn, Calvin Newport, and Chaodong Zheng Proceedings of the Symposium on Principles of Distributed Computing (PODC), Pages: 119–128 July, 2015 |
|
Cost-Oblivious Reallocation for Scheduling and Planning
by Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages: 143–154 June, 2015 |
|
Reallocation Problems in Scheduling
by Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert Algorithmica, 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 Young SIGACT News, 46(3):57–71, 2015 |
|
SybilCast: Broadcast on the Open Airwaves
by Seth Gilbert and Chaodong Zheng TOPC, 2(3):16, 2015 |
|
Making Sense of Relativistic Distributed Systems
by Seth Gilbert and Wojciech M. Golab Proceedings of the Symposium on Distributed Computing (DISC), Pages: 361–375 October, 2014 |
|
Who Are You? Secure Identities in Ad Hoc Networks
by Seth Gilbert, Calvin Newport, and Chaodong Zheng Proceeding 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 Young Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), Pages: 257–266 June, 2014 |
|
Cost-oblivious storage reallocation
by Michael A. Bender, Martin Farach-Colton, Sandor P. Fekete, Jeremy T. Fineman, and Seth Gilbert Proceeding 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 Rao Proceedings of the Conference on Distributed Computing in Sensor Systems (DCOSS), Pages: 101–110 May, 2014 |
|
Dynamic task allocation in asynchronous shared memory
by Dan Alistarh, James Aspnes, Michael Bender, Rati Gelashvili, and Seth Gilbert Proceedings 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. Newport Distributed Computing, 27(1):1–19, 2014 |
|
Tight Bounds for Asynchronous Renaming
by Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui J. ACM, 61(3):18:1–18:51, 2014 |
|
Broadcast in the Ad Hoc SINR Model
by Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin C. Newport Proceeding 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. Newport Proceedings 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 Gilbert Proceeding of the Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2013 |
|
SybilCast: broadcast on the open airwaves
by Seth Gilbert and Chaodong Zheng Proceeding of the Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2013 |
|
Asynchronous Gossip
by Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski Journal of the ACM, 60(2)April, 2013 |
|
Optimal Broadcast in Shared Spectrum Radio Networks
by Mohsen Ghaffari, Seth Gilbert, Calvin Newport, and Henry Tan Proceedings 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 Guerraoui Proceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2012 |
|
Aggregation in dynamic networks
by Alejandro Cornejo, Seth Gilbert, and Calvin C. Newport Proceedings 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. Newport Proceedings 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 Young Proceedings 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 Young Proceedings 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 Travers Algorithmica, 62(1-2):595-629, February, 2012 |
|
Perspectives on the CAP Theorem
by Seth Gilbert and Nancy A. Lynch IEEE Computer, 45(2):30-36, 2012 |
|
Meeting the deadline: On the complexity of fault-tolerant continuous gossip
by Chryssis Georgiou, Seth Gilbert, and Dariusz R. Kowalski Distributed Computing, 24(5):223–244, December, 2011 Abstract: 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 Gilbert Proceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2011 Abstract: 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 Guerraoui Proceedings of the Symposium on Foundations of Computer Science (FOCS), October, 2011 Abstract: 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 Newport Proceedings of the Symposium on Distributed Computing (DISC), September, 2011 Abstract: 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 Kowalski Proceedings of the International Conference on Distributed Computing Systems (ICDCS), June, 2011 Abstract: 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 Zadimoghaddam Proceedings of the International Conference on Principles of Distributed Computing (PODC), June, 2011 Abstract: 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 Newport Proceedings of the International Conference on Principles of Distributed Computing (PODC), June, 2011 Abstract: 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 Travers Proceedings of the International Conference On Distributed Computing and Networking (ICDCN), January, 2011 Abstract: 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 |
|
RAMBO: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
by Seth Gilbert, Nancy A. Lynch, and Alex A. Shvartsman Distributed Computing, 23(4):225-272, December, 2010 |
|
Fast Randomized Test-and-Set and Renaming
by Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui Proceedings of the International Symposium on Distributed Computing (DISC), September, 2010 Abstract: 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 |
|
Trusted Computing for Fault-Prone Wireless Networks
by Seth Gilbert and Dariusz Kowalski Proceedings of the International Symposium on Distributed Computing (DISC), September, 2010 Abstract: 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 |
|
How efficient can gossip be? (On the message complexity of resilient information exchange)
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Morteza Zadimoghaddam Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), July, 2010 Abstract: Gossip protocols, also known as epidemic dissemination schemes, are becoming increasingly popular in distributed systems. Yet, it has remained an open question to determine how efficient such protocols can be. Clearly, efficiency depends on the level of robustness required. We consider two different notions of robustness: the ability to tolerate oblivious failures, and the ability to tolerate adaptive failures. For oblivious failures, we present a new gossip protocol, CoordinatedGossip, that achieves optimal O(n) message complexity. This protocol makes novel use of the universe reduction technique to limit the message complexity, resulting in a protocol that is both fast and message-efficient. For adaptive failures, we present a new gossip protocol, TrickleGossip, that achieves near-optimal O(n log^3(n)) message complexity; to the best of our knowledge, this is the first epidemic-style protocol that can tolerate adaptive failures. The protocol makes use of a new spreading-and-sampling technique to carefully limit message complexity. We also show a direct relation between robustness and message complexity, demonstrating the following lower bound: every gossip protocol that can tolerate (1-epsilon)n failures, where may be a function of n, has message complexity at least (n log(1/epsilon)). For small epsilon, e.g., epsilon < 1/ loglog(n), this results in the first known super-linear lower bound on the message complexity of gossip. To download the paper: pdf format |
|
Meeting the deadline: On the complexity of fault-tolerant continuous gossip
by Chryssis Georgiou, Seth Gilbert, and Dariusz R. Kowalski Proceedings of the Symposium on Principles of Distributed Computing (PODC), July, 2010 Abstract: 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. To download the paper: pdf format |
|
Collaborative Scoring with Dishonest Participants
by Seth Gilbert, Rachid Guerraoui, Raezeh Malakouti Rad, and Morteza Zadimoghaddam Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), June, 2010 Abstract: Consider a set of players that are interested in collectively evaluating a set of objects. We develop a collaborative scoring protocol in which each player evaluates a subset of the objects, after which we can accurately predict each players' individual opinion of the remaining objects. The accuracy of the predictions is near optimal, depending on the number of objects evaluated by each player and the correlation among the players' preferences. A key novelty is the ability to tolerate malicious players. Surprisingly, the malicious players cause no (asymptotic) loss of accuracy in the predictions. In fact, our algorithm improves in both performance and accuracy over prior state-of-the-art collaborative scoring protocols that provided no robustness to malicious disruption. 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 Newport Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), June, 2010 Abstract: 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 |
|
Distributed Agreement with Optimal Communication Complexity
by Seth Gilbert and Dariusz Kowalski Proceedings of the Symposium on Discrete Algorithms (SODA), January, 2010 Abstract: We consider the problem of fault-tolerant agreement in a crash-prone synchronous system. We present a new randomized consensus algorithm that achieves optimal communication efficiency, using only O(n) bits of communication, and terminates in (almost optimal) time O(log n), with high probability. The same protocol, with minor modifications, can also be used in partially synchronous networks, guaranteeing correct behavior even in asynchronous executions, while maintaining efficient performance in synchronous executions. Finally, the same techniques also yield a randomized, fault-tolerant gossip protocol that terminates in O(log*n) rounds using O(n) messages (with bit complexity that depends on the data being gossiped). To download the paper: pdf format |
|
Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), December, 2009 Abstract: 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 Newport Proceeding of the 28th Symposium on Principles of Distributed Computing (PODC), August, 2009 Abstract: 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 Newport Proceedings of INFOCOM, April, 2009 Abstract: 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 Newport Theoretical 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 Gilbert Proceedings of the Symposium on Discrete Algorithms (SODA), January, 2009 Abstract: 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. Shvartsman Journal of Parallel and Distributed Computing, 69(1):100–116, January, 2009 Abstract: 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 Nolte Transactions 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 Nolte Proceedings of the Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), December, 2008 To download the paper: pdf format |
|
How to solve consensus in the smallest window of synchrony
by Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers 22nd International Symposium on Distributed Computing (DISC), September, 2008 Abstract: This paper finally answers the question of the minimum sized synchronous window needed to solve consensus in an otherwise asynchronous system. More specifically, we present the first optimally-resilient algorithm, ASAP, that solves consensus as soon as possible in an eventually synchronous system, i.e., a system that from some time GST onwards, delivers messages in a timely fashion. ASAP guarantees that, in an execution with at most f failures, every process decides no later than round GST + f+2, which is optimal. To download the paper: pdf format |
|
On the Complexity of Asynchronous Gossip
by Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz Kowalski Proceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008 Abstract: In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. This latter fact implies that there exist message-efficient asynchronous (randomized) consensus protocols, in the context of an oblivious adversary. To download the paper: pdf format |
|
Secure Communication over Radio Channels
by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport Proceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008 Abstract: 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 |
|
Virtual Infrastructure for Collision-Prone Wireless Networks
by Gregory Chockler, Seth Gilbert, and Nancy A. Lynch Proceeding of the 27th Symposium on Principles of Distributed Computing (PODC), August, 2008 Abstract: 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 |
|
Consensus and Collision Detectors in Radio Networks
by Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Tina Nolte Distributed Computing, 21(1):55–84, June, 2008 Abstract: 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. |
|
Extensible Encoding of Type Hierarchies
by Hamed S. Alavi, Seth Gilbert, and Rachid Guerraoui Proceedings of the Symposium on Principles of Programming Languages (POPL), January, 2008 Abstract: 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 |
|
Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)
by Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport Proceedings of the the 21st International Symposium on Distributed Computing (DISC), September, 2007 Abstract: 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 Kowalski Proceedings of the the 21st International Symposium on Distributed Computing (DISC), September, 2007 Abstract: 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 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 Spindel Proceedings of the the International Workshop on Wireless Sensor Network Architecture (WWSNA), April, 2007 Abstract: 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, 2007 Abstract: 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 |
|
Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks
by Seth Gilbert, Rachid Guerraoui, and Calvin Newport Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS), December, 2006 Abstract: 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 Gilbert Proceedings of the 14th Annual European Symposium on Algorithms (ESA), September, 2006 Abstract: 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 |
|
Playing Games in Many Possible Worlds
by Matthew Lepinski, David Liben-Nowell, Seth Gilbert, and April Rasala Lehman Proceedings of the Seventh ACM Conference on Electronic Commerce (EC), June, 2006 Abstract: In traditional game theory, players are typically endowed with exogenously given knowledge of the structure of the game—either full omniscient knowledge or partial but fixed information. In real life, however, people are often unaware of the utility of taking a particular action until they perform research into its consequences. In this paper, we model this phenomenon. We imagine a player engaged in a question-and-answer session, asking questions both about his or her own preferences and about the state of reality; thus we call this setting Socratic Games. In a Socratic game, players begin with an a priori probability distribution over many possible worlds, with a different utility function for each world. Players can make queries, at some cost, to learn partial information about which of the possible worlds is the actual world, before choosing an action. We consider two query models: (1) an unobservable-query model, in which players learn only the response to their own queries, and (2) an observable-query model, in which players also learn which queries their opponents made. The results in this paper consider cases in which the underlying worlds of a two-player Socratic game are either constant-sum games or strategically zero-sum games, a class that generalizes constant-sum games to include all games in which the sum of payoffs depends linearly on the interaction between the players. When the underlying worlds are constant sum, we give polynomial-time algorithms to find Nash equilibria in both the observable- and unobservable-query models. When the worlds are strategically zero sum, we give efficient algorithms to find Nash equilibria in unobservable-query Socratic games and correlated equilibria in observable-query Socratic games. To download the paper: pdf format |
|
Communication-Efficient Probabilistic Quorum Systems
by Gregory Chockler, Seth Gilbert, and Boaz Patt-Shamir Proceedings of the International Workshop on Foundations and Algorithms for Wireless Networking (FAWN), March, 2006 Abstract: 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 |
|
Reconfigurable Distributed Storage for Dynamic Networks
by Gregory Chockler, Seth Gilbert, Vincent C. Gramoli, Peter M. Musial, and Alex A. Shvartsman 9th International Conference on Principles of Distributed Systems (OPODIS), December, 2005 Abstract: 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. 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 Nolte 9th International Conference on Principles of Distributed Systems (OPODIS), December, 2005 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 |
|
GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks
by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer Welch Distributed Computing, 18(2):125–155, November, 2005 Abstract: 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. |
|
A Middleware Framework for Robust Applications in Wireless Ad Hoc Networks
by Gregory Chockler, Murat Demirbas, Seth Gilbert, and Calvin Newport Proceeding 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 |
|
Autonomous Virtual Mobile Nodes
by Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex A. Shvartsman, and Jennifer Welch Proceeding of the 3rd Workshop on Foundations of Mobile Computing (DIAL-M-POMC), September, 2005 Abstract: 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 Nolte Proceeding 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 Nolte Proceeding of the 24th Symposium on Principles of Distributed Computing (PODC), July, 2005 |
|
Concurrent Cache-Oblivious B-Trees
by Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul Proceedings of the Seventeenth Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2005 Abstract: 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 |
|
Consensus and Collision Detectors in Wireless Ad Hoc Networks
by Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport, and Tina Nolte 24th Annual Symposium on the Principles of Distributed Computing (PODC), July, 2005 Abstract: 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 |
|
Etna: a fault-tolerant algorithm for atomic mutable DHT data
by Athicha Muthitacharoen, Seth Gilbert, and Robert Morris Technical Report , MIT, June, 2005 Abstract: This paper presents Etna, an algorithm for atomic reads and writes of replicated data stored in a distributed hash table. Etna correctly handles dynamically changing sets of replica hosts, and is optimized for reads, writes, and reconfiguration, in that order. |
|
Reconciling the Theory and Practice of UnReliable Wireless Broadcast
by Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Tina Nolte International Workshop on Assurance in Distributed Systems and Networks (ADSN), June, 2005 Abstract: 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 |
|
The Quorum Deployment Problem
by Seth Gilbert and Grzegorz Malewicz Proceedings of the 8th International Conference on Principles of Distributed Systems (OPODIS), December, 2004 Abstract: 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 Welch Proceeding of the 18th International Conference on Distributed Computing (DISC), October, 2004 Abstract: 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 Welch Proceeding 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. Leiserson Proceedings of the Sixteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2004 Abstract: 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 Gilbert Proceedings of DIWANS Workshop, International Conference on Dependable Systems and Networks (DSN), July, 2004 Abstract: 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 |
|
GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks
by Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer Welch Proceeding of the 17th International Conference on Distributed Computing (DISC), October, 2003 Abstract: 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 |
|
RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
by Seth Gilbert, Nancy A. Lynch, and Alex A. Shvartsman Proceedings of the International Conference on Dependable Systems and Networks (DSN), June, 2003 Abstract: This paper presents a new algorithm implementing reconfigurable atomic read/write memory for highly dynamic environments. The original Rambo algorithm, recently developed by Lynch and Shvartsman, guarantees atomicity for arbitrary patterns of asynchrony, message loss, and node crashes. Rambo II implements a different approach to establishing new configurations: instead of operating sequentially, the new algorithm reconfigures aggressively, transferring information from old configurations to new configurations in parallel. This improvement substantially reduces the time to establish a new configuration and to remove obsolete configurations. This, in turn, substantially increases fault tolerance and reduces the latency of read/write operations when the network is unstable or reconfiguration is bursty. This paper presents Rambo II, a correctness proof, and a conditional analysis of its performance. Preliminary empirical studies illustrate the advantages of the new algorithm. To download the paper: pdf format To download talk slides: ppt format |
|
RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
by Seth Gilbert Master's Thesis, MIT, 2003 To download the paper: pdf format |
|
Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
by Seth Gilbert and Nancy A. Lynch SigAct News, June, 2002 Abstract: When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model. To download the paper: pdf format |
