James Aspnes
Yale University
Department of Computer Science
51 Prospect Street
P.O. Box 208285
New Haven, CT 065208285
email: james.aspnes@gmail.com
39 Willow Rd
Guilford, CT 064371723

PhD (CS) 1992, CarnegieMellon University.

SM (EECS) 1987, Massachusetts Institute of Technology.

SB (Math) 1987, Massachusetts Institute of Technology.

Yale University.
Assistant Professor of Computer Science, 1993–1998;
Associate Professor of Computer Science (term), 1998–2001;
Associate Professor of Computer Science (tenured), 2001–2005;
Professor of Computer Science, 2005–.

IBM Almaden Research Center. Visiting Scientist, 1992–1993.

NSF award CCF1650596,
2016–2018. (PI, $265,044.)

NSF award CCF1637385,
2016–2019. (CoPI, $600,000.)

NSF award CCF0916389,
2009–2013. (CoPI, $500,000.)

NSF award CNS0435201,
2004–2008. (CoPI, $349,987.)

NSF award CNS0305258,
2003–2006. (PI, $300,000.)

NSF award CCR0098078,
2001–2004. (PI, $200,940.)

NSF award CCR9820888,
1999–2002. (PI, $131,264.)

NSF award CCR9415410,
1995–1997. (CoPI, $122,318.)

NSF award CCR9410228,
1994–1998. (PI, $78,568.)
 Editorial board member:
Algorithmica, 2004–;
Distributed Computing, 2008–;
SIAM Journal on Computing, 2011–2020.

Program committee chair:
PODC 2005,
DCOSS 2007.
OPODIS 2017.

Program committee vice chair:
DCOSS 2006 (Algorithms track).

Program committee member:
PODC 1996,
PODC 1997,
PODC 1999,
FOCS 1999,
FOCS 2001,
PODC 2003,
PODC 2004,
DCOSS 2005,
MPPS 2005,
PODC 2005,
DCOSS 2006,
SSS 2006,
IPTPS 2007,
ICALP 2007,
DCOSS 2007,
DISC 2007,
SSS 2007,
STOC 2008,
DCOSS 2008,
IPDPS 2009,
COCOON 2009,
DCOSS 2009,
DISC 2009,
ALGOSENSORS 2009,
DISC 2009,
SSS 2009,
ICDCS 2010,
SSS 2010,
IPDPS 2011,
PODC 2011,
ICDCN 2012,
SIROCCO 2012,
SSS 2012,
DISC 2012,
OPODIS 2012,
STOC 2013,
ICALP 2013,
PODC 2013,
ICDCS 2013,
ICDCN 2014,
ICDCS 2014,
SSS 2014,
DISC 2014,
ICDCS 2015,
SSS 2015,
SIROCCO 2015,
ICDCN 2016,
PODC 2016,
ICALP 2017,
DISC 2017,
SSS 2018,
SIROCCO 2019,
PODC 2019,
SPAA 2019,
SSS 2019.
 Steering committee member:
PODC, 2004–2007.
 Advisory committee member:
Collaborative Research Group on Algorithmic
Theory of Networks, Pacific Institute for the Mathematical Sciences, 2012–2015.

Association for Computing Machinery, SIGACT.
Also available as a BibTex file.

Why extensionbased proofs fail, with Dan Alistarh, Faith Ellen, Rati Gelashvili, and Leqi Zhu. Accepted to STOC 2019. [PDF][bib]

Optimizing in the dark: Learning an optimal solution through a simple request interface, with Qiao Xiang, Haitao Yu, Franck Le, Linghe Kong, and Y. Richard Yang. To appear, AAAI 2019. [PDF][bib]

Allocateonuse space complexity of sharedmemory algorithms, with Bernhard Haeupler, Alexander Tong, and Philipp Woelfel. 32nd International Symposium on Distributed Computing (DISC 2018), October 2018, pp. 8:1–8:17. [PDF][bib]

Object oriented consensus, with Yehuda Afek, Edo Cohen, and Danny Vainstein. A brief announcement of a preliminary version of this work appeared in ACM Symposium on Principles of Distributed Computing (PODC 2017), July 2017, pp. 367–369. [PDF][bib]

