Communiation-efficient randomized consensus

Dan Alistarh, James Aspnes, Valerie King, and Jared Saia. Communiation-efficient randomized consensus. Accepted to DISC 2014.

Abstract

We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary.

We describe a new randomized consensus protocol with expected message complexity O(n² log² n) when fewer than n/2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n²) message lower bound. The protocol further ensures that no process sends more than O(n log³ n) messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt + t² log² t) total messages.

Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing a message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.

BibTeX

Download
@unpublished{AlistarhAKS2014,
author = {Dan Alistarh and James Aspnes and Valerie King and Jared Saia},
title = {Communication-Efficient Randomized Consensus},
month=may,
year = 2014,
note={Accepted to DISC 2014},
}

Dynamic task allocation in asynchronous shared memory

Dan Alistarh, James Aspnes, Michael Bender, Rati Gelashvili, and Seth Gilbert. Dynamic task allocation in asynchronous shared memory. 2014 ACM-SIAM Symposium on Discrete Algorithms, January 2014, pp. 416–435.

Abstract

Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of m tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. A major challenge in this setting is the fact that, at the same time, the adaptive adversary controls the scheduling and process crashes, as well as choosing the input. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random available locations in the data structure. Our analysis shows that that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected complexity of our algorithm on the same input is O(OPT log³m).

BibTeX

Download
@inproceedings{AlistarhABGG2014,
author = {Dan Alistarh and James Aspnes and Michael Bender and Rati Gelashvili and Seth Gilbert},
title = {Dynamic task allocation in asynchronous shared memory},
month=jan,
year = 2014,
booktitle={2014 ACM-SIAM Symposium on Discrete Algorithms},
pages={416--435}
}

Atomic snapshots in expected O(log³ n) steps using randomized helping

James Aspnes and Keren Censor-Hillel. Atomic snapshots in expected O(log³ n) steps using randomized helping. Submitted to Distributed Computing, January 2014. An earlier version appeared in Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14--18, 2013. Proceedings., Lecture Notes in Computer Science 8205, Springer-Verlag, October 2013, pp. 254–268.

Abstract

A randomized construction of unbounded snapshots objects from atomic registers is given. The cost of each snapshot operation is O(log³n) atomic register steps with high probability, where n is the number of processes, even against an adaptive adversary. This is an exponential improvement on the linear cost of the previous best known unrestricted snapshot construction and on the linear lower bound for deterministic constructions, and does not require limiting the number of updates as in previous sublinear constructions. One of the main ingredients in the construction is a novel randomized helping technique that allows out-of-date processes to obtain up-to-date information without running into covering lower bounds.

Our construction can be adapted to implement snapshots in a message-passing system. While a direct adaptation using the Attiya-Bar-Noy-Dolev construction gives a cost of O(log³ n) time and O(n log³n)$ messages per operation with high probability, we show that exploiting the inherent parallelism of a message-passing system can eliminate the need for randomized helping and reduce the complexity to O(log²n)$ time and O(n log² n) messages per operation in the worst case. This implementation includes an O(1)-time, O(n)-message construction of an unbounded max register that may be of independent interest.

BibTeX

Download
@incollection{AspnesC2013,
year={2013},
isbn={978-3-642-41526-5},
booktitle={Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14--18, 2013. Proceedings},
volume={8205},
series={Lecture Notes in Computer Science},
editor={Afek, Yehuda},
doi={10.1007/978-3-642-41527-2_18},
title={Atomic Snapshots in $O(log^3 n)$ Steps Using Randomized Helping},
url={http://dx.doi.org/10.1007/978-3-642-41527-2_18},
publisher={Springer Berlin Heidelberg},
author={Aspnes, James and Censor-Hillel, Keren},
pages={254--268}
}

Randomized loose renaming in O(log log n) time

Dan Alistarh, James Aspnes, George Giakkoupis, and Philipp Woelfel. Randomized loose renaming in O(log log n) time. 2013 ACM Symposium on Principles of Distributed Computing, July 2013, pp. 200–209.

Abstract

Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with O(log log n) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((log log k)²), where k is the actual contention in the execution. Both bounds hold with high probability against a strong adaptive adversary. The running time improvement over previously known solutions is exponential.

We complement the algorithms with an Ω(log log n) expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use O(n) test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting.

BibTeX

Download
@inproceedings{AlistarhAGW2013,
author = {Dan Alistarh and James Aspnes and George Giakkoupis and Philipp Woelfel},
title = {Randomized loose renmaing in $O(\log \log n)$ time},
month=jul,
year = 2013,
booktitle={2013 ACM Symposium on Principles of Distributed Computing},
pages={200--209}
}

On the learnability of shuffle ideals

Dana Angluin, James Aspnes, Sarah Eisenstat, and Aryeh Kontorovich. On the learnability of shuffle ideals. Journal of Machine Learning Research, 14(Jun):1513–1531, June 2013. An earlier version appeared in Twenty-Third International Converence on Algorithmic Learning Theory, October 2012, pp. 111–123.

Abstract

PAC learning unrestricted regular languages is long known to be a very difficult problem. The class of shuffle ideals is a very restricted subclass of regular languages, where the shuffle ideal generated by a string u is the collection of all strings containing u as a subsequence. This fundamental language family is of theoretical interest in its own right and provides the building blocks for other important language families. Despite its apparent simplicity, the class of shuffle ideals appears quite difficult to learn. In particular, just as for unrestricted regular languages, the class is not properly PAC learnable in polynomial time if RP ≠ NP, and PAC learning the class improperly in polynomial time would imply polynomial time algorithms for certain fundamental problems in cryptography. In the positive direction, we give an efficient algorithm for properly learning shuffle ideas in the statistical query (and therefor also PAC) model under the uniform distribution.

BibTeX

Download
@article{AngluinAEK2013,
  author  = {Dana Angluin and James Aspnes and Sarah Eisenstat and Aryeh Kontorovich},
  title   = {On the Learnability of Shuffle Ideals},
  journal = {Journal of Machine Learning Research},
  month = jun,
  year    = {2013},
  volume  = {14},
  number = {Jun},
  pages   = {1513--1531},
  url     = {http://jmlr.org/papers/v14/angluin13a.html}
}

A one-bit swap object using test-and-sets and a max register

James Aspnes. A one-bit swap object using test-and-sets and a max register. Available as YALEU/DCS/TR-1464, October 2012.

Abstract

We describe a linearizable, wait-free implementation of a one-bit swap object from a single max register and an unbounded array of test-and-set bits. Each swap operation takes at most three steps. Using standard randomized constructions, the max register and test-and-set bits can be replaced by read-write registers, at the price of raising the cost of a swap operation to an expected O(max(log n, min(log t, n))) steps, where t is the number of times the swap object has previously changed its value and n is the number of processes.

BibTeX

Download
@techreport{Aspnes2012swap,
author = {James Aspnes},
title = {A one-bit swap using test-and-sets and a max register},
institution="Yale University Department of Computer Science",
number="YALEU/DCS/TR-1464",
month=oct,
year = 2012
}

Tight bounds for asynchronous renaming

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. Tight bounds for asynchronous renaming. Journal of the Association for Computing Machinery, 61(3):18, May 2014.

Abstract

This paper presents the first tight bounds on the complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace.

We first prove an individual 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. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of Ω(k log(k/c)) on the total step complexity of renaming into a namespace of size ck, for any c ≥ 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors.

On the algorithmic side, we give a protocol that transforms any sorting network into a strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O(log k), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.

BibTeX

Download
@article{AlistarhACHGG2014,
author = {Dan Alistarh and James Aspnes and Keren Censor-Hillel and Seth Gilbert and Rachid Guerraoui},
title = {Tight bounds for asynchronous renaming},
month=may,
year = 2014,
journal = jacm,
volume=61,
number=3,
pages=18 
}

Faster randomized consensus with an oblivious adversary

James Aspnes. Faster randomized consensus with an oblivious adversary. To appear, Distributed Computing (PODC 2012 special issue), October 2012. An earlier version appeard in 2012 ACM Symposium on Principles of Distributed Computing, July 2012, pp. 1–8.

Abstract

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with constant probability. The first conciliator assumes unit-cost snapshots and achieves agreement among n processes with probability 1-ε in O(log* n + log(1/ε)) steps for each process. The second uses ordinary multi-writer registers, and achieves agreement with probability 1-ε in O(log log n + log(1/ε)) steps. Combining these constructions with known results gives randomized consensus for arbitrarily many possible input values using unit-cost snapshots in O(log* n) expected steps and randomized consensus for up to (log n)O(log log log n) possible input values using ordinary registers in O(log log n) expected steps.

BibTeX

Download
@inproceedings{Aspnes2012,
author = {James Aspnes},
title = {Faster randomized consensus with an oblivious adversary},
month = jul,
year = 2012,
booktitle = {2012 ACM Symposium on Principles of Distributed Computing},
pages={1--8}
}

Limited-use atomic snapshots with polylogarithmic step complexity

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Limited-use atomic snapshots with polylogarithmic step complexity. Accepted to JACM. An earlier version appeared in 2012 ACM Symposium on Principles of Distributed Computing, July 2012, pp. 375–384, under the title “Faster than optimal snapshots (for a while)” .

Abstract

This paper presents a novel implementation of a snapshot object for n processes, with O(log² b log n) step complexity for update operations and O(log b) step complexity for scan operations, where b is the number of updates. The algorithm uses only reads and writes.

For polynomially many updates, this is an exponential improvement on previous snapshot algorithms, which have linear step complexity. It overcomes the existing Ω(n) lower bound on step complexity by having the step complexity depend on the number of updates. The key to this implementation is the construction of a new object consisting of a pair of max registers that supports a scan operation.

BibTeX

Download
@inproceedings{AspnesACHE2012,
author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel and Faith Ellen},
title = {Faster than optimal snapshots (for a while)},
month = jul,
year = 2012,
booktitle = {2012 ACM Symposium on Principles of Distributed Computing},
pages={375--384}
}

Lower bounds for restricted-use objects

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Danny Hendler. Lower bounds for restricted-use objects. Twenty-Fourth ACM Symposium on Parallel Algorithms and Architectures, July 2012, pp. 172–181. Submitted to SIAM Journal on Computing, January 2013. Last revised September 2013.

Abstract

Concurrent objects play a key role in the design of applications for multi-core architectures, making it imperative to precisely understand their complexity requirements. For some objects, it is known that implementations can be significantly more efficient when their usage is restricted. However, apart from the specific restriction of one-shot implementations, where each process may apply only a single operation to the object, very little is known about the complexities of objects under general restrictions.

This paper draws a more complete picture by defining a large class of objects for which an operation applied to the object can be ``perturbed'' L consecutive times, and by proving lower bounds on their space complexity and on the time complexity of deterministic implementations of such objects. This class includes bounded-value max registers, limited-use approximate and exact counters, and limited-use collect and compare-and-swap objects; $L$ depends on the number of times the object can be accessed or the maximum value it can support.

For n-process implementations that use only historyless primitives, we prove Ω(min(L,n)) space complexity lower bounds, which hold for both deterministic and randomized implementations. For deterministic implementations, we prove lower bounds of Ω(min(log L, n)) on the worst-case step complexity of an operation. When arbitrary primitives can be used, we prove that either some operation incurs Ω(min(log L, n)) memory stalls or some operation performs Ω(min(log L, n)) steps.

In addition to our deterministic time lower bounds, the paper establishes lower bounds on the expected step complexity of restricted-use randomized versions of many of these objects in a weak oblivious adversary model.

BibTeX

Download
@inproceedings{AspnesACH2012,
author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel and Danny Hendler},
title = {Lower bounds for restricted-use objects},
month = jun,
year = 2012,
booktitle={Twenty-Fourth ACM Symposium on Parallel Algorithms and Architectures},
pages={172--181}
}

Network construction with subgraph connectivity constraints

Dana Angluin, James Aspnes, and Lev Reyzin. Network construction with subgraph connectivity constraints. To appear, Journal of Combinatorial Optimization.

Abstract

We consider the problem introduced by Korach and Stern (2008) 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 set of edges E such that each Si induces a connected subgraph of (V,E). First, we answer a question posed by Korach and Stern: for the offline version of the problem, we prove an Ω(log(n)) hardness of approximation result for uniform cost networks (where edge costs are all 1) and give an algorithm that almost matches this bound, even in the arbitrary cost case. Then we consider the online problem, where the constraints must be satisfied as they arrive. We give an O(n log(n))-competitive algorithm for the arbitrary cost online problem, which has an Ω(n)-competitive lower bound. We look at the uniform cost case as well and give an O(n2/3log2/3(n))-competitive algorithm against an oblivious adversary, as well as an Ω(√n)-competitive lower bound against an adaptive adversary. We also examine cases when the underlying network graph is known to be a star or a path, and prove matching upper and lower bounds of Θ(log(n)) on the competitive ratio for them.

