Biedl, Therese, Durocher, Stephane, Hoos, Holger H., Luan, Shuang, Saia, Jared, Young, Maxwell
he segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes...
The Forgiving Graph: A distributed data structure for low stretch under adversarial attack (2009)
Hayes, Tom, Saia, Jared, Trehan, Amitabh
We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts 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...
A Computational Approach to Animal Breeding (2008)
Abstract. We propose a computational model of mating strategies for controlled animal breeding programs. To the best of our knowledge, this is the first computational model of this problem. We focus...
Reducing Communication Costs in Robust Peer-to-Peer Networks (2008)
Several recent research results describe how to design Distributed Hash Tables (DHTs) that are robust to adversarial attack via Byzantine faults. Unfortunately, all of these results require a...
A Computational Approach to Animal Breeding (2008)
Tanyay Berger-wolf, Cristopher Moore, Jared Saia, Cristopher Moore, Jared Saia
doi:10.1016/j.jtbi.2006.08.028 This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the...
Fast Asynchronous Byzantine Agreement and Leader Election with Full Information (2008)
Bruce Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani
We resolve two long-standing open problems in distributed computation by showing that both Byzantine agreement and Leader Election can be solved in sub-exponential time in the asynchronous full...
Choosing a Random Peer in Chord (2008)
Valerie King, Scott Lewis, Jared Saia, Maxwell Young
We present two new algorithms, Arc Length and Peer Count, for choosing a peer uniformly at random from the set of all peers in Chord [24]. We show analytically that, in expectation, both algorithms...
Amos Fiat, Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, ...
We present a censorship resistant peer-to-peer Content Addressable Network for accessing n data items in a network of n nodes. Each search for a data item in the network takes O(log n) time and...
Responsive Algorithms for Defending Reconfigurable Networks (2008)
I-ching Boman, Jared Saia, Edl Schamiloglu, Chaouki T. Abdallah
We present algorithms to self-heal reconfigurable networks when they are under attack. These algorithms reconfigure the network during attack to protect two critical invariants. First, they insure...
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...
Approximation Algorithms for Minimizing Segments in Radiation Therapy (2008)
Shuang Luan, Jared Saia, Maxwell Young
Intensity modulated radiation therapy (IMRT) is one of the most effective modalities for modern cancer treatment. The key to successful IMRT treatment hinges on the delivery of a two-dimensional...
Abstract Scalable Leader Election (2008)
Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
In the leader election problem, there are n processors of which (1 − b)n are good. The problem is to design a distributed protocol to elect a good leader from the set of all processors. In this...
The Forgiving Tree: A Self-Healing Distributed Data Structure (2008)
Hayes, Tom, Rustagi, Navin, Saia, Jared, Trehan, Amitabh
We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that the following process continues for up to n rounds where n...
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...
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...
Picking up the Pieces: Self-Healing in Reconfigurable Networks (2008)
We consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Our goal is to maintain connectivity in these networks,...
Michael Collins, Jared Saia, Ling Yu
Aerial search and rescue (or bombing) missions frequently have to locate a target within some prescribed area, running a search pattern that is constrained by the flight characteristics of the...
Jared Saia, Steve Gribble, Anna R. Karlin, Stefan Saroiu
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an...
Abstract Dynamically Fault-Tolerant Content Addressable Networks (2007)
Jared Saia, Amos Fiat, Steve Gribble, Anna R. Karlin, Stefan Saroiu
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an...
Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, John Locke, ...
of Prohibited Books) from the Roman O#ce of the Inquisition,
Jared Saia, Steve Gribble, Anna R. Karlin, Stefan Saroiu
We describe a content addressable network which is robust in the face of massive adversarial attacks and in a highly dynamic environment. Our network is robust in the sense that at any time, an...
Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, John Milton, ...
(Index of Prohibited Books) from the
Jason Hartline, Anna R. Karlin, Jared Saia, John Wilkes
The data migration problem is the problem of computing an ecient plan for moving data stored on devices in a network from one conguration to another. Load balancing or changing usage patterns could...
Tracy Kimbrel, Jared Saia, T. J. Watson
Online and oine preemptive two-machine job shop scheduling Tracy Kimbrel Jared Saia We consider online and oine algorithms for special cases of preemptive job shop scheduling to minimize makespan....
Eric Anderson, Jason Hartline, Michael Hobbs, Anna R. Karlin, Jared Saia, Ram Swaminathan, ...
Abstract. The data migration problem is the problem of computing a plan for moving data objects stored on devices in a network from one con-guration to another. Load balancing or changing usage...
Spectral Analysis for Information Retrieval and Data Mining (2007)
The growth of the Internet in recent years has led to a proliferation of digital data that is readily available for computational analysis. This data tends to have the following qualities: 1) it...
Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks (2007)
King, Valerie, Phillips, Cynthia, Saia, Jared, Young, Maxwell
We address the problem of minimizing power consumption when performing reliable broadcast on a radio network under the following popular model. Each node in the network is located on a point in a two...
Michael J. Collins, David Kempe, Jared Saia, Maxwell Young
We consider an integer-subset representation problem motivated by a medical application in radiation therapy. We prove NP-completeness, derive nontrivial bounds, and report on the performance of a...
Towards secure and scalable computation in peer-to-peer networks (2006)
Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
We consider the problems of Byzantine Agreement and Leader Election, where a constant fraction b < 1/3 of processors are controlled by a malicious adversary. The first problem requires that all...
Censorship Resistant Peer-to-Peer Networks (2006)
Amos Fiat, Jared Saia, Thomas Hobbes, René Descartes, Francis Bacon, Benedict Spinoza, ...
Abstract: We present a censorship resistant peer-to-peer network for accessing n data items in a network of n nodes. Each search for a data item in the network takes O(logn) time and requires at most...
The Impact of Social Networks on Multi-Agent Recommender Systems (2005)
Link, Hamilton, Saia, Jared, Lane, Terran, LaViolette, Randall A.
Awerbuch et al.'s approach to distributed recommender systems (DRSs) is to have agents sample products at random while randomly querying one another for the best item they have found; we improve upon...
Parameters Affecting the Resilience of Scale-Free Networks to Random Failures (2005)
Link, Hamilton, LaViolette, Randall A., Saia, Jared, Lane, Terran
It is commonly believed that scale-free networks are robust to massive numbers of random node deletions. For example, Cohen et al. study scale-free networks including some which approximate the...
Making chord robust to byzantine attacks (2005)
Amos Fiat, Jared Saia, Maxwell Young
Abstract. Chord is a distributed hash table (DHT) that requires only O(logn) links per node and performs searches with latency and message cost O(logn), where n is the number of peers in the network....
The Impact of Social Networks on Multi-Agent Recommender Systems (2005)
Hamilton Link, Jared Saia, Terran Lane, All A. Laviolette
Abstract. Awerbuch et al.’s approach to distributed recommender systems (DRSs) is to have agents sample products at random while randomly querying one another for the best item they have found; we...
Making chord robust to byzantine attacks (2005)
Amos Fiat, Jared Saia, Maxwell Young
That which is not good for the swarm is not good for the bee either.
Distributed Recommender Systems and the Network Topologies that Love Them (2005)
Hamilton Link, Jared Saia, Randall Laviolette, Terran Lane
One approach to distributed recommender systems is to have users sample products at random and randomly query one another for the best item they have found. We have been considering refinements to...
Web content is under attack by state and corporate efforts to censor it, for political and... (2004)
Amos Fiat, Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, ...
Abstract: We present a censorship resistant peer-to-peer network for accessing n data items in a network of n nodes. Each search for a data item in the network takes O(logn) time and requires at most...
Censorship resistant peer-to-peer content addressable networks (2002)
Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, John Milton, ...
We present a censorship resistant peer-to-peer Content Addressable Network for accessing n data items in a network of n nodes. Each search for a data item in the network takes O(log n) time and...
Algorithms for managing data in distributed systems / (2002)
Thesis (Ph. D.)--University of Washington, 2002.
Spectral analysis of data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Every action must be due to one or other of seven causes: chance, nature, compulsion, habit, reasoning, anger, or appetite.
Spectral Analysis of Data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster...
Michael Collins, Jared Saia, Ling Yu
Aerial search and rescue (or bombing) missions frequently have to locate a target within some prescribed area, running a search pattern that is constrained by the flight characteristics of the...
Network Routing Models Applied To Aircraft Routing Problems (1995)
Zhiqiang Chen, Andrew T. Holle, Jared Saia, Ali Boroujerdi
We study network models applied to two aircraft routing problems, one in which the goal is to route strike aircraft to a target and back so as to minimize losses and one in which the goal is to route...