The FuzzyLog: A partially ordered shared log, with Joshua Lockerman, Jose M. Faleiro, Juno Kim, Soham Sankaram, Daniel J. Abadi, Siddhartha Sen, and Mahesh Balakrishnan. 13th USENIX Symposium on Operating Systems Design and Implementation, October 2018, pp. 357–372. [PDF][bib]

Toward the first SDN programming capacity theorem on realizing highlevel programs on lowlevel datapaths, with Christopher Leet, Xin Wang, Y. Richard Yang, and Changjun Jiang. IEEE INFOCOM 2018  IEEE Conference on Computer Communications, April 2018. [PDF][bib]

Spaceoptimal majority in population protocols, with Dan Alistarh and Rati Gelashvili. TwentyNinth Annual ACMSIAM Symposium on Discrete
Algorithms (SODA 2018), January 2018, pp. 2221–2239. [PDF][bib]

Clocked population protocols. ACM Symposium on Principles of Distributed Computing (PODC 2017), July 2017, pp. 431–440. [PDF][bib]

Timespace tradeoffs in population protocols, with Dan Alistarh, David Eisenstat, Rati Gelashvili, and Ronald Rivest. Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, January 2017, pp. 2560–2579. [PDF][bib]

Time and space optimal counting in population protocols, with Joffroy Beauquier, Janna Burman, and Devan Sohier. 20th International Conference on Principles of Distributed Systems,
OPODIS 2016, December 13–16, 2016, Madrid, Spain, December 2016, pp. 13:1–13:17. [PDF][bib]

Depth of a random binary search tree with concurrent insertions, with Eric Ruppert. Distributed Computing  30th International Symposium, {DISC} 2016, Paris, France, September 27–29, 2016. Proceedings, September 2016, pp. 371–384. [PDF][bib]

A population protocol for binary signaling consensus, with Dana Angluin and Dongqu Chen. Available as YALEU/DCS/TR1527, August 2016. [PDF][bib]

Concurrent use of writeonce memory, with Keren CensorHillel and Eitan Yaakobi. Journal of Parallel and Distributed Computing
113:250–260, March 2018.
An earlier version appeared in
Structural Information and Communication Complexity  23rd International
Colloquium, SIROCCO 2016, Helsinki, Finland, July 19–21, 2016, Revised
Selected Papers, July 2016, pp. 127–142. [PDF][bib]

Counting with population protocols, with Yves Mocquard, Emmanuelle Anceaume, Yann Busnel, and Bruno Sericola. 2015 IEEE 14th International Symposium on Network Computing and Applications, September 2015, pp. 35–42. [PDF][bib]

Network construction with subgraph connectivity constraints, with Dana Angluin and Lev Reyzin. Journal of Combinatorial Optimization, 29(2):418–432, February 2015.
[PDF][bib]

Communicationefficient randomized consensus, with Dan Alistarh, Valerie King, and Jared Saia. Distributed Computing, 31(6):489–501, November 2018. An earlier version appeared in Distributed Computing — 28th International Symposium, DISC 2014, Austin, TX, USA, October 12–15, 2014. Proceedings, Lecture Notes in Computer Science 8784, Springer, October 2014, pp. 61–75.
[PDF][bib]

Dynamic task allocation in asynchronous shared memory, with Dan Alistarh, Michael Bender, Rati Gelashvili, and Seth Gilbert. 2014 ACMSIAM Symposium on Discrete Algorithms, January 2014, pp. 416–435.
[PDF][bib]

Atomic snapshots in expected O(log³ n) steps using randomized helping, with Keren CensorHillel. Submitted to Distributed Computing, January 2014. Last revised September 2018. An earlier version appeared in Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 1418, 2013. Proceedings, Lecture Notes in Computer Science 8205, SpringerVerlag, October 2013, pp. 254–268. There is an important erratum for the proceeding version of this paper.
[PDF][bib]

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

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

A onebit swap object using testandsets and a max register. Available as YALEU/DCS/TR1464, October 2012.
[PDF][bib]