BibTeX

Download
@unpublished{AngluinAR2010connectivity,
author = {Dana Angluin and James Aspnes and Lev Reyzin},
title = {Network construction with subgraph connectivity constraints},
month=jan,
year = 2013,
note="To appear, Journal of Combinatorial Optimization"
}

Randomized load balancing by joining and splitting bins

James Aspnes and Yitong Yin. Randomized load balancing by joining and splitting bins. Information Processing Letters, 112(8–9):309–313, April 2012.

Abstract

Consider the following load balancing scenario: a certain amount of work load is distributed among a set of machines that may change over time as machines join and leave the system. Upon an arrival of a new machine, one of the existing machines gives some of its load to the new machine; and upon a departure of a machine, it gives all its load away to one of the existing machines in the system. Such load balancing schemes can be modeled as a simple game of joining and splitting weighted bins. Each bin corresponds to a machine in the system, and the weight of the bin represents the amount of load assigned to the machine. The arrival of a new machine corresponds to a split of a bin, and the departure of an existing machine is represented by joining two bins.

We consider what happens when the joins and splits are randomized. When the bins are split with probability proportional to their weights, it is not hard to see that this gives the same behavior as uniformly cutting a ring as in (Karger et al., 1997), which yields an O(log n) load factor for n bins. Where it is infeasible to bias the random choice with the weights, it is natural to implement uniform splits, where the split bin is sampled uniformly. Despite its simple definition, analyzing the performance of this natural load-distribution mechanism is a nontrivial task.

In this paper, we apply a novel technique based on vector norms to analyze the load balancing performance of uniform random joins and splits. We show that if only splits (with no joins) are applied, the expected load factor, the ratio between the maximum weight and the average weight of the bins, is between Ω(n0.5) and O(n0.742). We then study the performance of mixed joins and splits, and show that the expected load factor approaches O(n1/√((1/2) lg n)) after alternatively applying sufficiently many joins and splits to an arbitrary initial load assignment of n bins. These results demonstrate that the good load factor obtained by (Karger et al., 1997) depends strongly on the ability to preferentially split heavily-loaded bins.

BibTeX

Download
@article{AspnesY2012,
author = {James Aspnes and Yitong Yin},
title = {Randomized load balancing by joining and splitting bins},
month=apr,
year = 2012,
journal="Information Processing Letters",
volume=112,
number={8--9},
pages={309--313}
}

The complexity of renaming

