Self-stabilizing population protocols (2009)
Dana Angluin, James Aspnes, Michael J. Fischer, Hong Jiang
This paper studies self-stabilization in networks of anonymous, asynchronously interacting nodes where the size of the network is unknown. Constant-space protocols are given for Dijkstra-style...
Learning acyclic probabilistic circuits using test paths (2009)
Dana Angluin, James Aspnes, Jiang Chen
We define a model of learning probabilistic acyclic circuits using value injection queries, in which fixed values are assigned to an arbitrary subset of the wires and the value on the single output...
Approximate Shared-Memory Counting Despite a Strong Adversary (2009)
A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed ɛ, the counter achieves a relative...
Network Construction with Subgraph Connectivity Constraints (2009)
Dana Angluin, James Aspnes, Lev Reyzin
Abstract. We consider the problem of building a network given connectivity constraints. A network designer is given a set of vertices V and constraints Si ⊆ V, and seeks to build the lowest cost...
Approximate Shared-Memory Counting Despite a Strong Adversary ∗ (2009)
A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed ɛ, the counter achieves a relative...
James Aspnes, Hagit Attiya, Keren Censor
This paper presents a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers, in the presence of a strong adversary....
Optimally learning social networks with activations and suppressions (2009)
Dana Angluin, James Aspnes, Lev Reyzin
Abstract. In this paper we consider the problem of learning hidden independent cascade social networks using exact value injection queries. These queries involve activating and suppressing agents in...
Collisions Lead to Shallower Decision Trees (2009)
James Aspnes, Murat Demirbas, Atri Rudra
Abstract. We study the following generalization of decision trees, which we call k +-decision trees (where k � 1 is an integer). The algorithms are now allowed to query any arbitrary subset of the...
Combining Shared Coin Algorithms (2009)
James Aspnes, Hagit Attiya, Keren Censor
This paper shows that shared coin algorithms can be combined to optimize several complexity measures, even in the presence of a strong adversary. By combining shared coins of Bracha and Rachman [10]...
Distributed Computing manuscript No. (will be inserted by the editor) (2009)
Dana Angluin, James Aspnes, David Eisenstat, Dana Angluin, James Aspnes, David Eisenstat
Abstract Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents...
Department of Computer Science, (2009)
James Aspnes, Murat Demirbas, Atri Rudra, Steve Uurtamo
We study the following generalization of decision trees, which we call k +-decision trees (where k � 1 is an integer). The algorithms are now allowed to query any arbitrary subset of the n input...
Max Registers, Counters, and Monotone Circuits (2009)
James Aspnes, Hagit Attiya, Keren Censor
A method is given for constructing a max register, a linearizable, wait-free concurrent data structure that supports a write operation and a read operation that returns the largest value previously...
Approximate shared-memory counting despite a strong adversary (2009)
A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed ɛ, the counter achieves a relative...
Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network? (2008)
James Aspnes, Navin Rustagi, Jared Saia
Abstract. Consider the following game between a worm and an alert 3 over a network of n nodes. Initially, no nodes are infected or alerted and each node in the network is a special detector node...
The Computational Power of Collision Detection (2008)
James Aspnes, Murat Demirbas, Atri Rudra
We show that packet collisions, often considered a nuisance in wireless sensor networks, can be used to reduce the cost of computing aggregate functions of distributed data. Formally, we consider a...
Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network? (2008)
James Aspnes, Navin Rustagi, Jared Saia
Abstract. Consider the following game between a worm and an alert 3 over a network of n nodes. Initially, no nodes are infected or alerted and each node in the network is a special detector node...
Abstract Exposing Computationally-Challenged Byzantine Impostors (2008)
Internet protocols permit a single machine to masquerade as many, allowing an adversary to appear to control more nodes than it actually does. The possibility of such Sybil attacks has been taken to...
Dana Angluin, Michael J. Fischer, James Aspnes, René Peralta, Zoë Diamadi
We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of...
Towards a Theory of Data Entanglement ⋆ (Extended Abstract) (2008)
James Aspnes, Joan Feigenbaum, R Yampolskiy, Sheng Zhong
Abstract. We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-ornothing integrity (AONI) that binds the users ’ data in a way...
Abstract Path-Independent Load Balancing With Unreliable Machines (2008)
James Aspnes, Yang Richard, Yang Yitong Yin
We consider algorithms for load balancing on unreliable machines. The objective is to optimize the two criteria of minimizing the makespan and minimizing job reassignments in response to machine...
ABSTRACT The Expansion and Mixing Time of Skip Graphs with Applications (2008)
We prove that with high probability a skip graph contains a 4-regular expander as a subgraph, and estimate the quality of the expansion via simulations. As a consequence skip graphs contain a large...
Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network? (2008)
James Aspnes, Navin Rustagi, Jared Saia
Abstract. Consider the following game between a worm and an alert 3 over a network of n nodes. Initially, no nodes are infected or alerted and each node in the network is a special detector node...
O(log n)-time overlay network construction from graphs with outdegree 1 (2008)
Abstract. A fast self-stabilizing algorithm is described to rapidly construct a balanced overlay network from a directed graph initially with out-degree 1, a natural starting case that arises in...
ABSTRACT Fast Construction of Overlay Networks (2008)
Dana Angluin, Yinghua Wu, James Aspnes, Yitong Yin
An asynchronous algorithm is described for rapidly constructing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other directly through an underlying...
Fast Computation by Population Protocols With a (2008)
Dana Angluin, James Aspnes, David Eisenstat
Abstract. Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents...
ABSTRACT Wait-Free Consensus with Infinite Arrivals (2008)
A randomized algorithm is given that solves the wait-free consensus problem for a shared-memory model with infinitely many processes. The algorithm is based on a weak shared coin algorithm that uses...
Dana Angluin, Michael J. Fischer, James Aspnes, René Peralta, Zoë Diamadi
We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of...
BEATCS no 90 THE EATCS COLUMNS (2008)
Mario Mavronicolas, James Aspnes, Shlomi Dolev, Chryssis Georgiou, Costas Busch, Panagiota Fatourou, ...
Distributed Computing Theory continues to be one of the most active research fields in Theoretical Computer Science today. Besides its foundational topics (such as consensus and synchronization), it...
Chapter 8 OPPORTUNITY COST ALGORITHMS FOR COMBINATORIAL AUCTIONS (2008)
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Abstract Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder...
routing protocols General Terms (2008)
James Aspnes, Jonathan Kirsch, Arvind Krishnamurthy
We describe a load-balancing mechanism for assigning elements to servers in a distributed data structure that supports range queries. The mechanism ensures both load-balancing with respect to an...
Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network? (2008)
James Aspnes, Navin Rustagi, Jared Saia
Consider the following game between a worm and an alert1 over a network of n nodes. Initially, no nodes are infected or alerted and each node in the network is a special detector node independently...
James Aspnes, Maurice He Rlihy
Abstract. Many fundamental multi-processor coordination problems can be expressed as cozwtmg problems: Processes must cooperate to assign successive values from a gwen range, such as addresses in...
routing protocols General Terms (2008)
James Aspnes, Jonathan Kirsch, Arvind Krishnamurthy
We describe a load-balancing mechanism for assigning elements to servers in a distributed data structure that supports range queries. The mechanism ensures both load-balancing with respect to an...
ABSTRACT Learning a Circuit by Injecting Values [Extended Abstract] (2008)
Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu
We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of...
O(log n)-time overlay network construction from graphs with outdegree 1 (2008)
A fast self-stabilizing algorithm is described to rapidly construct a balanced overlay network from a directed graph initially with out-degree 1, a natural starting case that arises in peerto-peer...
Towards a Theory of Data Entanglement ⋆,⋆⋆ Abstract (2008)
James Aspnes, Joan Feigenbaum, R Yampolskiy, Sheng Zhong
We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-or-nothing integrity (AONI) that binds the users ’ data in a way that makes...
Ranged hash functions and the price of churn (2008)
James Aspnes, Muli Safra, Yitong Yin
Ranged hash functions generalize hash tables to the setting where hash buckets may come and go over time, a typical case in distributed settings where hash buckets may correspond to unreliable...
A simple population protocol for fast robust approximate majority (2008)
Dana Angluin, James Aspnes, David Eisenstat
Abstract We describe and analyze a 3-state one-way population protocol to compute approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an...
Distributed Algorithms for Maintaining Dynamic Expander Graphs (2008)
We consider the problem of maintaining expansion in an overlay network with dynamic node insertions. We study this problem in two models: one, where insertions are chosen benevolently, and the other,...
Randomized Consensus in Expected O(n log n) Individual Work (2008)
James Aspnes, Hagit Attiya, Keren Censor
This paper presents a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers, in the presence of a strong adversary....
A simple population protocol for fast robust approximate majority (2008)
Dana Angluin, James Aspnes, David Eisenstat
Abstract. We describe and analyze a 3-state one-way population protocol for approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial...
A simple population protocol for fast robust approximate majority (2008)
Dana Angluin, James Aspnes, David Eisenstat
Abstract. We describe and analyze a 3-state one-way population protocol for approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial...
A simple population protocol for fast robust approximate majority (2008)
Dana Angluin, James Aspnes, David Eisenstat
Abstract. We describe and analyze a 3-state one-way population protocol for approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial...
Randomized Load Balancing by Joining and Splitting Bins (2008)
We study the following load balancing game: initially there is only one bin, which contains all the load; and at each time, either one of the bins is split into two bins, or two bins are joined into...
On the Carpool Problem - Long-Term Behaviour Of a Chip Game Concerning Scheduling (2007)
Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
We study the carpool problem, suggested by Fagin and Williams [15] as an abstraction of the notion of fairness in on-line scheduling. In this abstraction, a set of n people form a carpool. On each...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-topoint and multicast) where the goal is to minimize the required bandwidth. We concentrate on the...
We consider the problem of designing an overlay network and routing mechanism that permits nding resources eciently in a peer-to-peer system. We argue that many existing approaches to this problem...
James Aspnes, Julia Hartling, Ming-yang Kao, Junhyong Kim, Gauri Shah
In modern biology, one of the most important research problems is to understand how protein sequences fold into their native 3D structures. To investigate this problem at a high level, one wishes to...
OPERATIONS PER PROCESSOR (2007)
Abstract. This paper presents a new randomized algorithm for achieving consensus among asynchronous processors that communicate by reading and writing shared registers. The fastest previously known...
Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long...
James Aspnes, David F. Fischer, Michael J. Fischer, Ming-yang Kao
This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the...
Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long...
James Aspnes, David F. Fischer, Michael J. Fischer, Ming-yang Kao
This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agentbased model for a stock market where the...
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
1 Supported in part by NSF Grant CCR-9896165. 2
shared coins Consensus is a decision problem in which n processors, each starting with a value not known to the others, must collectively agree on a single value. If the initial values are equal, the...
Exposing Computationally-Challenged Byzantine Impostors (2007)
James Aspnes, Collin Jackson, Arvind Krishnamurthy
Internet protocols permit a single machine to masquerade as many, allowing an adversary to appear to control more nodes than it actually does. The possibility of such Sybil attacks has been taken to...
Angluin, Dana, Aspnes, James, Diamadi, Zoe, Fischer, Michael J., Peralta, Rene
Urn automata are a new class of automata consisting of an input tape, a finite-state controller, and an urn containing tokens with a finite set of colors, where the finite-state controller can sample...
Learning large-alphabet and analog circuits with value injection queries (2007)
Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin
Abstract. We consider the problem of learning an acyclic discrete circuit with n wires, fan-in bounded by k and alphabet size s using value injection queries. For the class of transitively reduced...
Path-independent load balancing with unreliable machines (2007)
James Aspnes, James Aspnes, Yang Richard, Yang Richard, Yang Yitong Yin, Yang Yitong Yin
We consider algorithms for load balancing on unreliable machines. The objective is to optimize the two criteria of minimizing the makespan and minimizing job reassignments in response to machine...
Learning large-alphabet and analog circuits with value injection queries (2007)
Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin
We consider the problem of learning an acyclic discrete circuit with n wires, fan-in bounded by k and alphabet size s using value injection queries. For the class of transitively reduced circuits, we...
Learning large-alphabet and analog circuits with value injection queries (2007)
Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin
Abstract. We consider the problem of learning an acyclic discrete circuit with n wires, fan-in bounded by k and alphabet size s using value injection queries. For the class of transitively reduced...
Learning large-alphabet and analog circuits with value injection queries (2007)
Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin
We consider the problem of learning an acyclic discrete circuit with n wires, fan-in bounded by k and alphabet size s using value injection queries. For the class of transitively reduced circuits, we...
Dana Angluin, James Aspnes, David Eisenstat
We consider the model of population protocols introduced by Angluin et al. [AAD + 04], in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way...
Learning large-alphabet and analog circuits with value injection queries (2007)
Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin
1 Introduction We consider learning large-alphabet and analog acyclic circuits in the valueinjection model introduced in [5]. In this model, we may inject values of our choice on any subset of wires,...
The computational power of population protocols (2006)
Angluin, Dana, Aspnes, James, Eisenstat, David, Ruppert, Eric
We consider the model of population protocols introduced by Angluin et al., in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions...
Path-independent load balancing with unreliable machines (2006)
Aspnes, James, Yang, Yang Richard, Yin, Yitong
We consider algorithms for load balancing on unreliable machines. The objective is to optimize the two criteria of minimizing the makespan and minimizing job reassignments in response to machine...
Fast computation by population protocols with a leader (2006)
Dana Angluin, James Aspnes, David Eisenstat, Dana Angluin, James Aspnes, David Eisenstat
Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in...
Fast computation by population protocols with a leader (2006)
Dana Angluin, James Aspnes, David Eisenstat
Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in...
A theory of network localization (2006)
James Aspnes, Tolga Eren, David K. Goldenberg, Student Member, A. Stephen Morse, Walter Whiteley, ...
Abstract—In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring...
Greedy Routing in Peer-to-Peer Systems ∗ (2006)
James Aspnes, Zoë Diamadi, Gauri Shah
We consider the problem of designing an overlay network and routing mechanism that permits finding resources efficiently in a peer-to-peer system. We argue that many existing approaches to this...
Learning a circuit by injecting values (2006)
We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of...
James Aspnes, Julia Hartling, Ming-yang Kao, Junhyong Kim, Gauri Shah
In modern biology, one of the most important research problems is to understand how protein sequences fold into their native 3D structures. To investigate this problem at a high level, one wishes to...
Fast computation by population protocols with a leader (2006)
Dana Angluin, James Aspnes, David Eisenstat
Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in...
Learning a circuit by injecting values (2006)
Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu
We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of...
Distance-Sensitive Information Brokerage in Sensor Networks (2006)
Funke, Stefan, Guibas, Leonidas, Nguyen, An, Wang, Yusu, Gibbons, Phillip B., Abdelzaher, Tarek F., ...
In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of interactions...
Learning a circuit by injecting values (2006)
We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of...
Learning a circuit by injecting values (2006)
Dana Angluin, James Aspnes, Jiang Chen
We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of...
Exposing Computationally-Challenged Byzantine Impostors (2005)
James Aspnes, Collin Jackson, Arvind Krishnamurthy, James Aspnes, Collin Jackson, Arvind Krishnamurthy
Internet protocols permit a single machine to masquerade as many, allowing an adversary to appear to control more nodes than it actually does. The possibility of such Sybil attacks has been taken to...
Spreading alerts quietly and the subgroup escape problem (2005)
James Aspnes, Zoë Diamadi, Kristian Gjøsteen, René Peralta, Aleksandr Yampolskiy, James Aspnes, ...
We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit commitment scheme, which is AND-homomorphic. It has not been known how...
Self-stabilizing Population Protocols (2005)
Dana Angluin James, James Aspnes, Michael J. Fischer, Hong Jiang
Self-stabilization in a model of anonymous, asynchronous interacting agents deployed in a network of unknown size is considered. Dijkstra-style round-robin token circulation can be done...
Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, (2005)
Hong Jiang And, Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, ...
We consider a scenario in which anonymous, finite-state sensing devices are deployed in an ad-hoc communication network of arbitrary size and unknown topology, and explore what properties of the...
Spreading Alerts Quietly (2005)
And The Subgroup, James Aspnes, Zoë Diamadi, Kristian Gjøsteen, René Peralta
We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit commitment scheme, which is AND-homomorphic. It has not been known how...
Spreading alerts quietly and the subgroup escape problem (2005)
Abstract. We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit commitment scheme, which is AND-homomorphic. It has not been...
Ittai Abraham, James Aspnes, Jian Yuan
Abstract. We describe a new data structure, the Skip B-Tree that combines the advantages of skip graphs with features of traditional B-trees. A skip B-Tree provides efficient search, insertion and...
Distributed Computing manuscript No. (will be inserted by the editor) (2005)
Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, René Peralta
Abstract The computational power of networks of small resource-limited mobile agents is explored. Two new models of computation based on pairwise interactions of finite-state agents in populations of...
Stably computable properties of network graphs (2005)
Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, René Peralta
Abstract. We consider a scenario in which anonymous, finite-state sensing devices are deployed in an ad-hoc communication network of arbitrary size and unknown topology, and explore what properties...
On the power of anonymous one-way communication (2005)
Dana Angluin, James Aspnes, David Eisenstat
Abstract. We consider a population of anonymous processes communicating via anonymous message-passing, where the recipient of each message is chosen by an adversary and the sender is not identified...
Self-stabilizing population protocols (2005)
Dana Angluin, James Aspnes, Michael J. Fischer, Hong Jiang
This paper studies self-stabilization in networks of anonymous, asynchronously interacting agents where the size of the network is unknown. Dijkstra-style round-robin token circulation can be done...
Spreading alerts quietly and the subgroup escape problem (2005)
James Aspnes, Zoë Diamadi, Kristian Gjøsteen, René Peralta, Aleksandr Yampolskiy
Abstract. We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit commitment scheme, which is AND-homomorphic. It has not been...
Self-stabilizing population protocols (2005)
Dana Angluin, James Aspnes, Michael J. Fischer, Hong Jiang
Abstract. Self-stabilization in a model of anonymous, asynchronous interacting agents deployed in a network of unknown size is considered. Dijkstra-style round-robin token circulation can be done...
Spreading alerts quietly and the subgroup escape problem (2005)
James Aspnes, Zoë Diamadi, Kristian Gjøsteen, René Peralta, R Yampolskiy
Abstract. We introduce a new cryptographic primitive called a blind coupon mecha-nism (BCM). In effect, a BCM is an authenticated bit commitment scheme, which is AND-homomorphic. It has not been...
Spreading alerts quietly and the subgroup escape problem (2005)
James Aspnes, Zoë Diamadi, Kristian Gjøsteen, René Peralta
Abstract. We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit commitment scheme, which is AND-homomorphic. It has not been...
Stably computable properties of network graphs (2005)
Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, René Peralta
We consider a scenario in which anonymous, finite-state sensing devices are deployed in an ad-hoc communication network of arbitrary size and unknown topology, and explore what properties of the...
The expansion and mixing time of skip graphs with applications (2005)
We prove that with high probability a skip graph contains a 4-regular expander as a subgraph and estimate the quality of the expansion via simulations. As a consequence, skip graphs contain a large...
Ittai Abraham, James Aspnes, Jian Yuan
Abstract. We describe a new data structure, the Skip B-Tree, that combines the advantages of skip graphs with features of traditional Btrees. A skip B-Tree provides efficient search, insertion and...
On the power of anonymous one-way communication (2005)
Dana Angluin, James Aspnes, David Eisenstat
Abstract. We consider a population of anonymous processes communicating via anonymous message-passing, where the recipient of each message is chosen by an adversary and the sender is not identified...
Inoculation Strategies for Victims of Viruses and the Sum-of-Squares Partition Problem (2005)
Kevin Chang, Aleksandr Yampolskiy, James Aspnes, James Aspnes, Kevin Chang Aleks, R Yampolskiy
We propose a simple game for modeling containment of the spread of viruses in a graph of n nodes. Each node must choose to either install anti-virus software at some known cost C, or risk infection...
The expansion and mixing time of skip graphs with applications (2005)
We prove that with high probability a skip graph contains a 4-regular expander as a subgraph, and estimate the quality of the expansion via simulations. As a consequence skip graphs contain a large...
Forward ………………………………………………………………………………........i (2005)
Rida Bazzi, James Aspnes, Y. H. Lee, H. Lee, A. Alagöz, E. Ahi, ...
This technical report contains the papers that were presented in the poster session of the
The expansion and mixing time of skip graphs with applications (2005)
We prove that with high probability a skip graph contains a 4-regular expander as a subgraph and estimate the quality of the expansion via simulations. As a consequence, skip graphs contain a large...
Load balancing and locality in range-queriable data structures (2004)
James Aspnes, Jonathan Kirsch, Arvind Krishnamurthy
We describe a load-balancing mechanism for assigning elements to servers in a distributed data structure that supports range queries. The mechanism ensures both load-balancing with respect to an...
On the computational complexity of sensor network localization (2004)
James Aspnes, David Goldenberg, Yang Richard Yang
Abstract. Determining the positions of the sensor nodes in a network is essential to many network functionalities such as routing, coverage and tracking, and event detection. The localization problem...
Computation in networks of passively mobile finite-state sensors (2004)
Dana Angluin, James Aspnes, Zo E Diamadi, Michael J. Fischer, Ren E Peralta
We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of...
Towards a Theory of Data Entanglement (2004)
Joan Feigenbaum, Aleksandr Yampolskiy, Sheng Zhong, James Aspnes, James Aspnes, Joan Feigenbaum Aleks, ...
We propose a formal model for data entanglement as used in storage systems like Dagster [25] and Tangler [26]. These systems split data into blocks in such a way that a single block becomes a part of...
On the Computational Complexity of Sensor Network Localization (2004)
James Aspnes, David Goldenberg, Yang Richard Yang
Determining the positions of the sensor nodes in a network is essential to many network functionalities such as routing, coverage and tracking, and event detection. The localization problem for...
Computation in Networks of Passively Mobile Finite-State Sensors (2004)
Dana Angluin, James Aspnes, Zoe Diamadi
Machine of Berry and Boudol [2] is an abstract machine designed to model a situation in which components move about a system and communicate when they come See [5, 6] for surveys of Petri nets.
Relationships between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems (2004)
James Aspnes, Faith Fich, Eric Ruppert
We study the power of reliable anonymous distributed systems, where processes do not fail, do not have identifiers, and run identical programmes. We are interested specifically in the relative powers...
Towards a Theory of Data Entanglement (2004)
Exte Nd Ed, James Aspnes, Joan Feigenbaum, R Yampolskiy, Sheng Zhong
We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-or-nothing integrity (AONI) that binds the users' data in a way that...
and the Sum-of-Squares Partition Problem (2004)
James Aspnes, Kevin Chang, Aleksandr Yampolskiy, James Aspnes, Kevin Chang Aleks, R Yampolskiy
Abstract We propose a simple game for modeling containment of the spread of viruses in a graph of nnodes. Each node must choose to either install anti-virus software at some known cost C, or...
On the computational complexity of sensor network localization (2004)
James Aspnes, James Aspnes, David Goldenberg, David Goldenberg, Yang Richard Yang, Yang Richard Yang
Abstract Determining the positions of the sensor nodes in a network is essential to many networkfunctionalities such as routing, coverage and tracking, and event detection. The localization problem...
Relationships between broadcast and shared memory in reliable anonymous distributed systems (2004)
Abstract. We study the power of reliable anonymous distributed systems, where processes do not fail, do not have identifiers, and run identical programmes. We are interested specifically in the...
On the computational complexity of sensor network localization (2004)
James Aspnes, James Aspnes, David Goldenberg, David Goldenberg, Yang Richard Yang, Yang Richard Yang
Determining the positions of the sensor nodes in a network is essential to many network functionalities such as routing, coverage and tracking, and event detection. The localization problem for...
On the computational complexity of sensor network localization (2004)
James Aspnes, David Goldenberg, Yang Richard Yang
Abstract. Determining the positions of the sensor nodes in a network is essential to many network functionalities such as routing, coverage and tracking, and event detection. The localization problem...
Compositional Competitiveness for Distributed Algorithms ∗ (2004)
We define a measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. This new measure...
James Aspnes, Joan Feigenbaum, Aleksandr Yampolskiy, Sheng Zhong
aleksandr.yampolskiy@yale.edu. Supported by NSF.
Relationships between broadcast and shared memory in reliable anonymous distributed systems (2004)
Faith Ellen, James Aspnes, James Aspnes
the date of receipt and acceptance should be inserted later Abstract We study the power of reliable anonymous distributed systems, where processes do not fail, do not have identifiers, and run...
Compositional Competitiveness for Distributed Algorithms* (2004)
Abstract We define a measure of competitive performance for distributed al-gorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. This new...
1 Scenario: A flock of birds (2004)
Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, René Peralta, Dana Angluin, ...
Suppose we have equipped each bird in a particular flock with a sensor that can determine whether the bird’s temperature is elevated or not, and we wish to know whether at least 5 birds in the...
On the Computational Complexity of Sensor Network Localization (2004)
James Aspnes, James Aspnes, David Goldenberg, David Goldenberg, Yang Richard Yang, Yang Richard Yang
Determining the positions of the sensor nodes in a network is essential to many network functionalities such as routing, coverage and tracking, and event detection. The localization problem for...
Towards a Theory of Data Entanglement (2004)
James Aspnes, Joan Feigenbaum, Aleksandr Yampolskiy, Sheng Zhong
We propose a formal model for data entanglement as used in storage systems like Dagster [25] and Tangler [26]. These systems split data into blocks in such a way that a single block becomes a part of...
Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, René Peralta
Summary. The computational power of networks of small resource-limited mobile agents is explored. Two new models of computation based on pairwise interactions of finite-state agents in populations of...
Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes...
Compositional competitiveness for distributed algorithms (2003)
We define a measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. This new measure...
Fault-tolerant routing in peer-to-peer systems (2003)
Aspnes, James, Diamadi, Zoe, Shah, Gauri
We consider the problem of designing an overlay network and routing mechanism that permits finding resources efficiently in a peer-to-peer system. We argue that many existing approaches to this...
Randomized protocols for asynchronous consensus (2003)
The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single...
Dana Angluin, James Aspnes, Zoe Diamadi, Michael J. Fischer, Rene Peralta
Urn automata are a new class of automata consisting of an input tape, a finite-state controller, and an urn containing tokens with a finite set of colors, where the finite-state controller can sample...
Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes...
Dana Angluin, Dana Angluin, James Aspnes, James Aspnes, Zoë Diamadi, Zoë Diamadi, ...
Urn automata are a new class of automata consisting of an input tape, a finite-state controller, and an urn containing tokens with a finite set of colors, where the finite-state controller can sample...
Introducing a Notion of Competitive Analysis for Distributed Algorithms The (2003)
Miklos Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Bartal, Fiat, and Rabani [18], and of Awerbuch, Kutten,...
Randomized protocols for asynchronous consensus (2003)
The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single...
Randomized protocols for asynchronous consensus (2002)
The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single...
Fast Deterministic Consensus in a Noisy Environment (2002)
It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy...
Wait-free consensus with infinite arrivals (2002)
James Aspnes, Gauri Shah, Jatin Shah
A randomized algorithm is given that solves the wait-free consensus problem for a shared-memory model with innitely many processes. The algorithm is based on a weak shared coin algorithm that uses...
Fault-tolerant routing in peer-to-peer systems (2002)
James Aspnes, Zo E Diamadi, Gauri Shah
We consider the problem of designing an overlay network and routing mechanism that permits nding resources eciently in a peer-to-peer system. We argue that many existing approaches to this problem...
Opportunity cost algorithms for combinatorial auctions (2002)
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Two general algorithms based on opportunity costs are given for approximating a revenuemaximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder oers a price...
Fault-tolerant routing in peer-to-peer systems (2002)
James Aspnes, Zo "e Diamadi, Gauri Shah
z
Opportunity cost algorithms for combinatorial auctions (2002)
James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Abstract Two general algorithms based on opportunity costs are given for approximating a revenuemaximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder...
Aspnes, James, Hartling, Julia, Kao, Ming-Yang, Kim, Junhyong, Shah, Gauri
In modern biology, one of the most important research problems is to understand how protein sequences fold into their native 3D structures. To investigate this problem at a high level, one wishes to...
Opportunity Cost Algorithms for Combinatorial Auctions (2000)
Akcoglu, Karhan, Aspnes, James, DasGupta, Bhaskar, Kao, Ming-Yang
Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a...
Aspnes, James, Fischer, David F., Fischer, Michael J., Kao, Ming-Yang, Kumar, Alok
This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the...
Fast deterministic consensus in a noisy environment (2000)
It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy...
Fast deterministic consensus in a noisy environment (2000)
It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy...
Opportunity Cost Algorithms for Combinatorial Auctions (2000)
Karhan Akcoglu, James Aspnes, Bhaskar Dasgupta, Ming-yang Kao
Two general algorithms based on opportunity costs are given for approximating a revenue maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a...
Modular Competitiveness for Distributed Algorithms (2000)
We define a novel measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. This new measure...
Aspnes, James, Herlihy, Maurice, Shavit, Nir
Many fundamental multiprocessor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory or...
Consensus is a decision problem in which n processors, each starting with a value not known to the others, must collectively agree on a single value. If the initial values are equal, the processors...
Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long...
Lower Bounds for Distributed Coin-Flipping and Randomized Consensus (1998)
We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must...
Spreading Rumors Rapidly Despite an Adversary (1998)
In the collect problem [32], n processors in a shared-memory system must each learn the values of n registers. We give a randomized algorithm that solves the collect problem in O(n log 3 n) total...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
. In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required...
Lower Bounds for Distributed Coin-Flipping and Randomized Consensus (1997)
We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required...
James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, Orli Waarts
In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to minimize the required bandwidth. We concentrate on the...
Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long...
A Modular Measure of Competitive Performance for Distributed Algorithms (1995)
We define a novel measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. This new measure...
Fairness in Scheduling (Extended Abstract) (1995)
Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
) Miklos Ajtai James Aspnes y Moni Naor z Yuval Rabani x Leonard J. Schulman -- Orli Waarts k Abstract On-line machine scheduling has been studied extensively, but the fundamental issue of fairness...
A theory of competitive analysis for distributed algorithms (1994)
Miklos Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
We introduce a theory of competitive analysis for distributed algorithms. The rst steps in this direction were made in the seminal papers of Bartal, Fiat, and Rabani [18], and of Awerbuch, Kutten,...
The expressive power of voting polynomials (1994)
James Aspnes, Richard Beigel, Merrick Furst, Steven Rudich
We consider the problem of approximating a Boolean function f: f0; 1g n! f0; 1g by the sign of an integer polynomial p of degree k. For us, a polynomial p(x) predicts the value of f(x) if, whenever...
A theory of competitive analysis for distributed algorithms (1994)
Abstract. Most applications of competitive analysis have involved online problems where a candidate on-line algorithm must compete on some input sequence against an optimal off-line algorithm that...
A Theory of Competitive Analysis for Distributed Algorithms (1994)
Miklos Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Bartal, Fiat, and Rabani [17], and of Awerbuch, Kutten,...
James Aspnes, Maurice Herlihy, Nir Shavit
Many fundamental multi-processor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory or...
James Aspnes, Maurice Herlihy, Nir Shavit
Many fundamental multi-processor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory or...
A theory of competitive analysis for distributed algorithms (1994)
Miklos Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
We demonstrate our method by studying the cooperative collect primitive, first abstracted by Saks, Shavit, and Woll [57]. We present two algorithms (with different strengths) for this primitive, and...
James Aspnes, Maurice Herlihy, Nir Shavit
part of this work was performed while the author was at
Time- and space-efficient randomized consensus (1993)
A protocol is presented which solves the randomized consensus problem[9] for shared memory. The protocol uses a total of O(p 2 +n) worst-case expected increment, decrement and read operations on a...
James Aspnes, Maurice Herlihy, Nir Shavit
Many fundamental multi-processor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory or...
Abstract: "Consensus is a decision problem in which n processors, each starting with a value not known to the others, must collectively agree on a single value. If the initial values are equal, the...
Counting Networks and Multi-Processor Coordination (Extended Abstract) (1991)
James Aspnes, Maurice Herlihy, Nir Shavit
) James Aspnes Maurice Herlihy y Nir Shavit z Digital Equipment Corporation Cambridge Research Lab CRL 90/11 September 18, 1991 Abstract Many fundamental multi-processor coordination problems can be...
Counting Networks and Multi-Processor Coordination (1991)
Many fundamental multi-processor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory or...
Wait-free data structures in the asynchronous PRAM model (1990)
In the asynchronous PRAM model, processes communicate by atomically reading and writing shared memory locations. This paper investigates the extent to which asynchronous PRAM permits long-lived,...
Wait-free data structures in the asynchronous PRAM model (1990)
A wait-free implementation of a data object in shared memory is one that guarantees that any process can complete any operation in a nite number of steps, regardless of the execution speeds of the...
Fast randomized consensus using shared memory (1990)
We give a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers. The fastest previously known algorithm has...
Wait-free data structures in the asynchronous PRAM model (1990)
A wad-free implementation of a data object in shared memory is one that guarantees that any process can complete any operation in a finite number of steps, re-gardless of the execution speeds of the...
Modular Competitiveness for Distributed Algorithms
We define a novel measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an algorithm can carry out in a fixed amount of work. An important...