Tight bounds for asynchronous renaming, with Dan Alistarh, Keren CensorHillel, Seth Gilbert, and Rachid Guerraoui. Journal of the Association for Computing Machinery, 61(3):18, May 2014.
[PDF][bib]

Faster randomized consensus with an oblivious adversary. Distributed Computing 28(1):21–29, February 2015. (PODC 2012 special issue). An earlier version appeard in 2012 ACM Symposium on Principles of Distributed Computing, July 2012, pp. 1–8. [PDF][bib]

Limiteduse atomic snapshots with polylogarithmic step complexity, with Hagit Attiya, Keren CensorHillel, and Faith Ellen. Journal of the Association for Computing Machinery 62(1):3, February 2015. Erratum. 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)”
. [PDF][bib]

Lower bounds for restricteduse objects, with Hagit Attiya, Keren CensorHillel, and Danny Hendler. SIAM Journal on Computing 45(3):734–762, 2016.
An earlier version appeared in
TwentyFourth ACM Symposium on Parallel Algorithms and Architectures,
July 2012, pp. 172–181.
[PDF][bib]

Randomized load balancing by joining and splitting bins, with Yitong Yin. Information Processing Letters, 112(8–9):309–313, April 2012.
[PDF][bib]

The complexity of renaming, with Dan Alistarh, Seth Gilbert, and Rachid Guerraoui. FiftySecond Annual IEEE Symposium on Foundations of Computer Science, October 2011, pp. 718–727. [PDF][bib]

Randomized consensus in expected O(n²) total work using singlewriter registers. Distributed Computing: 25th International Symposium, DISC 2011.
Lecture Notes in Computer Science 6950,
SpringerVerlag, September 2011, pp. 363–373.
[PDF][bib]

Sublogarithmic testandset against a weak adversary, with Dan Alistarh. Distributed Computing: 25th International Symposium, DISC 2011.
Lecture Notes in Computer Science 6950,
SpringerVerlag, September 2011, pp. 97–109.
[PDF][bib]

Optimaltime adaptive tight renaming, with applications to counting, with Dan Alistarh, Keren CensorHillel, Seth Gilbert, and Morteza Zadimoghaddam. Thirtieth Annual ACM SIGACTSIGOPS Symposium on Principles of
Distributed Computing, June 2011, pp. 239–248.
[PDF][bib]