Dan Alistarh, James Aspnes, Seth Gilbert, and Rachid Guerraoui. The complexity of renaming. Fifty-Second Annual IEEE Symposium on Foundations of Computer Science, October 2011, pp. 718–727.

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 an individual 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 individual bound with a global lower bound of Ω(k log(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.

BibTeX

Download
@inproceedings{AlistarhAGG2011,
author = {Dan Alistarh and James Aspnes and Seth Gilbert and Rachid Guerraoui},
title = {The complexity of renaming},
month = oct,
year = 2011,
booktitle={Fifty-Second Annual IEEE Symposium on Foundations of Computer Science},
pages={718--727}
}

Randomized consensus in expected O(n²) total work using single-writer registers

James Aspnes. Randomized consensus in expected O(n²) total work using single-writer registers. Distributed Computing: 25th International Symposium, DISC 2011. Lecture Notes in Computer Science 6950, Springer-Verlag, September 2011, pp. 363–373.

Abstract

A new weak shared coin protocol yields a randomized wait-free shared-memory consensus protocol that uses an optimal O(n²) expected total work with single-writer registers despite asynchrony and process crashes. Previously, no protocol was known that achieved this bound without using multi-writer registers.

BibTeX

Download
@inproceedings{Aspnes2011,
author = {James Aspnes},
title = {Randomized consensus in expected {$O(n^2)$} total work using single-writer registers},
month =sep, 
year = 2011,
booktitle="Distributed Computing: 25th International Symposium, DISC 2011",
series="Lecture Notes in Computer Science",
volume=6950,
publisher="Springer-Verlag",
pages={363--373},
}

Sub-logarithmic test-and-set against a weak adversary

Dan Alistarh and James Aspnes. Sub-logarithmic test-and-set against a weak adversary. Distributed Computing: 25th International Symposium, DISC 2011. Lecture Notes in Computer Science 6950, Springer-Verlag, September 2011, pp. 97–109.

Abstract

A randomized implementation is given of a test-and-set register with O(log log n) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complexity improvement over previous solutions designed to work against a strong adversary.

BibTeX

Download
@inproceedings{AlistarhA2011,
author = {Dan Alistarh and James Aspnes},
title = {Sub-logarithmic test-and-set against a weak adversary},
month = sep,
year = 2011,
booktitle="Distributed Computing: 25th International Symposium, DISC 2011",
series="Lecture Notes in Computer Science",
volume=6950,
publisher="Springer-Verlag",
pages={97--109},
}

Optimal-time adaptive tight renaming, with applications to counting

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Morteza Zadimoghaddam. Optimal-time adaptive tight renaming, with applications to counting. Thirtieth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, June 2011, pp. 239–248.

Abstract

We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. 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(log³ n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong 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 strong 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).

BibTeX

Download
@inproceedings{AlistarhACHGZ2011,
author = {Dan Alistarh and James Aspnes and Keren Censor-Hillel and Seth Gilbert and Morteza Zadimoghaddam},
title = {Optimal-time adaptive tight renaming, with applications to counting},
month = jun,
year = 2011,
booktitle = {Proceedings of the Thirtieth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing},
pages={239--248},
}

Tight bounds for adopt-commit objects

James Aspnes and Faith Ellen. Tight bounds for adopt-commit objects. To appear, Theory of Computing Systems (SPAA 2011 special issue). An earlier version appeared in 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, June 2011, pp. 317–324, under the title “Tight bounds for anonymous adopt-commit objects.”

Abstract

We give matching upper and lower bounds of Θ(min(log m / log log m, n)) for the individual step complexity of a wait-free m-valued adopt-commit object implemented using multi-writer registers for n anonymous processes. While the upper bound is deterministic, the lower bound holds for randomized adopt-commit objects as well. Our results are based on showing that adopt-commit objects are equivalent, up to small additive constants, to a simpler class of objects that we call conflict detectors.

Our anonymous lower bound also applies to the individual step complexity of m-valued wait-free anonymous consensus, even for randomized algorithms with global coins against an oblivious adversary. The upper bound can be used to slightly improve the cost of randomized consensus in an oblivious-adversary model.

For deterministic non-anonymous implementations of adopt-commit objects, we show a lower bound of Ω(min(log m / log log m, sqrt(log n) / log log n) and an upper bound of O(min(log m / log log m, log n) on the worst-case individual step complexity. For randomized non-anonymous implementations, we show that any execution contains at least one process whose steps exceed the deterministic lower bound.

BibTeX

Download
@inproceedings{AspnesE2011,
author = {James Aspnes and Faith Ellen},
title = {Tight bounds for anonymous adopt-commit objects},
month = jun,
year = 2011,
pages={317--324},
booktitle={23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures}
}

Mutation systems

Dana Angluin, James Aspnes, and Raonne Barbosa Vargas. Mutation systems. International Journal of Computer Mathematics 90(6):1132–1149, June 2013. (LATA 2011 special issue). An earlie version appeared in Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26–31, 2011, Lecture Notes in Computer Science 6638, Springer-Verlag, May 2011, pp. 92–104.

Abstract

We propose Mutation Systems as a model of the evolution of a string subject to the effects of mutations and a fitness function. One fundamental question about such a system is whether knowing the rules for mutations and fitness, we can predict whether it is possible for one string to evolve into another. To explore this issue we define a specific kind of mutation system with point mutations and a fitness function based on conserved strongly k-testable string patterns. We show that for k ≥ 2, such systems can simulate computation by both finite state machines and cellular automata. The cellular automaton simulation shows that in this framework, universal computation is possible and the question of whether one string can evolve into another is undecidable. We also analyze the efficiency of the finite state machine simulation assuming random point mutations.

BibTeX

Download
@article{AngluinABV2013,
author = {Dana Angluin and James Aspnes and Barbosa Vargas, Raonne},
title = {Mutation systems},
month = jun,
year = 2013,
journal = {International Journal of Computer Mathematics},
volume = 90,
number = 6,
pages = {1132--1149}
}

Slightly smaller splitter networks

James Aspnes. Slightly smaller splitter networks. Available as YALEU/DCS/TR-1438, November 2010, and as arXiv:1011.3170.

Abstract

The classic renaming protocol of Moir and Anderson (1995) uses a network of Θ(n²) splitters to assign unique names to n processes with unbounded initial names. We show how to reduce this bound to Θ(n3/2) splitters.

BibTeX

Download
@techreport{Aspnes2010splitters,
author = {James Aspnes},
title = {Slightly smaller splitter networks},
institution="Yale University Department of Computer Science",
number="YALEU/DCS/TR-1438",
month=nov,
year = 2010
}

Inferring social networks from outbreaks

Dana Angluin, James Aspnes, and Lev Reyzin. Inferring social networks from outbreaks. Algorithmic Learning Theory, 21st International Conference, Lecture Notes in Computer Science 6331, Springer-Verlag, October 2010, pp. 104–118.

Abstract

We consider the problem of inferring the most likely social network given connectivity constraints imposed by observations of outbreaks within the network. Given a set of vertices (or agents) V and constraints (or observations) Si ⊆ V, we seek to find a minimum log-likelihood cost (or maximum likelihood) set of edges (or connections) E such that each Si induces a connected subgraph of (V,E). For the offline version of the problem, we prove an Ω(log n) hardness of approximation result for uniform cost networks and give an algorithm that almost matches this bound, even for arbitrary costs. Then we consider the online problem, where the constraints are satisfied as they arrive. We give an O(n log n)-competitive algorithm for the arbitrary cost online problem, which has an Ω(n)-competitive lower bound. We look at the uniform cost case as well and give an O(n2/3 log2/3n)-competitive algorithm against an oblivious adversary, as well as an Ω(√n)-competitive lower bound against an adaptive adversary. We examine cases when the underlying network graph is known to be a star or a path, and prove matching upper and lower bounds of Θ(log n) on the competitive ratio for them.

BibTeX

Download
@inproceedings{AngluinAR2010outbreaks,
author = {Dana Angluin and James Aspnes and Lev Reyzin},
title = {Inferring social networks from outbreaks},
month=oct,
year = 2010,
pages = {104--118},
booktitle = {Algorithmic Learning Theory, 21st International Conference, ALT 2010, Canberra, Australia, October 6-8, 2010. Proceedings},
publisher = {Springer},
series    = {Lecture Notes in Computer Science},
volume    = {6331}
}

Effective storage capacity of labeled graphs

Dana Angluin, James Aspnes, Rida A. Bazzi, Jiang Chen, David Eisenstat, and Goran Konjevod. Effective storage capacity of labeled graphs. Information and Computation 234:44–56, February 2014. (SSS 2010 special issue). An earlier version appeared in Stabilization, Safety, and Security of Distributed Systems: 12th International Symposium, SSS 2010, New York, NY, USA, September 20--22, 2010. Proceedings, Lecture Notes in Computer Science, volume 6366, Springer-Verlag, September 2010, pp. 573–587, under the title “Storage capacity of labeled graphs.” (Winner, Best Student Paper award.)

Abstract

We consider the question of how much information can be stored by labeling the vertices of a connected undirected graph G using a constant-size set of labels, when isomorphic labelings are not distinguishable. An exact information-theoretic bound is easily obtained by counting the number of isomorphism classes of labelings of G, which we call the information-theoretic capacity of the graph. More interesting is the effective capacity of members of some class of graphs, the number of states distinguishable by a Turing machine that uses the labeled graph itself in place of the usual linear tape. We show that the effective capacity equals the information-theoretic capacity up to constant factors for trees, random graphs with polynomial edge probabilities, and bounded-degree graphs.

BibTeX

Download
@article{AngluinABCEK2014,
author = {Dana Angluin and James Aspnes and Rida A. Bazzi and Jiang Chen and David Eisenstat and Goran Konjevod},
title = {Effective storage capacity of labeled graphs},
month=feb,
journal={Information and Computation},
year = 2014,
volume=234,
pages={44--56}
}

A modular approach to shared-memory consensus, with applications to the probabilistic-write model

James Aspnes. A modular approach to shared-memory consensus, with applications to the probabilistic-write model. Distributed Computing 25(2):179–188, May 2012. (PODC 2010 special issue.) An earlier version appeared in Twenty-Ninth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, July 2010, pp. 460–467.

Abstract

We show that consensus can be solved by an alternating sequence of adopt-commit objects (Gafni, 1998; Alistarh et al. 2009), which detect agreement, and conciliators, which ensure agreement with some probability. We observe that most known randomized consensus algorithms have this structure.

We give a deterministic implementation of an m-valued adopt-commit object for an unbounded number of processes that uses lg m + Θ(log log m) space and individual work. We also give a randomized conciliator for any number of values in the probabilistic-write model with n processes that guarantees agreement with constant probability while using one multi-writer register, O(log n) expected individual work, and Θ(n) expected total work. Combining these objects gives a consensus protocol for the probabilistic-write model that uses O(log n) individual work and O(n log m) total work. No previous protocol in this model uses sublinear individual work or linear total work for constant m.

BibTeX

Download
@article{Aspnes2012modular,
author = {James Aspnes},
title = {A modular approach to shared-memory consensus, with applications to the probabilistic-write model},
month=may,
year = 2012,
journal="Distributed Computing",
volume=25,
number=2,
pages={179--188}
}

k+ decision trees

James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, and Steve Uurtamo. k+ decision trees. Sixth International Workshop on Algorithms for Sensor Systems, Revised Selected Papers, Lecture Notes in Computer Science 6451, Springer-Verlag, July 2010, pp. 74–88.

Abstract

Consider a wireless sensor network in which each sensor has a bit of information. Suppose all sensors with the bit 1 broadcast this fact to a basestation. If zero or one sensors broadcast, the basestation can detect this fact. If two or more sensors broadcast, the basestation can only detect that there is a "collision." Although collisions may seem to be a nuisance, they can in some cases help the basestation compute an aggregate function of the sensors' data.

Motivated by this scenario, we study a new model of computation for boolean functions: the 2+ decision tree. This model is an augmentation of the standard decision tree model: now each internal node queries an arbitrary set of literals and branches on whether 0, 1, or at least 2 of the literals are true. This model was suggested in a work of Ben-Asher and Newman but does not seem to have been studied previously.

Our main result shows that 2+ decision trees can "count" rather effectively. Specifically, we show that zero-error 2+ decision trees can compute the threshold-of-t symmetric function with O(t) expected queries (and that Ω(t) is a lower bound even for two-sided error 2+ decision trees). Interestingly, this feature is not shared by 1+ decision trees. Our result implies that the natural generalization to k+ decision trees does not give much more power than 2+ decision trees. We also prove a lower bound of Ω~(t⋅log(n/t)) for the deterministic 2+ complexity of the threshold-of-t function, demonstrating that the randomized 2+ complexity can in some cases be unboundedly better than deterministic 2+ complexity.

Finally, we generalize the above results to arbitrary symmetric functions, and we discuss the relationship between k+ decision trees and other complexity notions such as decision tree rank and communication complexity.

BibTeX

Download
@inproceedings{AspnesBDORU2010,
author = {James Aspnes and Eric Blais and Murat Demirbas and Ryan O'Donnell and Atri Rudra and Steve Uurtamo},
title = {$k^+$ decision trees},
month=jul,
year = 2010,
booktitle={Algorithms for Sensor Systems: 6th International Workshop
               on Algorithms for Sensor Systems, Wireless Ad Hoc Networks,
               and Autonomous Mobile Entities, ALGOSENSORS 2010, Bordeaux,
               France, July 5, 2010, Revised Selected Papers},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
volume = 6451,
pages = {74--88}
}

Low contention data structures

James Aspnes, David Eisenstat, and Yitong Yin. Low contention data structures. Journal of Parallel and Distributed Computing, 72(5):705–715, May 2012. An earlier version appeared in Twenty-Second ACM Symposium on Parallelism in Algorithms and Architectures, June 2010, pp. 345–354.

Abstract

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has n items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n) space where queries require $O(1)$ probes and the contention is O(1/n). Asymptotically, all of these quantities are optimal. For arbitrary query distributions, we construct a data structure in O(n) space where each query requires O(log n / log log n) probes and the contention is O(log n / (n log log n)). The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(log log n).

BibTeX

Download
@article{AspnesEY2012,
author = {James Aspnes and David Eisenstat and Yitong Yin},
title = {Low-contention data structures},
month=may,
year = 2012,
journal={Journal of Parallel and Distributed Computing},
volume=72,
number=5,
pages = {705--715}
}

Combining shared coin algorithms

James Aspnes, Hagit Attiya, and Keren Censor. Combining shared coin algorithms. Journal of Parallel and Distributed Computing 70(3):317–322, March 2010.

Abstract

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 and of Aspnes and Waarts, this yields a shared coin algorithm, and hence, a randomized consensus algorithm, with O(n log² n) individual work and O(n² log n) total work, using single-writer registers. This improves upon each of the above shared coins (where the former has a high cost for individual work, while the latter reduces it but pays in the total work), and is currently the best for this model.

Another application is to prove a construction of Saks, Shavit, and Woll, which combines a shared coin algorithm that takes O(1) time in failure-free executions, with one that takes (log n) time in executions where at most √n process fail, and another one O((n³)/(n-f)) time in any other execution.

BibTeX

Download
@article{AspnesAC2010,
author = {James Aspnes and Hagit Attiya and Keren Censor},
title = {Combining shared coin algorithms},
month=mar,
year = 2010,
journal = {Journal of Parallel and Distributed Computing},
volume = 70,
number = 3,
pages = {317--322}
}

Polylogarithmic concurrent data structures from monotone circuits

James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic concurrent data structures from monotone circuits. Journal of the Association for Computing Machinery, 59(1):2:1–2:24, February 2012. An earlier version appeared in Twenty-Eighth Annual ACM Symposium on Principles of Distributed Computing, August 2009, pp. 36–45, under the title “Max registers, counters, and monotone circuits.”

Abstract

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 written. For fixed m, an m-valued max register can be constructed from one-bit multi-writer multi-reader registers at a cost of at most ⌈lg m⌉ atomic register operations per write or read.

It is also shown how a max register can be used to transform any monotone circuit into a wait-free concurrent data structure that provides write operations setting the inputs to the circuit and a read operation that returns the value of the circuit on the largest input values previously supplied. The cost of a write is bounded by O(S d min(⌈lg m⌉, n), where m is the size of the alphabet for the circuit, S is the number of gates whose value changes as the result of the write, and d is the number of inputs to each gate; the cost of a read is min(⌈lg m⌉, O(n)). While the resulting data structure is not linearizable in general, it satisfies a weaker but natural consistency condition. As an application, we obtain a simple, linearizable, wait-free counter implementation with a cost of O(min(log n log v, n)) to perform an increment and O(min(log v, n)) to perform a read, where v is the current value of the counter. For polynomially-many increments, this becomes O(log² n), an exponential improvement on the best previously known upper bounds of O(n) for an exact counting and O(n4/5+ε) for approximate counting.

Finally, it is shown that the upper bounds are almost optimal. We prove that min(⌈lg m⌉, n-1) is a lower bound on the worst-case complexity for any solo-terminating deterministic implementation of an m-valued bounded max register, which is exactly equal to the upper bound for m ≤ 2n-1. The same bound also holds m-valued counters. Furthermore, even in a solo-terminating randomized implementation of an n-valued max register with an oblivious adversary and global coins, there exist simple schedules containing n-1 partial write operations and one read operation in which, with high probability, the worst-case step complexity of a read operation is Ω(log n / log log n) if the write operations have polylogarithmic step complexity.

BibTeX

Download
@article{AspnesAC2012,
author = {James Aspnes and Hagit Attiya and Keren Censor-Hillel},
title = {Polylogarithmic concurrent data structures from monotone circuits},
journal=jacm,
month=feb,
year = 2012,
volume=59,
number=1,
pages={2:1--2:24}
}

Approximate shared-memory counting despite a strong adversary

James Aspnes and Keren Censor. Approximate shared-memory counting despite a strong adversary. ACM Transactions on Algorithms 6(2):1–23, March 2010 (SODA 2009 special issue). An earlier version appeared in Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2009, pp. 441–450.

Abstract

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented once by each of n processes in a model that allows up to n-1 crash failures. For any fixed ε, the counter achieves a relative error of δ with high probability, at the cost of O(((1/δ) log n)O(1/ε)) register operations per increment and O(n4/5+ε((1/δ) log n)O(1/ε)) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first counter implementation that is sublinear the number of processes and works despite a strong adversary scheduler that can observe internal states of processes.

An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O(n log n) to an optimal O(n), resolving one of the last remaining open problems concerning consensus in this model.

BibTeX

Download
@article{AspnesC2010,
 author = {Aspnes, James and Censor, Keren},
 title = {Approximate shared-memory counting despite a strong adversary},
 journal = {ACM Transactions on Algorithms},
 volume = {6},
 number = {2},
 year = {2010},
 issn = {1549-6325},
 pages = {1--23},
 doi = {http://doi.acm.org/10.1145/1721837.1721841},
 publisher = {ACM},
 address = {New York, NY, USA},
 }

Optimally learning social networks with activations and suppressions

Dana Angluin, James Aspnes, and Lev Reyzin. Optimally learning social networks with activations and suppressions. Nineteenth International Conference on Algorithmic Learning Theory, Lecture Notes in Computer Science 5254, Springer-Verlag, October 2008, pp. 272–286. Theoretical Computer Science 411(29–30):2729–2740. (ALT 2008 special issue).

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 the target network. We develop an algorithm that optimally learns an arbitrary social network of size n using O(n²) queries, matching the information theoretic lower bound we prove for this problem. We also consider the case when the target social network forms a tree, and we show that the learning problem takes Θ(n log n) queries. We also give an approximation algorithm for finding an influential set of nodes in the network, without resorting to learning its structure. Finally, we discuss some limitations of our approach, and limitations of path-based methods, when non-exact value injection queries are used.

BibTeX

Download
@article{AngluinAR2010networks,
author = {Dana Angluin and James Aspnes and Lev Reyzin},
title = {Optimally learning social networks with activations and suppressions},
month=jun,
year = 2010,
journal = {Theoretical Computer Science},
volume = 411,
number = {29--30},
pages = {2729--2740}
}

Randomized consensus in expected O(n log n) individual work

James Aspnes, Hagit Attiya, and Keren Censor. Randomized consensus in expected O(n log n) individual work. In Twenty-Seventh annual ACM Symposium on Principles of Distributed Computing, August 2008, pp. 325–334.

Abstract

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. The fastest previously known algorithm requires a process to perform an expected O(n log² n) read and write operations in the worst case. In our algorithm, each process executes at most an expected O(n log n) read and write operations. It is shown that shared coin algorithms can be combined together to yield an algorithm with O(n log n) individual work and O(n²) total work.

BibTeX

Download
@inproceedings{AspnesAC2008,
author = {James Aspnes and Hagit Attiya and Keren Censor},
title = {Randomized consensus in expected {$O(n \log n)$} individual work},
month=aug,
year = 2008,
booktitle = {PODC '08: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing},
pages = {325--334}
}

Learning acyclic probabilistic circuits using test paths

Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, and Lev Reyzin. Learning acyclic probabilistic circuits using test paths. Journal of Machine Learning Research, 10(Aug):1881–1911, 2009. An earlier version appeared in Twenty-First International Conference on Learning Theory (COLT), July 2008, pp. 169–179.

Abstract

We define a model of learning probabilistic acyclic circuits using value injection queries, in which an arbitrary subset of wires is set to fixed values, and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm (Angluin et al., STOC 2006) to show that there is a polynomial time algorithm that uses value injection queries to learn Boolean probabilistic circuits of constant fan-in and logarithmic depth. In the process, we discover that test paths fail utterly for circuits over alphabets of size greater than two and establish upper and lower bounds on the attenuation factor of test paths versus general experiments for general and transitively reduced Boolean probabilistic circuits. To overcome the limitations of test paths for non-Boolean alphabets, we introduce function injection queries, which allow the symbols on a wire to be mapped to other symbols rather than just to themselves or constants.

BibTeX

Download
@article{AngluinACER2009,
author = {Dana Angluin and James Aspnes and Jiang Chen and David Eisenstat and Lev Reyzin},
title = {Learning acyclic probabilistic circuits using test paths},
month=aug,
year = 2009,
journal = {Journal of Machine Learning Research},
pages = {1881--1911},
volume = 10,
number = {Aug}
}

Ranged hash functions and the price of churn

James Aspnes, Muli Safra, and Yitong Yin. Ranged hash functions and the price of churn. Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2008, pp. 1066–1075.

Abstract

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 servers or network connections. Monotone ranged hash functions are a particular class of ranged hash functions that minimize item reassignments in response to churn: changes in the set of available buckets. The canonical example of a monotone ranged hash function is the ring-based consistent hashing mechanism of Karger et al. (1997). These hash functions give a maximum load of Θ((n/m) log m) when n is the number of items and m is the number of buckets. The question of whether some better bound could be obtained using a more sophisticated hash function has remained open. We resolve this question by showing two lower bounds. First, the maximum load of any randomized monotone ranged hash function is Ω(√((n/m) log m)) when n=o(m log m). This bound covers almost all of the nontrivial case, because when n = Ω(m log m), simple random assignment matches the trivial lower bound of Ω(n/m). We give a matching (though impractical) upper bound that shows that our lower bound is tight over almost all of its range. Second, for randomized monotone ranged hash functions derived from metric spaces, there is a further trade-off between the expansion factor of the metric and the load balance, which for the special case of growth-restricted metrics gives a bound of Ω((n/m) log m), asymptotically equal to that of consistent hashing. These are the first known non-trivial lower bounds for ranged hash functions. They also explain why in ten years no better ranged hash functions have arisen to replace consistent hashing.

BibTeX

Download
@inproceedings{AspnesSY2008,
author    = {James Aspnes and Muli Safra and Yitong Yin},
title     = {Ranged hash functions and the price of churn},
month = jan,
year      = {2008},
booktitle="Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = {1066--1075}
}

O(log n)-time overlay network construction from graphs with out-degree 1

James Aspnes and Yinghua Wu. O(log n)-time overlay network construction from graphs with out-degree 1. Principles of Distributed Systems; 11th International Conference, OPODIS 2007, Gaudaloupe, French West Indies, December 17–20, 2007, Proceedings. Lecture Notes in Computer Science 4878. Springer-Verlag, December 2007, pp. 286–300.

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 peer-to-peer systems where each node attempts to join by contacting some single other node. This algorithm constructs a balanced search tree in time O(W+log n), improving by a factor of log n on the previous bound starting from a general graph, while retaining the properties of low contention and short messages. Our construction includes an improved version of the distributed Patricia tree structure of (Angluin et al., 2005) that we call a double-headed radix tree. This data structure responds gracefully to node failures and supports search, predecessor, and successor operations in O(W) time with smoothly distributed load for predecessor and successor operations. Though the resulting tree data structure is highly vulnerable to disconnection due to failures, the fast predecessor and successor operations (as shown in previous work) can be used to quickly construct standard overlay networks with more redundancy.

BibTeX

Download
@inproceedings{AspnesW2007,
author = {James Aspnes and Yinghua Wu},
title = {{$O(\log n)$}-time overlay network construction from graphs with out-degree {$1$}},
month = dec,
year = 2007,
booktitle = {Principles of Distributed Systems;
11th International Conference, OPODIS 2007,
Gaudaloupe, French West Indies, December 17--20, 2007. Proceedings},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
volume = 4878,
pages={286--300}}

Worm versus alert: Who wins in a battle for control of a large-scale network?

James Aspnes, Navin Rustagi, and Jared Saia. Worm versus alert: Who wins in a battle for control of a large-scale network? . Principles of Distributed Systems; 11th International Conference, OPODIS 2007, Gaudaloupe, French West Indies, December 17–20, 2007, Proceedings. Lecture Notes in Computer Science 4878. Springer-Verlag, December 2007, pp. 443–456.

Abstract

Consider the following game between a worm and an alert 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 with small but constant probability. The game starts with a single node becoming infected. In every round thereafter, every infected node sends out a constant number of worms to other nodes in the population, and every alerted node sends out a constant number of alerts. Nodes in the network change state according to the following three rules: 1) If a worm is received by a node that is not a detector and is not alerted, that node becomes infected; 2) If a worm is received by a node that is a detector, that node becomes alerted; 3) If an alert is received by a node that is not infected, that node becomes alerted.

We make two assumptions about this game. First, that an infected node can send worm messages to any other node in the network but, in contrast, an alerted node can send alert messages only through a previously determined, constant degree overlay network. Second, we assume that the infected nodes are intelligent, coordinated and essentially omniscient. In other words, the infected nodes know everything except for which nodes are detectors and the alerted nodes' random coin flips i.e. they know the topology of the overlay network used by the alerts; which nodes are alerted and which are infected at any time; where alerts and worms are being sent; the overall strategy used by the alerted nodes; etc. The alerted nodes are assumed to know nothing about which other nodes are infected or alerted, where alerts or worms are being sent, or the strategy used by the infected nodes.

Is there a strategy for the alerted nodes that ensures only a vanishingly small fraction of the nodes become infected, no matter what strategy is used by the infected nodes? Surprisingly, the answer is yes. In particular, we prove that a simple strategy achieves this result with probability approaching 1 provided that the overlay network has good node expansion. Specifically, this result holds if d ≥ α and α / (β(1-γ)} > 2d/c, where α and β represent the rate of the spread of the alert and worm respectively; γ is the probability that a node is a detector node; d is the degree of the overlay network; and c is the node expansion of the overlay network. Next, we give empirical results that suggest that our algorithms for the alert may be useful in current large-scale networks. Finally, we show that if the overlay network has poor expansion, in particular if (1-γ)β > d, then the worm will likely infect almost all of the non-detector nodes.

BibTeX

Download
@inproceedings{AspnesRS2007,
author = {James Aspnes and Navin Rustagi and Jared Saia},
title = {Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?},
month = dec,
year = 2007,
booktitle = {Principles of Distributed Systems;
11th International Conference, OPODIS 2007,
Gaudaloupe, French West Indies, December 17--20, 2007. Proceedings},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
volume = 4878,
pages={443--456}}

The computational power of population protocols

Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing 20(4):279–304, November 2007. (PODC 2006 special issue.) Incorporates material previously appearing in OPODIS 2005 and PODC 2006. Available as arXiv:cs.CC/0608084.

Abstract

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 in the all-pairs family of communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model. Removing the assumption of two-way interaction, we also consider several variants of the model in which agents communicate by anonymous message-passing where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. These one-way models are distinguished by whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. We characterize the classes of predicates stably computable in each of these one-way models using natural subclasses of the semilinear predicates.

BibTeX

Download
@article(AngluinAER2007,
title="The computational power of population protocols",
author="Dana Angluin and James Aspnes and David Eisenstat and Eric Ruppert",
journal={Distributed Computing},
volume=20,
number=4,
pages={279--304},
month = nov,
year = 2007,
)

An introduction to population protocols

James Aspnes and Eric Ruppert. An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science, Distributed Computing Column, 93:98–117, October 2007. An updated and extended version appears in Middleware for Network Eccentric and Mobile Applications, Benoît Garbinato, Hugo Miranda, and Luís Rodrigues, eds., Springer-Verlag, 2009, pp. 97–120.

Abstract

The population protocol model describes a collection of tiny mobile agents that interact with one another to carry out a computation. The agents are identically programmed finite state machines. Interactions between pairs of agents cause the two agents to update their states. These interactions are scheduled by an adversary, subject to a fairness constraint. Input values are initially distributed to the agents, and the agents must eventually converge to the correct output value. This framework can be used to model mobile ad hoc networks of tiny devices or collections of molecules undergoing chemical reactions. We survey results that describe what can be computed in various versions of the population protocol model.

BibTeX

Download
@article{AspnesR2007,
author = {James Aspnes and Eric Ruppert},
title = {An introduction to population protocols},
journal = {Bulletin of the European Association for Theoretical Computer Science},
volume=93,
pages={98--117},
month=oct,
year = 2007}

@incollection{AspnesR2009,
author = {James Aspnes and Eric Ruppert},
title = {An introduction to population protocols},
booktitle = {Middleware for Network Eccentric and Mobile Applications},
editor = {Beno\^it Garbinato and Hugo Miranda and Lu\'is Rodrigues},
pages={97--120},
publisher = {Springer-Verlag},
year = 2009}

A simple population protocol for fast robust approximate majority

Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing 21(2):87–102, July 2008 (DISC 2007 special issue). An earlier version appeared in Distributed Computing, 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24–26, 2007, Proceedings, pp. 20–32.

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 configuration of x's, y's and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values x or y. Additionally, the value chosen should be the majority non-blank initial value, provided it exceeds the minority by a sufficient margin. We prove that with high probability the agents reach consensus in time O(log n) and the value chosen is the majority provided that its initial margin is at least ω(sqrt(n) log n). This protocol has the additional property of tolerating Byzantine behavior in o(sqrt(n)) of the agents, making it the first known population protocol that tolerates Byzantine agents.

BibTeX

Download
@article{AngluinAE2008majority,
author = {Dana Angluin and James Aspnes and David Eisenstat},
title = {A simple population protocol for fast robust approximate majority},
journal = {Distributed Computing},
volume=21,
number=2,
month = jul,
year = 2008,
pages= {87--102},
}

Learning large-alphabet and analog circuits with value injection queries

Dana Angluin, James Aspnes, Jiang Chen, and Lev Reyzin. Learning large-alphabet and analog circuits with value injection queries. Machine Learning 72(1–2):113–138, August 2008 (COLT 2007 special issue). An earlier version appeared in Twentieth Annual Conference on Learning Theory, June 2007, pp. 51–65. Winner, Best Student Paper award.

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 circuits, we develop the Distinguishing Paths Algorithm, that learns such a circuit using (ns)O(k) value injection queries and time polynomial in the number of queries. We describe a generalization of the algorithm to the class of circuits with shortcut width bounded by b that uses (ns)O(k+b) value injection queries. Both algorithms use value injection queries that fix only O(kd) wires, where d is the depth of the target circuit. We give a reduction showing that without such restrictions on the topology of the circuit, the learning problem may be computationally intractable when s = nΘ(1), even for circuits of depth O(log n). We apply our large-alphabet learning algorithms to the problem of approximate learning of analog circuits and show that analog circuits with constant bounded fan-in, logarithmic depth, and constant bounded shortcut width whose gate functions satisfy a Lipschitz condition are approximately learnable in polynomial time using value injection queries. Finally, we consider models in which behavioral equivalence queries are also available, and extend and improve the learning algorithms of (Angluin et al., 2006) to handle general classes of gates functions that are polynomial time learnable from counterexamples.

BibTeX

Download
@article{AngluinACR2008,
author = {Dana Angluin and James Aspnes and Jiang Chen and Lev Reyzin},
title = {Learning large-alphabet and analog circuits with value injection queries},
journal   = {Machine Learning},
volume    = {72},
number    = {1-2},
month     = aug,
year      = {2008},
pages     = {113-138},
}

Path-independent load balancing with unreliable machines

James Aspnes, Yang Richard Yang, and Yitong Yin. Path-independent load balancing with unreliable machines. Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007, pp. 814–823. Available as arXiv:cs.DS/0607026.

Abstract

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 failures. We assume that the set of jobs is known in advance but that the pattern of machine failures is unpredictable. Motivated by the requirements of BGP routing, we consider path-independent algorithms, with the property that the job assignment is completely determined by the subset of available machines and not the previous history of the assignments. We examine first the question of performance measurement of path-independent load-balancing algorithms, giving the measure of makespan and the normalized measure of reassignments cost. We then describe two classes of algorithms for optimizing these measures against an oblivious adversary for identical machines. The first, based on independent random assignments, gives expected reassignment costs within a factor of 2 of optimal and gives a makespan within a factor of O(log m/log log m) of optimal with high probability, for unknown job sizes. The second, in which jobs are first grouped into bins and at most one bin is assigned to each machine, gives constant-factor ratios on both reassignment cost and makespan, for known job sizes. Several open problems are discussed.

BibTeX

Download
@inproceedings{AspnesYY2007,
author    = {James Aspnes and Yang Richard Yang and Yitong Yin},
title     = {Path-independent load balancing with unreliable machines},
month = jan,
year      = {2007},
booktitle="Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = {814--823}
}

A theory of network localization

J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R. Yang, B. D. O. Anderson, and P. N. Belhumeur. A theory of network localization. IEEE Transactions on Mobile Computing, 12(5):1663–1678, December 2006.

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 the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

BibTeX

Download
@article(AspnesEGMWYAB2006,
title="A theory of network localization",
author="J. Aspnes and T. Eren and D. K. Goldenberg and A. S. Morse and W. Whiteley and Y. R. Yang and B. D. O. Anderson and P. N. Belhumeur",
journal="IEEE Transactions on Mobile Computing",
volume=5,
number=12,
pages={1663--1678},
month=dec,
year=2006
)

Eight open problems in distributed computing

James Aspnes, Costas Busch, Shlomi Dolev, Panagiota Fatourou, Chryssis Georgiou, Alex Shvartsman, Paul Spirakis, and Roger Wattenhofer. Eight open problems in distributed computing. Bulletin of the European Association for Theoretical Computer Science, Distributed Computing Column, 90:109–126, October 2006.

Abstract

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 is currently being enriched with many new topics inspired from modern technological advances (e.g., the Internet). In this note, we present eight open problems in Distributed Computing Theory that span a wide range of topics-both classical and modern.

BibTeX

Download
@article{AspnesBD+2006,
author = {James Aspnes and Costas Busch and Shlomi Dolev and Panagiota Fatourou and Chryssis Georgiou and Alex Shvartsman and Paul Spirakis and Roger Wattenhofer},
title = {Eight open problems in distributed computing},
journal = {Bulletin of the European Association for Theoretical Computer Science},
volume = 90,
pages = {109--126},
month = oct,
year = 2006}

Fast computation by population protocols with a leader

Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing 21(2):183–199, July 2008 (DISC 2007 special issue). An earlier version appeared in Distributed Computing, 20th International Symposium, DISC 2006, pp. 61–75. Available as YALEU/DCS/TR-1332, May 2006.

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 interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual register machine with high probability in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log5 n) interactions using a simple register representation or in O(n log² n) interactions using a more sophisticated representation that requires an extra O(n logO(1) n)-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Applications include a reduction of the cost of computing a semilinear predicate to O(n log5 n) interactions from the previously best-known bound of O(n² log n) interactions and simulation of a LOGSPACE Turing machine using O(n log² n) interactions per step after an initial O(n logO(1) n)-interaction startup phase. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an expected Θ(1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption.

BibTeX

Download
@article(AngluinAE2008fast,
title="Fast computation by population protocols with a leader",
author="Dana Angluin and James Aspnes and David Eisenstat",
journal="Distributed Computing",
volume=21,
number=3,
month=sep,
year=2008,
pages={183--199}
)

Stably computable predicates are semilinear

Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. Twenty-Fifth ACM Symposium on Principles of Distributed Computing, July 2006, pp. 292–299.

Abstract

We consider the model of population protocols introduced by Angluin et. al., in which anonymous finite-state agents stably compute a predicate of their inputs via two-way interactions in the all-pairs family of communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model.

BibTeX

Download
@inproceedings{AngluinAE2006semilinear,
 author = {Dana Angluin and James Aspnes and David Eisenstat},
 title = {Stably computable predicates are semilinear},
 booktitle = {PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing},
 year = {2006},
 isbn = {1-59593-384-0},
 pages = {292--299},
 location = {Denver, Colorado, USA},
 doi = {http://doi.acm.org/10.1145/1146381.1146425},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }

Learning a circuit by injecting values

Dana Angluin, James Aspnes, Jiang Chen, and Yinghua Wu. Learning a circuit by injecting values. Journal of Computer and System Sciences 75(1):60–77, January 2009. (Special Issue: Learning Theory 2006.) An earlier version appeared in Thirty-Eighth Annual ACM Symposium on Theory of Computing, May 2006, pp. 584–593.

Abstract

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 the circuit's single output wire may be observed. We give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) boolean circuits of constant depth and unbounded fan-in over AND, OR, and NOT gates. Thus, both AC0 and NC1 circuits are learnable in polynomial time in this model. Negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn AND/OR circuits of unbounded depth and fan-in; it is NP-hard to learn AND/OR circuits of unbounded depth and fan-in 2; and it is NP-hard to learn circuits of bounded depth and unbounded fan-in over AND, OR, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. We also consider the effect of adding an oracle for behavioral equivalence. In this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn boolean circuits with arbitrary fan-in and unbounded depth over AND, OR, and NOT gates. A corollary is that these two classes are PAC-learnable if experiments are available.

BibTeX

Download
@article{AngluinACW2009,
 author = {Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu},
 title = {Learning a circuit by injecting values},
 journal = {Journal of Computer and System Sciences},
 month = jan,
 year = {2009},
 pages = {60--77},
 volume = 75,
 number = 1,
 }

On the power of anonymous one-way communication

Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. On the power of anonymous one-way communication. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 396–411.

Abstract

We consider a network 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 to the recipient. Even with unbounded message sizes and process states, such a system can compute only limited predicates on inputs held by the processes. In the finite-state case, we show how the exact strength of the model depends critically on design choices that are irrelevant in the unbounded-state case, such as whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. These results may have implications for the design of distributed systems where processor power is severely limited, as in sensor networks.

BibTeX

Download
@inproceedings(AngluinAER2005,
title="On the power of anonymous one-way communication",
author="Dana Angluin and James Aspnes and David Eisenstat and Eric Ruppert",
booktitle="Principles of Distributed Systems;
9th International Conference, OPODIS 2005;
Pisa, Italy; December 2005; Revised Selected Papers",
series="Lecture Notes in Computer Science",
volume=3974,
month=dec,
year=2005,
pages={396--411}
)

Self-stabilizing population protocols

Dana Angluin, James Aspnes, Michael J. Fischer, and Hong Jiang. Self-stabilizing population protocols. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 103–117. ACM Transactions on Autonomous and Adaptive Systems 3(4):13. (Special issue on stabilization, safety, and security of distributed systems.)

Abstract

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 deterministically with constant space per node in this model. Constant-space protocols are given for leader election in rings, local-addressing in degree-bounded graphs, and establishing consistent global direction in an undirected ring. A protocol to construct a spanning tree in regular graphs using O(log D) memory is also given, where D is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.

BibTeX

Download
@article(AngluinAFJ2008,
title="Self-stabilizing population protocols",
author="Dana Angluin and James Aspnes and Michael J. Fischer and Hong Jiang",
journal="ACM Transactions on Autonomous and Adaptive Systems",
volume=3,
number=4,
pages={13},
month=nov,
year=2008,
)

Skip B-trees

Ittai Abraham, James Aspnes, and Jian Yuan. Skip B-trees. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 366–380.

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 deletion operations. The data structure is highly fault tolerant even to adversarial failures, and allows for particularly simple repair mechanisms. Related resource keys are kept in blocks near each other enabling efficient range queries. Using this data structure, we describe a new distributed peer-to-peer network, the Distributed Skip B-Tree. Given m data items stored in a system with n nodes, the network allows to perform a range search operation for r consecutive keys that costs only O(logb m + r/b) where b=Θ(m/n). In addition, our distributed Skip B-tree search network has provable polylogarithmic costs for all its other basic operations like insert, delete, and node join. To the best of our knowledge, all previous distributed search networks either provide a range search operation whose cost is worse than ours or may require a linear cost for some basic operation like insert, delete, and node join.

BibTeX

Download
@inproceedings(AbrahamAY2005,
title="Skip {B}-trees",
author="Ittai Abraham and James Aspnes and Jian Yuan",
booktitle="Principles of Distributed Systems;
9th International Conference, OPODIS 2005;
Pisa, Italy; December 2005; Revised Selected Papers",
series="Lecture Notes in Computer Science",
volume=3974,
month=dec,
year=2005,
pages={366--380}
)

Spreading alerts quietly and the subgroup escape problem

James Aspnes, Zoë Diamadi, Kristian Gjøsteen, René Peralta, and Aleksandr Yampolskiy. Spreading alerts quietly and the subgroup escape problem. Accepted to Journal of Cryptology. An earlier version appeared in Advances in Cryptology — ASIACRYPT 2005: 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4–8, 2005. Proceedings. Lecture Notes in Computer Science 3788, Springer-Verlag, December 2005, pp. 253–272. Available as YALEU/DCS/TR-1326, December 2005.

Abstract

We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit-commitment, which is AND-homomorphic. We show that the BCM has natural and important applications. In particular, we use it to construct a mechanism for transmitting alerts undetectably in a message-passing system of n nodes. Our algorithms allow an alert to quickly propagate to all nodes without its source or existence being detected by an adversary, who controls all message traffic. Our proofs of security are based on a new subgroup escape problem, which seems hard on certain groups with bilinear pairings and on elliptic curves over the ring ℤn.

BibTeX

Download
@inproceedings(AspnesDGPY2005,
title="Spreading alerts quietly and the subgroup escape problem",
author="James Aspnes and Zo{\"e} Diamadi and Kristian Gj\o{}steen and Ren\'e Peralta and Aleksandr Yampolskiy",
booktitle="Advances in Cryptology --- ASIACRYPT 2005: 11th International
Conference on the Theory and Application of Cryptology and Information
Security, Chennai, India, December 4--8, 2005.  Proceedings.",
publisher="Springer-Verlag",
series="Lecture Notes in Computer Science",
volume="3788",
month=dec,
year=2005,
pages={253--272}
)

Distributed data structures for P2P systems

James Aspnes and Gauri Shah. Distributed data structures for P2P systems. Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, Jie Wu, editor, CRC Press, 2005, pages 685–700.

Abstract

This article describes some recent distributed data structures that have been proposed to implement peer-to-peer systems for resource sharing. We first give a broad overview of Distributed Hash Tables (DHTs) which form the basic building blocks of many peer-to-peer systems, and describe some of the features of the more popular DHT implementations. We also briefly describe some of the other organized data structures that have been proposed to build peer-to-peer systems. We then focus on describing skip graphs, which overcome some limitations of DHTs such as lack of spatial locality and lack of support for range queries.

BibTeX

Download
@incollection(AspnesS2005,
title="Distributed data structures for {P2P} systems",
author="James Aspnes and Gauri Shah",
booktitle="Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks",
editor="Jie Wu",
publisher="CRC press",
month=aug,
pages={685--700},
year=2005
)

Exposing computationally-challenged Byzantine impostors

James Aspnes, Collin Jackson, and Arvind Krishnamurthy. Exposing computationally-challenged Byzantine impostors. Available as YALEU/DCS/TR-1332, July 2005.

Abstract

Internet protocols permit a single machine to masquerade as many, allowing an adversary to appear to control more nodes than it actually does. The possibily of such Sybil attacks has been taken to mean that distributed algorithms that tolerate only a fixed fraction of faulty nodes are not useful in peer-to-peer systems unless identities can be verified externally. The present work argues against this assumption, by presenting practical algorithms for the central distributed computing problem of Byzantine agreement that defend against Sybil attacks by using moderately hard puzzles as a pricing scheme for identities. Though our algorithms do not prevent Sybil attacks entirely, they solve Byzantine agreement (and some useful variants) when the limited fraction of nodes that can fail is replaced by a limited fraction of the total computational power. These results suggest that Byzantine agreement and similar tools from the distributed computing literature are likely to help solve the problem of adversarial behavior by components of peer-to-peer systems.

BibTeX

Download
@techreport(AspnesJK2005,
title="Exposing computationally-challenged {B}yzantine impostors",
author="James Aspnes and Collin Jackson and Arvind Krishnamurthy",
institution="Yale University Department of Computer Science",
number="YALEU/DCS/TR-1332",
month=jul,
year=2005
)

Fast construction of overlay networks

Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin. Fast construction of overlay networks. Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 2005, pages 145–154.

Abstract

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 network, but each participating node initially has pointers to only a handful of other participants. The output of the mechanism is a linked list of all participants sorted by their identifiers, which can be used as a foundation for building various linear overlay networks such as Chord or skip graphs. Assuming the initial pointer graph is weakly-connected with maximum degree d and the length of a node identifier is W, the mechanism constructs a binary search tree of nodes of depth O(W) in expected O(W log n) time using expected O((d+W)n log n) messages of size O(W) each. Furthermore, the algorithm has low contention: at any time there are only O(d) undelivered messages for any given recipient. A lower bound of Ω(d + log n) is given for the running time of any procedure in a related synchronous model that yields a sorted list from a degree-d weakly-connected graph of n nodes. We conjecture that this lower bound is tight and could be attained by further improvements to our algorithms.

BibTeX

Download
@inproceedings(AngluinACWY2005,
title="Fast construction of overlay networks",
author="Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu and Yitong Yin",
booktitle="Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures",
month=jul,
year=2005,
pages={145--154}
)

The expansion and mixing time of skip graphs with applications

James Aspnes and Udi Wieder. The expansion and mixing time of skip graphs with applications. Distributed Computing 21(6):385–393, March 2009. An earlier version appeared in Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 2005, pages 126–134.

Abstract

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 connected component even after an adversarial deletion of nodes. We show how the expansion property could be used to sample a node in the skip graph in a highly efficient manner. We also show that the expansion property could be used to load balance the skip graph quickly. Finally it is shown that the skip graph could serve as an unstructured P2P system, thus it is a good candidate for a hybrid P2P system.

BibTeX

Download
@article(AspnesW2009,
title="The expansion and mixing time of skip graphs with applications",
author="James Aspnes and Udi Wieder",
journal="Distributed Computing",
month=mar,
year=2009,
pages={385--393}
)

Stably computable properties of network graphs

Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, and René Peralta. Stably computable properties of network graphs. Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USE, June/July, 2005, Proceedings, Lecture Notes in Computer Science, volume 3560, Springer-Verlag, June 2005, pp. 63–74.

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 of the network graph can be stably computed by the devices. We show that they can detect whether the network has degree bounded by a constant d, and, if so, organize a computation that achieves asymptotically optimal linear memory use. We define a model of stabilizing inputs to such devices and show that a large class of predicates of the multiset of final input values are stably computable in any weakly-connected network. We also show that nondeterminism in the transition function does not increase the class of stably computable predicates.

BibTeX

Download
@inproceedings(AngluinACFJP2005,
title="Stably computable properties of network graphs",
author="Dana Angluin and James Aspnes and Melody Chan and Michael J. Fischer and Hong Jiang and Ren\'e Peralta",
booktitle="Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USE, June/July, 2005, Proceedings",
editor="Viktor K. Prasanna and Sitharama Iyengar and Paul Spirakis and Matt Welsh",
series="Lecture Notes in Computer Science",
publisher="Springer-Verlag",
pages     = {63--74},
volume="3560",
month=jun,
year=2005
)

Inoculation strategies for victims of viruses and the sum-of-squares partition problem

James Aspnes, Kevin Chang, and Aleksandr Yampolskiy. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. Journal of Computer and System Sciences, 72(6):1077–1093, September 2006. An ealier version appeared in Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2005, pp. 43–52. Available as YALEU/DCS/TR-1295, July 2004.

Abstract

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 and a loss L if a virus that starts at a random initial point in the graph can reach it without being stopped by some intermediate node. The goal of individual nodes is to minimize their individual expected cost. We prove many game theoretic properties of the model, including an easily-applied characterization of Nash equilibria, culminating in our showing that allowing selfish users to choose Nash equilibrium strategies is highly undesirable, because the price of anarchy is an unacceptable Θ(n) in the worst case. This shows in particular that a centralized solution can give a much better total cost than an equilibrium solution. Though it is NP-hard to compute such a social optimum, we show that the problem can be reduced to a previously unconsidered combinatorial problem that we call the sum-of-squares partition problem. Using a greedy algorithm based on sparse cuts, we show that this problem can be approximated to within a factor of O(log²n), giving the same approximation ratio for the inoculation game.

BibTeX

Download
@article(AspnesCY2006,
title="Inoculation strategies for victims of viruses and the sum-of-squares partition problem",
author="James Aspnes and Kevin Chang and Aleksandr Yampolskiy",
journal=jcss,
volume=72,
number=6,
pages={1077--1093},
month=sep,
year=2006,
)

Relationships between broadcast and shared memory in reliable anonymous distributed systems

James Aspnes, Faith Ellen Fich, and Eric Ruppert. Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distributed Computing 18(3):209–219, February 2006. (DISC 2004 special issue.) An earlier version appeared in Proceedings of the Eighteenth International Symposium on Distributed Computing (DISC 2004), October 2004, pp. 260–274.

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 relative powers of systems with different communications mechanisms: anonymous broadcast, read-write registers, or registers supplemented with additional shared-memory objects. We show that a system with anonymous broadcast can simulate a system of shared-memory objects if and only if the objects satisfy a property we call idemdicence; this result holds regardless of whether either system is synchronous or asynchronous. Conversely, the key to simulating anonymous broadcast in anonymous shared memory is the ability to count: broadcast can be simulated by an asynchronous shared-memory system that uses only counters, but registers by themselves are not enough. We further examine the relative power of different types and sizes of bounded counters and conclude with a non-robustness result.

BibTeX

Download
@article(AspnesFR2006,
title="Relationships between broadcast and shared memory in reliable anonymous distributed systems",
author="James Aspnes and Faith Ellen Fich and Eric Ruppert",
journal={Distributed Computing},
volume=18,
number=3,
month=feb,
year=2006,
pages={209--219}
)

Towards a theory of data entanglement

James Aspnes, Joan Feigenbaum, Aleksandr Yampolskiy, and Sheng Zhong. Towards a theory of data entanglement. Theoretical Computer Science 389(1–2):26–43, December 2007. An earlier version appeared in Ninth European Symposium on Research in Computer Security, Lecture Notes in Computer Science 3192, Springer-Verlag, September 2004, pp. 177–192.

Abstract

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 it hard to corrupt the data of any one user without corrupting the data of all users. AONI can be a useful defense against negligent or dishonest storage providers who might otherwise be tempted to discard documents belonging to users without much clout. We show that, if all users use a fixed standard recovery algorithm, we can implement AONI using a MAC, but, if some of the users adopt instead a non-standard recovery algorithm provided by the dishonest storage provider, AONI can no longer be achieved. However, even for the latter scenario, we describe a simple entangling mechanism that provides AONI for a restricted class of destructive adversaries.

BibTeX

Download
@article(AspnesFYZ2007,
title="Towards a theory of data entanglement",
author="James Aspnes and Joan Feigenbaum and Aleksandr Yampolskiy and Sheng Zhong",
journal="Theoretical Computer Science",
volume=389,
number={1--2},
month=dec,
year=2007,
)

Computation in networks of passively mobile finite-state sensors

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4):235–253, March 2006. (PODC 2004 special issue.) An earlier version appeared in Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, July 2004, pp. 290–299.

Abstract

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 finite but unbounded size. With a fairness condition on interactions, we define the concept of eventual computation of a function or predicate, and give protocols that eventually compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all eventually computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P intersect RL. Several open problems and promising future directions are discussed.

BibTeX

Download
@article(AngluinADFP2006,
title="Computation in networks of passively mobile finite-state sensors",
author="Dana Angluin and James Aspnes and Zo{\"e} Diamadi and Michael J. Fischer and Ren\'e Peralta",
journal="Distributed Computing",
month=mar,
year=2006,
pages={235--253}
)

Load balancing and locality in range-queriable data structures

James Aspnes, Jonathan Kirsch, and Arvind Krishnamurthy. Load balancing and locality in range-queriable data structures. Twenty-Third ACM Symposium on Principles of Distributed Computing, July 2004, pp. 115–124.

Abstract

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 arbitrary load measure specified by the user and geographical locality, assigning elements with similar keys to the same server. Though our mechanism is specifically designed to improve the performance of skip graphs, it can be adapted to provide deterministic, locality-preserving load-balancing to any distributed data structure that orders machines in a ring or line.

BibTeX

Download
@inproceedings(AspnesKK2004,
title="Load balancing and locality in range-queriable data structures",
author="James Aspnes and Jonathan Kirsch and Arvind Krishnamurthy",
booktitle="Twenty-Third ACM Symposium on Principles of Distributed Computing",
month=jul,
year=2004,
pages={115--124}
)

On the computational complexity of sensor network localization

James Aspnes, David Goldenberg, and Yang Richard Yang. On the computational complexity of sensor network localization. Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004. Proceedings. Lecture Notes in Computer Science 3121, Springer-Verlag, 2004, pp. 32–44. Available as YALEU/DCS/TR-1282, April 2004.

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 for sensor networks is to reconstruct the positions of all of the sensors in a network, given the distances between all pairs of sensors that are within some radius r of each other. In the past few years, many algorithms for solving the localization problem were proposed, without knowing the computational complexity of the problem. In this paper, we show that no polynomial-time algorithm can solve this problem in the worst case, even for sets of distance pairs for which a unique solution exists, unless RP=NP. We also discuss the consequences of our result and present open problems.

BibTeX

Download
@inproceedings(AspnesGY2004,
title="On the computational complexity of sensor network localization",
author="James Aspnes and David Goldenberg and Yang Richard Yang",
booktitle="Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004. Proceedings.",
series={Lecture Notes in Computer Science},
volume=3121,
publisher="Springer-Verlag",
year=2004,
pages={32--44}
)

Urn automata

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Urn automata. Available as YALEU/DCS/TR-1280, November 2003.

Abstract

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 and replace tokens in the urn but cannot control which tokens it receives. We consider the computational power of urn automata, showing that an urn automaton with O(f(n)) tokens can, with high probability, simulate a probabilistic Turing machine using O(log f(n)) space and vice versa, as well as giving several technical results showing that the computational power of urn automata is not affected by variations in parameters such as the size of the state space, the number of tokens sampled per step, and so forth. Motivated by problems in distributed computing, we consider a special class of urn automata called pairing automata that model systems of finite-state machines that interact through random pairwise encounters. We show that pairing automata recognize precisely the symmetric languages recognized by urn automata.

BibTeX

Download
@techreport(AngluinADFP2003,
title="Urn automata",
author="Dana Angluin and James Aspnes and Zo{\"e} Diamadi and Michael J. Fischer and Ren\'e Peralta",
institution="Yale University Department of Computer Science",
number="YALEU/DCS/TR-1280",
month=nov,
year=2003
)

Randomized protocols for asynchronous consensus

James Aspnes. Randomized protocols for asynchronous consensus. Invited survey paper for Distributed Computing PODC 20th anniversary issue, 16:(2–3):165–175, September 2003. Available as arXiv:cs.DS/0209014.

Abstract

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 process can fail. Since its publication, two decades of work on fault-tolerant asynchronous consensus algorithms have evaded this impossibility result by using extended models that provide (a) randomization, (b) additional timing assumptions, (c) failure detectors, or (d) stronger synchronization mechanisms than are available in the basic model. Concentrating on the first of these approaches, we illustrate the history and structure of randomized asynchronous consensus protocols by giving detailed descriptions of several such protocols.

BibTeX

Download
@article(Aspnes2003,
title="Randomized protocols for asynchronous consensus",
author="James Aspnes",
journal="Distributed Computing",
volume=16,
number={2--3},
pages={165--175},
month=sep,
year=2003
)

Towards better definitions and measures of Internet security

James Aspnes, Joan Feigenbaum, Michael Mitzenmacher, and David C. Parkes. Towards better definitions and measures of Internet security. Workshop on Large-Scale-Network Security and Deployment Obstacles, Landsdowne VA, March 2003.

Abstract

The conventional wisdom is that “the Internet is very insecure.” The subtitle of this workshop, namely “deployment obstacles,” implies that network owners, operators, and users could have solved pervasive security problems if they had deployed existing security technology. Is there solid evidence that either of these statements is true?

BibTeX

Download
@inproceedings(AspnesFMP2003,
title="Towards better definitions and measures of Internet security",
author="James Aspnes and Joan Feigenbaum and Michael Mitzenmacher and David C. Parkes",
booktitle="Workshop on Large-Scale-Network Security and Deployment Obstacles",
address="Landsdowne, VA",
month=mar,
year=2003
)

Skip graphs

James Aspnes and Gauri Shah. Skip graphs. ACM Transactions on Algorithms, 3(4):37, November 2007. An earlier version appeared in Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2003, pp. 384–393. Available as arXiv:cs.DS/0306043.

Abstract

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 that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, constructing, inserting new nodes into, searching a skip graph, and detecting and repairing errors in the data structure introduced by node failures can be done using simple and straightforward algorithms.

BibTeX

Download
@article(AspnesS2007,
title="Skip graphs",
author="James Aspnes and Gauri Shah",
journal="ACM Transactions on Algorithms",
month=nov,
year=2007,
volume=3,
number=4,
pages={37}
)

Fault-tolerant routing in peer-to-peer systems

James Aspnes, Zoë Diamadi, and Gauri Shah. Fault-tolerant routing in peer-to-peer systems. Twenty-First ACM Symposium on Principles of Distributed Computing, July 2002, pp. 223–232. Available as arXiv:cs.DS/0302022.

Abstract

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 problem can be modeled as the construction of a random graph embedded in a metric space whose points represent resource identifiers, where the probability of a connection between two nodes depends only on the distance between them in the metric space. We study the performance of a peer-to-peer system where nodes are embedded at grid points in a simple metric space: a one-dimensional real line. We prove upper and lower bounds on the message complexity of locating particular resources in such a system, under a variety of assumptions about failures of either nodes or the connections between them. Our lower bounds in particular show that the use of inverse power-law distributions in routing, as suggested by Kleinberg (1999), is close to optimal. We also give heuristics to efficiently maintain a network supporting efficient routing as nodes enter and leave the system. Finally, we give some experimental results that suggest promising directions for future work.

BibTeX

Download
@inproceedings(AspnesDS2002,
title="Fault-tolerant routing in peer-to-peer systems",
author="James Aspnes and Zo{\"e} Diamadi and Gauri Shah",
booktitle="Twenty-First ACM Symposium on Principles of Distributed Computing",
month=jul,
year=2002,
pages={223--232}
)

Wait-free consensus with infinite arrivals

James Aspnes, Gauri Shah, and Jatin Shah. Wait-free consensus with infinite arrivals. Thirty-Fourth Annual ACM Symposium on Theory of Computing, May 2002, pp. 524–533.

Abstract

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 weighted voting to achieve a majority outcome with at least constant probability that cannot be disguised even if a strong adversary is allowed to destroy infinitely many votes. The number of operations performed by process i is a polynomial function of i. Additional algorithms are given for solving consensus more efficiently in models with an unknown upper bound b on concurrency or an unknown upper bound n on the number of active processes; under either of these restrictions, it is also shown that the problem can be solved even with infinitely many anonymous processes by prefixing each instance of the shared coin with a naming algorithm that breaks symmetry with high probability. For many of these algorithms, matching lower bounds are proved that show that their per-process work is nearly optimal as a function of i, b, or n. The case of n active processes gives an algorithm for anonymous, adaptive consensus that requires only O(n log² n) per-process work, which is within a constant factor of the best previously known non-adaptive algorithm for a strong adversary. Finally, it is shown that standard universal constructions based on consensus continue to work with infinitely many processes with only slight modifications. This shows that in infinite distributed systems, as in finite ones, with randomness all things are possible.

BibTeX

Download
@inproceedings(AspnesSS2002,
title="Wait-free consensus with infinite arrivals",
author="James Aspnes and Gauri Shah and Jatin Shah",
booktitle="Thirty-Fourth Annual ACM Symposium on Theory of Computing",
month=may,
year=2002,
pages={524--533}
)

Opportunity-cost algorithms for combinatorial auctions

Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao. Opportunity-cost algorithms for combinatorial auctions. In E. J. Kontoghiorghes, B. Rustem, and S. Siokos, eds., Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance, Kluwer Academic Publishers, 2002, pp. 455–479. An earlier version is available as DIMACS technical report 2000-27 and as arXiv:cs.CE/0010031.

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 offers a price for some subset of the available goods and the auctioneer can only accept non-intersecting bids. Since this problem is difficult even to approximate in general, the algorithms are most useful when the bids are restricted to be connected node subsets of an underlying object graph that represents which objects are relevant to each other. The approximation ratios of the algorithms depend on structural properties of this graph and are small constants for many interesting families of object graphs. The running times of the algorithms are linear in the size of the bid graph, which describes the conflicts between bids. Extensions of the algorithms allow for efficient processing of additional constraints, such as budget constraints that associate bids with particular bidders and limit how many bids from a particular bidder can be accepted.

BibTeX

Download
@incollection(AkcogluADK2002,
title="Opportunity-cost algorithms for combinatorial auctions",
author="Karhan Akcoglu and James Aspnes and Bhaskar DasGupta and Ming-Yang Kao",
booktitle="Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance",
editor="E. J. Kontoghiorghes and B. Rustem and S. Siokos",
publisher="Kluwer Academic Publishers",
year=2002,
pages={455--479}
)

A combinatorial toolbox for protein sequence design and landscape analysis in the Grand Canonical model

James Aspnes, Julia Hartling, Ming-Yang Kao, Junhyong Kim, and Gauri Shah. A combinatorial toolbox for protein sequence design and landscape analysis in the Grand Canonical model. Journal of Computational Biology, 9(5):721–741, October, 2002. An earlier version appeared in Twelfth Annual International Symposium on Algorithms and Computation, December 2001, pp. 403–415. Available as arXiv:cs.CE/0101015.

Abstract

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 analyze the protein landscapes, i.e., the structures of the space of all protein sequences and their native 3D structures. Perhaps the most basic computational problem at this level is to take a target 3D structure as input and design a fittest protein sequence with respect to one or more fitness functions of the target 3D structure. We develop a toolbox of combinatorial techniques for protein landscape analysis in the Grand Canonical model of Sun, Brem, Chan, and Dill. The toolbox is based on linear programming, network flow, and a linear-size representation of all minimum cuts of a network. It not only substantially expands the network flow technique for protein sequence design in Kleinberg's seminal work but also is applicable to a considerably broader collection of computational problems than those considered by Kleinberg. We have used this toolbox to obtain a number of efficient algorithms and hardness results. We have further used the algorithms to analyze 3D structures drawn from the Protein Data Bank and have discovered some novel relationships between such native 3D structures and the Grand Canonical model.

BibTeX

Download
@article(AspnesHKKS2002,
title="A combinatorial toolbox for protein sequence design and landscape analysis in the {G}rand {C}anonical model",
author="James Aspnes and Julia Hartling and Ming-Yang Kao and Junhyong Kim and Gauri Shah",
journal="Journal of Computational Biology",
volume=9,
number=5,
pages={721--741},
month=oct,
year=2002
)

Towards understanding the predictability of stock markets from the perspective of computational complexity

James Aspnes, David F. Fischer, Michael J. Fischer, Ming-Yang Kao, and Alok Kumar. Towards understanding the predictability of stock markets from the perspective of computational complexity. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2001, pp. 745–754. Available as arXiv:cs.CE/0010021.

Abstract

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 agents are traders equipped with simple trading strategies, and their trades together determine the stock prices. Computer simulations show that a basic case of this model is already capable of generating price graphs which are visually similar to the recent price movements of high tech stocks. In the general model, we prove that if there are a large number of traders but they employ a relatively small number of strategies, then there is a polynomial-time algorithm for predicting future price movements with high accuracy. On the other hand, if the number of strategies is large, market prediction becomes complete in two new computational complexity classes CPP and promise-BCPP, where PNP[O(log N)] <= promise-BCPP <= CPP = PP. These computational completeness results open up a novel possibility that the price graph of a actual stock could be sufficiently deterministic for various prediction goals but appear random to all polynomial-time prediction algorithms.

BibTeX

Download
@inproceedings(AspnesFFKK2001,
title="Towards understanding the predictability of stock markets from the perspective of computational complexity",
author="James Aspnes and David F. Fischer and Michael J. Fischer and Ming-Yang Kao and Alok Kumar",
booktitle="Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms",
month=jan,
year=2001,
pages={745--754}
)

Fast deterministic consensus in a noisy environment

James Aspnes. Fast deterministic consensus in a noisy environment. Journal of Algorithms, 45(1):16–39, October, 2002. An earlier version appeared in Nineteenth Annual ACM Symposium on Principles of Distributed Computing, July 2000, pp. 299–309. Available as arXiv:cs.DS/0206012.

Abstract

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 scheduling, in which an adversarial schedule is perturbed randomly, and show that in this model randomness in the environment can substitute for randomness in the algorithm. In particular, we show that a simplified, deterministic version of Chandra's wait-free shared-memory consensus algorithm solves consensus in time at most logarithmic in the number of active processes. The proof of termination is based on showing that a race between independent delayed renewal processes produces a winner quickly. In addition, we show that the protocol finishes in constant time using quantum and priority-based scheduling on a uniprocessor, suggesting that it is robust against the choice of model over a wide range.

BibTeX

Download
@article(Aspnes2002,
title="Fast deterministic consensus in a noisy environment",
author="James Aspnes",
journal={Journal of Algorithms},
volume=45,
number=1,
pages={16--39},
month=oct,
year=2002
)

Lower bounds for distributed coin-flipping and randomized consensus

James Aspnes. Lower bounds for distributed coin-flipping and randomized consensus. Journal of the Association for Computing Machinery 45(3):415–450, May 1998. An earlier version appeared in Twenty-Ninth Annual ACM Symposium on Theory of Computing, May 1997, pp. 559–568.

Abstract

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 be combined to form a single global coin flip. An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to t local coin flips. We show that to guarantee at most constant bias, Ω(t²) local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately whether to hide or reveal each local coin, and (c) the game can detect which local coins have been hidden. If the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in t, Ω(t²/log² t) local coins are needed. Combining this fact with an extended version of the well-known Fischer-Lynch-Paterson impossibility proof of deterministic consensus, we show that given an adaptive adversary, any t-resilient asynchronous consensus protocol requires Ω(t²/log² t) local coin flips in any model that can be simulated deterministically using atomic registers. This gives the first non-trivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors.

BibTeX

Download
@article(Aspnes1998coin,
title="Lower bounds for distributed coin-flipping and randomized consensus",
author="James Aspnes",
journal=jacm,
volume=45,
number=3,
pages={415--450},
month=may,
year=1998
)

Competitive analysis of distributed algorithms

James Aspnes. Competitive analysis of distributed algorithms. Invited survey paper, Dagstuhl-Seminar on On-line Algorithms, Schloss Dagstuhl, June 23–28, 1996. In Amos Fiat, Gerhard Woeginger, eds., Online Algorithms: The State of the Art, Lecture Notes in Computer Science 1442, Springer-Verlag, 1998, pp. 118–146.

Abstract

Most applications of competitive analysis have involved on-line problems where a candidate on-line algorithm must compete on some input sequence against an optimal off-line algorithm that can in effect predict future inputs. Efforts to apply competitive analysis to fault-tolerant distributed algorithms require accounting for not only this input nondeterminism but also system nondeterminism that arises in distributed systems prone to asynchrony and failures. This paper surveys recent efforts to adapt competitive analysis to distributed systems, and suggests how these adaptations might in turn be useful in analyzing a wider variety of systems. These include tools for building competitive algorithms by composition, and for obtaining more meaningful competitive ratios by limiting the knowledge of the off-line algorithm.

Full version: PDF.

BibTeX

Download
@incollection(Aspnes1998competitive,
title="Competitive analysis of distributed algorithms",
author="James Aspnes",
booktitle="Online Algorithms: The State of the Art",
editor="Amos Fiat and Gerhard Woeginger",
series={Lecture Notes in Computer Science},
volume=1442,
publisher="Springer-Verlag",
year=1998,
pages={118--146}
)

Compositional competitiveness for distributed algorithms

James Aspnes and Orli Waarts. Compositional competitiveness for distributed algorithms. Journal of Algorithms 54(2):127–151, February 2005. Available as arXiv:cs.DS/0306044. An earlier version appeared in Twenty-Eighth Annual ACM Symposium on Theory of Computing, May 1996, pp. 237–246, under the title “Modular competitiveness for distributed algorithms.” A brief announcement of this work appeared in Fourteenth Annual ACM Symposium on Principles of Distributed Computing, August 1995, p. 252, under the title “A modular measure of competitive performance for distributed algorithms.”

Abstract

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 complements the latency measure of Ajtai et al., which measures how quickly an algorithm can finish tasks that start at specified times. The novel feature of the throughput measure, which distinguishes it from the latency measure, is that it is compositional: it supports a notion of algorithms that are competitive relative to a class of subroutines, with the property that an algorithm that is k-competitive relative to a class of subroutines, combined with an l-competitive member of that class, gives a combined algorithm that is kl-competitive.

In particular, we prove the throughput-competitiveness of a class of algorithms for collect operations, in which each of a group of n processes obtains all values stored in an array of n registers. Collects are a fundamental building block of a wide variety of shared-memory distributed algorithms, and we show that several such algorithms are competitive relative to collects. Inserting a competitive collect in these algorithms gives the first examples of competitive distributed algorithms obtained by composition using a general construction.

BibTeX

Download
@article(AspnesW2005compositional,
title="Compositional competitiveness for distributed algorithms",
author="James Aspnes and Orli Waarts",
journal={Journal of Algorithms},
volume=54,
number=2,
pages={127--151},
month=feb,
year=2005
)

Spreading rumors rapidly despite an adversary

James Aspnes and William Hurwood. Spreading rumors rapidly despite an adversary. Journal of Algorithms 26(2):386–411, February 1998. An earlier version appeared in Fifteenth Annual ACM Symposium on Principles of Distributed Computing, May 1996, pp. 143–151.

Abstract

In the collect problem, 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³ n) total read and write operations with high probability, even if timing is under the control of a content-oblivious adversary (a slight weakening of the usual adaptive adversary). This improves on both the trivial upper bound of O(n²) steps and the best previously known bound of O(n3/2 log n) steps, and is close to the lower bound of Ω(n log n) steps. Furthermore, we show how this algorithm can be used to obtain a multi-use cooperative collect protocol that is O(log³ n)-competitive in the latency model of Ajtai et al and O(n1/2) log3/2 n)-competitive in the throughput model of Aspnes and Waarts; in both cases we show that the competitive ratios are within a polylogarithmic factor of optimal.

BibTeX

Download
@article(AspnesH1998,
title="Spreading rumors rapidly despite an adversary",
author="James Aspnes and William Hurwood",
journal={Journal of Algorithms},
volume=26,
number=2,
pages={386--411},
month=feb,
year=1998
)

Fairness in scheduling

Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, and Orli Waarts. Fairness in scheduling. Journal of Algorithms 29(2):306–357, November, 1998. (SODA 1995 special issue.) An earlier version appeared in Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1995, pp. 477–485.

Abstract

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 living processes which should be repeatedly scheduled for various tasks throughout the lifetime of a system. For any such instance we develop a notion of desired load of a process, which is a function of the tasks it participates in. The unfairness of a system is the maximum, taken over all processes, of the difference between the desired load and the actual load.

An example of such a setting is the carpool problem suggested by Fagin and Williams. In this problem, a set of n people form a carpool. On each day a subset of the people arrive and one of them is designated as the driver. A scheduling rule is required so that the driver will be determined in a “fair” way.

We investigate this problem under various assumptions on the input distribution. We also show that the carpool problems can capture several other problems of fairness in scheduling.

BibTeX

Download
@article(AjtaiANRSW1998,
title="Fairness in scheduling",
author="Miklos Ajtai and James Aspnes and Moni Naor and Yuval Rabani and Leonard J. Schulman and Orli Waarts",
journal={Journal of Algorithms},
volume=29,
number=2,
pages={306--357},
month=nov,
year=1998
)

A theory of competitive analysis for distributed algorithms

Miklos Ajtai, James Aspnes, Cynthia Dwork, and Orli Waarts. A theory of competitive analysis for distributed algorithms. Thirty-Fifth IEEE Symposium on Foundations of Computer Science, November 1994, pp. 401–411. A brief announcement of this work appeared in Thirteenth ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1994, under the title “Competitive analysis for distributed algorithms.”

Abstract

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, and of Awerbuch, Kutten, and Peleg, in the context of data management and job scheduling. In these papers, as well as in other subsequent work, the cost of a distributed algorithm is compared to the cost of an optimal global-control algorithm. Here we introduce a more refined notion of competitiveness for distributed algorithms, one that reflects the performance of distributed algorithms more accurately. In particular, our theory allows one to compare the cost of a distributed on-line algorithm to the cost of an optimal distributed algorithm.

We demonstrate our method by studying the cooperative collect primitive, first abstracted by Saks, Shavit, and Woll. We present two algorithms (with different strengths) for this primitive, and provide a competitive analysis for each one.

BibTeX

Download
@inproceedings(AjtaiADW1994,
title="A theory of competitive analysis for distributed algorithms",
author="Miklos Ajtai and James Aspnes and Cynthia Dwork and Orli Waarts",
booktitle="Thirty-Fifth IEEE Symposium on Foundations of Computer Science",
month=nov,
year=1994,
pages={401--411}
)

On-line routing of virtual circuits with applications to load balancing and machine scheduling

James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the Association for Computing Machinery 44(3):486–504, May 1997. An earlier version appeared in Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 1993, pp. 623–631, under the title “On-line load balancing with applications to machine scheduling and virtual circuit routing.”

Abstract

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 bandwidth. We concentrate on the case of permanent virtual circuits (i.e., once a circuit is established, it exists forever), and describe an algorithm that achieves an O(log n) competitive ratio with respect to maximum congestion, where n is the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O(log n) factor. We also show that this result is tight, i.e. for any on-line algorithm there exists a scenario in which Ω(log n) increase in bandwidth is necessary in directed networks.

We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases this machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load.

For the related machines case, we describe the first algorithm that achieves constant competitive ratio. For the unrelated case (with n machines), we describe a new method that yields O(log n)-competitive algorithm. This stands in contrast to the natural greedy approach, whose competitive ratio is exactly n.

BibTeX

Download
@article(AspnesAFPW1993,
title="On-line routing of virtual circuits with applications to load balancing and machine scheduling",
author="James Aspnes and Yossi Azar and Amos Fiat and Serge Plotkin and Orli Waarts",
journal=jacm,
volume=44,
number=3,
pages={486--504},
month=may,
year=1997
)

Randomized consensus in expected O(n log² n) operations per processor

James Aspnes and Orli Waarts. Randomized consensus in expected O(n log² n) operations per processor. SIAM Journal on Computing 25(5):1024–1044, October 1996. An earlier version appeared in Thirty-Third IEEE Symposium on Foundations of Computer Science, October 1992, pp. 137–146.

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 algorithm requires a processor to perform an expected O(n² log n) read and write operations in the worst case. In our algorithm, each processor executes at most an expected O(n log² n) read and write operations, which is close to the trivial lower bound of Ω(n).

All previously known polynomial-time consensus algorithms were structured around a shared coin protocol in which each processor repeatedly adds random ±1 votes to a common pool. Consequently, in all of these protocols, the worst case expected bound on the number of read and write operations done by a single processor is asymptotically no better than the bound on the total number of read and write operations done by all of the processors together. We succeed in breaking this tradition by allowing the processors to cast votes of increasing weights. This grants the adversary greater control since he can choose from up to n different weights (one for each processor) when determining the weight of the next vote to be cast. We prove that our shared coin protocol is correct nevertheless using martingale arguments.

BibTeX

Download
@article(AspnesW1996,
title="Randomized consensus in expected $O(n \log^2 n)$ operations per processor",
author="James Aspnes and Orli Waarts",
journal=sicomp,
volume=25,
number=5,
pages={1024--1044},
month=oct,
year=1996
)

Wait-Free Consensus

James Aspnes. Wait-Free Consensus. PhD thesis, Carnegie-Mellon University, 1992. Available as CMU-CS-TR-92-164.

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 processors must agree on that common value; this is the validity condition. A consensus protocol is wait-free if every processor finishes in a finite number of its own steps regardless of the relative speeds of the other processors, a condition that precludes the use of traditional synchronization techniques such as critical sections, locking, or leader election. Wait-free consensus is fundamental to synchronization without mutual exclusion, as it can be used to construct wait-free implementations of arbitrary concurrent data structures. It is known that no deterministic algorithm for wait-free consensus is possible, although many randomized algorithms have been proposed.

I present two algorithms for solving the wait-free consensus problem in the standard asynchronous shared-memory model. The first is a very simple protocol based on a random walk. The second is a protocol based on weighted voting, in which each processor executes O(n log² n) expected operations. This bound is close to the trivial lower bound of Ω(n), and it substantially improves on the best previously-known bound of O(n² log n), due to Bracha and Rachman.

BibTeX

Download
@phdthesis(Aspnes1992,
title="Wait-Free Consensus",
author="James Aspnes",
school="Carnegie-Mellon University",
year=1992
)

Counting networks

James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks. Journal of the Association for Computing Machinery 41(5):1020–1048, September 1994. An earlier version appeared in Twenty-Third Annual ACM Symposium on Theory of Computing, May 1991, pp. 348–358, under the title “Counting networks and multiprocessor coordination.”

Abstract

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 destinations on an interconnection network. Conventional solutions to these problems perform poorly because of synchronization bottlenecks and high memory contention.

Motivated by observations on the behavior of sorting networks, we offer a new approach to solving such problems, by introducing counting networks, a new class of networks that can be used to count. We give two counting network constructions, one of depth log n (1 + log n) / 2 using n log n (1 + log n) / 4 “gates” and a second of depth log² n, using n log² n / 2 gates. These networks avoid the sequential bottlenecks inherent to earlier solutions, and substantially lower the memory contention.

Finally, to show that counting networks are not merely mathematical creatures, we provide experimental evidence that they outperform conventional synchronization techniques under a variety of circumstances.

BibTeX

Download
@article(AspnesHS1994,
title="Counting networks",
author="James Aspnes and Maurice Herlihy and Nir Shavit",
journal=jacm,
volume=41,
number=5,
pages={1020--1048},
month=sep,
year=1994
)

The expressive power of voting polynomials

James Aspnes, Richard Beigel, Merrick Furst, and Steven Rudich. The expressive power of voting polynomials. Combinatorica 14(2):1–14, 1994. An earlier version appeared in Twenty-Third Annual ACM Symposium on Theory of Computing, May 1991, pp. 402–409.

Abstract

We consider the problem of approximating a Boolean function f: {0,1}n → {0,1} 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 p(x) ≥ 0, f(x) = 1, and whenever p(x)<0, f(x) = 0. A low-degree polynomial p is a good approximator for f if it predicts f at almost all points. Given a positive integer k, and a Boolean function f, we ask, “how good is the best degree k approximation to f?” We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the case f is parity. Minsky and Papert proved that a perceptron can not compute parity; our bounds indicate exactly how well a perceptron can approximate it. As a consequence, we are able to give the first correct proof that, for a random oracle A, PPA is properly contained in PSPACEA. We are also able to prove the old AC0 exponential-size lower bounds in a new way. This allows us to prove the new result that an AC0 circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials.

BibTeX

Download
@article(AspnesBFR1994,
title="The expressive power of voting polynomials",
author="James Aspnes and Richard Beigel and Merrick Furst and Steven Rudich",
journal="Combinatorica",
volume=14,
number=2,
pages={1--14},
year=1994
)

Fast randomized consensus using shared memory

James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms 11(3):441–461, September 1990.

Abstract

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 exponential expected running time. Our algorithm is polynomial, requiring an expected O(n4) operations. Applications of this algorithm include the elimination of critical sections from concurrent data structures and the construction of asymptotically unbiased shared coins.

BibTeX

Download
@article(AspnesH1990consensus,
title="Fast randomized consensus using shared memory",
author="James Aspnes and Maurice Herlihy",
journal={Journal of Algorithms},
volume=11,
number=3,
pages={441--461},
month=sep,
year=1990
)

Time- and space-efficient randomized consensus

James Aspnes. Time- and space-efficient randomized consensus. Journal of Algorithms 14(3):414–431, May 1993. An earlier version appeared in Ninth ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1990, pp. 325–331.

Abstract

A protocol is presented which solves the randomized consensus problem for shared memory. The protocol uses a total of O(p² + n) worst-case expected increment, decrement and read operations on a set of three shared O(log n)-bit counters, where p is the number of active processors and n is the total number of processors. It requires less space than previous polynomial-time consensus protocols, and is faster when not all of the processors participate in the protocol. A modified version of the protocol yields a weak shared coin whose bias is guaranteed to be in the range 1/2 ± epsilon regardless of scheduler behavior, and which is the first such protocol for the shared-memory model to guarantee that all processors agree on the outcome of the coin.

BibTeX

Download
@article(Aspnes1993,
title="Time- and space-efficient randomized consensus",
author="James Aspnes",
journal={Journal of Algorithms},
volume=14,
number=3,
pages={414--431},
month=may,
year=1993
)

Wait-free data structures in the asynchronous PRAM model

James Aspnes and Maurice Herlihy. Wait-free data structures in the asynchronous PRAM model. Second Annual ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 340–349.

Abstract

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, highly concurrent data structures. An implementation of a concurrent object is wait-free if every operation will complete in a finite number of steps, and it is k-bounded wait-free, for some k > 0, if every operation will complete within k steps. In the first part of this paper, we show that there are objects with wait-free implementations but no k-bounded wait-free implementations for any k, and that there is an infinite hierarchy of objects with implementations that are k-bounded wait-free but not K-bounded wait-free for some K > k. In the second part of the paper, we give an algebraic characterization of a large class of objects that do have wait-free implementations in asynchronous PRAM, as well as a general algorithm for implementing them. Our tools include simple iterative algorithms for wait-free approximate agreement and atomic snapshot.

BibTeX

Download
@inproceedings(AspnesH1990waitfree,
title="Wait-free data structures in the asynchronous {PRAM} model",
author="James Aspnes and Maurice Herlihy",
booktitle="Second Annual ACM Symposium on Parallel Algorithms and Architectures",
month=jul,
year=1990,
pages={340--349}
)

A theory of timestamp-based concurrency control for nested transactions

James Aspnes, Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. A theory of timestamp-based concurrency control for nested transactions. Fourteenth International Conference on Very Large Databases, August 1988, pp. 431–444.

Abstract

We present a rigorous framework for analyzing timestamp-based concurrency control and recovery algorithms for nested transactions. We define a local correctness property, local static atomicity, that affords useful modularity. We show that local static atomicity of each object is sufficient to ensure global serializability. We present generalizations of algorithms due to Reed and Herlihy, and show that each ensures local static atomicity.

BibTeX

Download
@inproceedings(AspnesFLMW1988,
title="A theory of timestamp-based concurrency control for nested transactions",
author="James Aspnes and Alan Fekete and Nancy Lynch and Michael Merritt and William Weihl",
booktitle="Fourteenth International Conference on Very Large Databases",
month=aug,
year=1988,
pages={431--444}
)


james.aspnes@gmail.com