Tight bounds for adoptcommit objects, with Faith Ellen. Theory of Computing Systems 55(3):451474.
(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 adoptcommit objects.”
[PDF][bib]

Mutation systems, with Dana Angluin and Raonne Barbosa Vargas. 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,
SpringerVerlag, May 2011, pp. 92–104.
[PDF][bib]

Slightly smaller splitter networks. Available as YALEU/DCS/TR1438, November 2010, and as
arXiv:1011.3170.
[PDF][bib]

Inferring social networks from outbreaks, with Dana Angluin and Lev Reyzin. Algorithmic Learning Theory, 21st International Conference, Lecture Notes in Computer Science 6331, SpringerVerlag, October 2010, pp. 104–118.
[PDF][bib]

Effective storage capacity of labeled graphs, with Dana Angluin, Rida A. Bazzi, Jiang Chen, David Eisenstat, and Goran Konjevod. 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
2022, 2010. Proceedings, Lecture Notes in Computer Science, volume 6366,
SpringerVerlag, September 2010, pp. 573–587, under the title
“Storage capacity of labeled graphs.”
(Winner, Best Student Paper award.)
[PDF][bib]

A modular approach to sharedmemory consensus, with applications to the probabilisticwrite model. Distributed Computing 25(2):179–188, May 2012. (PODC 2010 special issue.)
An earlier version appeared in
TwentyNinth Annual ACM SIGACTSIGOPS Symposium on Principles of
Distributed Computing, July 2010, pp. 460–467.
[PDF][bib]

k^{+} decision trees, with Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, and Steve Uurtamo. Sixth International Workshop on Algorithms for Sensor Systems, Revised Selected Papers,
Lecture Notes in Computer Science 6451,
SpringerVerlag, July 2010, pp. 74–88.
[PDF][bib]

Low contention data structures, with David Eisenstat and Yitong Yin. Journal of Parallel and Distributed Computing, 72(5):705–715, May 2012.
An earlier version appeared in
TwentySecond ACM Symposium on Parallelism in Algorithms and
Architectures, June 2010, pp. 345–354.
[PDF][bib]

Combining shared coin algorithms, with Hagit Attiya and Keren Censor. Journal of Parallel and Distributed Computing 70(3):317–322, March 2010.
[PDF][bib]

Polylogarithmic concurrent data structures from monotone circuits, with Hagit Attiya and Keren CensorHillel. Journal of the Association for Computing Machinery,
59(1):2:1–2:24, February 2012.
An earlier version appeared
in
TwentyEighth Annual ACM Symposium on Principles of Distributed Computing, August 2009, pp. 36–45,
under the title
“Max registers, counters, and monotone circuits.”
[PDF][bib]

Approximate sharedmemory counting despite a strong adversary, with Keren Censor. ACM Transactions on Algorithms 6(2):1–23, March 2010 (SODA 2009 special issue).
An earlier version appeared in
Twentieth Annual ACMSIAM Symposium on Discrete Algorithms, January 2009, pp. 441–450.
[PDF][bib]

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

Randomized consensus in expected O(n log n) individual work, with Hagit Attiya and Keren Censor.
In TwentySeventh annual ACM Symposium on Principles of Distributed Computing, August 2008, pp. 325–334.
[PDF][bib]

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

Ranged hash functions and the price of churn, with Muli Safra and Yitong Yin. Nineteenth Annual
ACMSIAM Symposium on Discrete Algorithms, January 2008, pp. 1066–1075.
[PDF][bib]

O(log n)time overlay network construction from graphs with outdegree 1, with Yinghua Wu. Principles of Distributed Systems;
11th International Conference, OPODIS 2007,
Gaudaloupe, French West Indies, December 17–20, 2007, Proceedings.
Lecture Notes in Computer Science 4878.
SpringerVerlag, December 2007, pp. 286–300.
[PDF][bib]

Worm versus alert: Who wins in a battle for control of a largescale network?
, with Navin Rustagi and Jared Saia. Principles of Distributed Systems;
11th International Conference, OPODIS 2007,
Gaudaloupe, French West Indies, December 17–20, 2007, Proceedings.
Lecture Notes in Computer Science 4878.
SpringerVerlag, December 2007, pp. 443–456.
[PDF][bib]

The computational power of population protocols, with Dana Angluin, David Eisenstat, and Eric Ruppert. 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.
[PDF][bib]

An introduction to population protocols, with Eric Ruppert. 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., SpringerVerlag, 2009, pp. 97–120.
[PDF][bib]

A simple population protocol for fast robust approximate majority, with Dana Angluin and David Eisenstat. 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.
[PDF][bib]

Learning largealphabet and analog circuits with value injection queries, with Dana Angluin, Jiang Chen, and Lev Reyzin. 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.
[PDF][bib]

Pathindependent load balancing with unreliable machines, with Yang Richard Yang and Yitong Yin. Eighteenth Annual ACMSIAM Symposium on Discrete Algorithms, January 2007, pp. 814–823.
Available as arXiv:cs.DS/0607026.
[PDF][bib]

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

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

Fast computation by population protocols with a leader, with Dana Angluin and David Eisenstat. 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/TR1332, May 2006.
[PDF][bib]

Stably computable predicates are semilinear, with Dana Angluin and David Eisenstat. TwentyFifth ACM Symposium on Principles of Distributed Computing, July 2006, pp. 292–299.
[PDF][bib]

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

On the power of anonymous oneway communication, with Dana Angluin, David Eisenstat, and Eric Ruppert.
Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 396–411.
[PDF][bib]

Selfstabilizing population protocols, with Dana Angluin, Michael J. Fischer, and Hong Jiang.
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.)
[PDF][bib]

Skip Btrees, with Ittai Abraham and Jian Yuan.
Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 366–380.
[PDF][bib]

Spreading alerts quietly and the subgroup escape problem, with Zoë Diamadi, Kristian Gjøsteen, René Peralta, and Aleksandr Yampolskiy. Journal of Cryptology 28(4):796–819, October 2015. 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,
SpringerVerlag, December 2005, pp. 253–272.
Available as YALEU/DCS/TR1326, December 2005.
[PDF][bib]

Distributed data structures for P2P systems, with Gauri Shah. Theoretical and Algorithmic Aspects of
Sensor, Ad Hoc Wireless and PeertoPeer Networks, Jie Wu, editor,
CRC Press, 2005, pages 685–700.
[bib]

Exposing computationallychallenged Byzantine impostors, with Collin Jackson and Arvind Krishnamurthy. Available as YALEU/DCS/TR1332, July 2005. [PDF][bib]

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

The expansion and mixing time of skip graphs with applications, with Udi Wieder. 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.
[PDF][bib]

Stably computable properties of network graphs, with Dana Angluin, Melody Chan, Michael J. Fischer, Hong Jiang, and René Peralta. 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, SpringerVerlag, June 2005, pp. 63–74.
[PDF][bib]

Inoculation strategies for victims of viruses and the sumofsquares partition problem, with Kevin Chang and Aleksandr Yampolskiy. Journal of Computer and System Sciences,
72(6):1077–1093, September 2006.
An ealier version appeared in
Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms,
January 2005, pp. 43–52.
Available as YALEU/DCS/TR1295, July 2004.
[PDF][bib]

Relationships between broadcast and shared memory in reliable anonymous distributed systems, with Faith Ellen Fich and Eric Ruppert. 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.
[PDF][bib]

Towards a theory of data entanglement, with Joan Feigenbaum, Aleksandr Yampolskiy, and Sheng Zhong. 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,
SpringerVerlag, September 2004, pp. 177–192.
[PDF][bib]

Computation in networks of passively mobile finitestate sensors, with Dana Angluin, Zoë Diamadi, Michael J. Fischer, and René Peralta. Distributed Computing 18(4):235–253, March 2006. (PODC 2004 special issue.)
An earlier version appeared in
TwentyThird Annual ACM SIGACTSIGOPS Symposium on
Principles of Distributed Computing, July 2004, pp. 290–299.
[PDF][bib]

Load balancing and locality in rangequeriable data structures, with Jonathan Kirsch and Arvind Krishnamurthy. TwentyThird ACM Symposium on Principles of Distributed Computing, July 2004, pp. 115–124.
[PDF][bib]

On the computational complexity of sensor network localization, with David Goldenberg and Yang Richard Yang. Algorithmic Aspects of Wireless Sensor Networks: First International
Workshop, ALGOSENSORS 2004, Turku, Finland, July 16,
2004. Proceedings.
Lecture Notes in Computer Science 3121,
SpringerVerlag, 2004, pp. 32–44.
Available as YALEU/DCS/TR1282, April 2004.
[PDF][bib]

Urn automata, with Dana Angluin, Zoë Diamadi, Michael J. Fischer, and René Peralta. Available as YALEU/DCS/TR1280, November 2003. [PDF][bib]

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.
[PDF][bib]

Towards better definitions and measures of Internet security, with Joan Feigenbaum, Michael Mitzenmacher, and David C. Parkes. Workshop on LargeScaleNetwork Security and Deployment Obstacles, Landsdowne VA, March 2003. [PDF][bib]

Skip graphs, with Gauri Shah. ACM Transactions on Algorithms, 3(4):37, November 2007. An earlier version appeared in
Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, January 2003, pp. 384–393.
Available as arXiv:cs.DS/0306043.
[PDF][bib]

Faulttolerant routing in peertopeer systems, with Zoë Diamadi and Gauri Shah. TwentyFirst ACM Symposium on Principles of Distributed Computing, July 2002, pp. 223–232.
Available as arXiv:cs.DS/0302022.
[PDF][bib]

Waitfree consensus with infinite arrivals, with Gauri Shah and Jatin Shah. ThirtyFourth Annual ACM Symposium on Theory of Computing, May
2002, pp. 524–533.
[PDF][bib]

Opportunitycost algorithms for combinatorial auctions, with Karhan Akcoglu, Bhaskar DasGupta, and MingYang Kao.
In
E. J. Kontoghiorghes, B. Rustem, and S. Siokos, eds.,
Applied Optimization 74: Computational Methods in DecisionMaking,
Economics and Finance,
Kluwer Academic Publishers, 2002, pp. 455–479.
An earlier version is available as
DIMACS technical report 200027
and as
arXiv:cs.CE/0010031.
[PDF][bib]

A combinatorial toolbox for protein sequence design and landscape analysis in the Grand Canonical model, with Julia Hartling, MingYang Kao, Junhyong Kim, and Gauri Shah. 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.
[PDF][bib]

Towards understanding the predictability of stock markets from the perspective of computational complexity, with David F. Fischer, Michael J. Fischer, MingYang Kao, and Alok Kumar. Twelfth Annual
ACMSIAM Symposium on Discrete Algorithms, January 2001, pp. 745–754.
Available as arXiv:cs.CE/0010021.
[PDF][bib]

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.
[PDF][bib]

Lower bounds for distributed coinflipping and randomized consensus. Journal of the Association for Computing Machinery
45(3):415–450, May 1998.
An earlier version appeared in
TwentyNinth Annual ACM Symposium on Theory of
Computing, May 1997, pp. 559–568.
[PDF][bib]

Competitive analysis of distributed algorithms.
Invited survey paper, DagstuhlSeminar on Online 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,
SpringerVerlag, 1998, pp. 118–146.
[bib]

Compositional competitiveness for distributed algorithms, with Orli Waarts. Journal of Algorithms 54(2):127–151, February 2005.
Available as arXiv:cs.DS/0306044.
An earlier version appeared in TwentyEighth 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.”
[PDF][bib]

Spreading rumors rapidly despite an adversary, with William Hurwood. 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.
[PDF][bib]

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

A theory of competitive analysis for distributed algorithms, with Miklos Ajtai, Cynthia Dwork, and Orli Waarts. ThirtyFifth
IEEE Symposium on Foundations of Computer Science, November 1994,
pp. 401–411. A brief announcement of this work appeared in
Thirteenth ACM SIGACTSIGOPS Symposium on Principles of
Distributed Computing, August 1994, under the title
“Competitive analysis for distributed algorithms.”
[PDF][bib]

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

Randomized consensus in expected O(n log² n) operations per processor, with Orli Waarts. SIAM Journal on Computing
25(5):1024–1044, October 1996. An earlier version appeared in
ThirtyThird IEEE Symposium on
Foundations of Computer Science, October 1992, pp. 137–146.
[PDF][bib]

WaitFree Consensus.
PhD thesis, CarnegieMellon University, 1992.
Available as CMUCSTR92164.
[PDF][bib]

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

The expressive power of voting polynomials, with Richard Beigel, Merrick Furst, and Steven Rudich. Combinatorica 14(2):1–14, 1994. An earlier version appeared in
TwentyThird Annual ACM Symposium on Theory of Computing,
May 1991, pp. 402–409.
[PDF][bib]

Fast randomized consensus using shared memory, with Maurice Herlihy. Journal of Algorithms 11(3):441–461, September 1990.
[PDF][bib]

Time and spaceefficient randomized consensus. Journal of Algorithms 14(3):414–431, May 1993.
An earlier version appeared in
Ninth ACM SIGACTSIGOPS Symposium on
Principles of Distributed Computing, August 1990, pp. 325–331.
[PDF][bib]

Waitfree data structures in the asynchronous PRAM model, with Maurice Herlihy. Second Annual ACM Symposium on Parallel
Algorithms and Architectures, July 1990, pp. 340–349.
[PDF][bib]

A theory of timestampbased concurrency control for nested transactions, with Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Fourteenth International Conference on Very Large Databases, August 1988, pp. 431–444.
[PDF][bib]
Last updated April 11th, 2019
james.aspnes@gmail.com