Vita for James Aspnes

James Aspnes

Work address

Yale University
Department of Computer Science
51 Prospect Street
P.O. Box 208285
New Haven, CT 06520-8285
USA
email: james.aspnes@gmail.com

Home address

39 Willow Rd
Guilford, CT 06437-1723

Degrees

PhD (CS) 1992, Carnegie-Mellon University.
SM (EECS) 1987, Massachusetts Institute of Technology.
SB (Math) 1987, Massachusetts Institute of Technology.

Experience

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–2021; Harold W. Cheel Professor of Computer Science, 2021–.
IBM Almaden Research Center. Visiting Scientist, 1992–1993.

Honors

ACM-EATCS Dijkstra Prize in Distributed Computing, 2020.
The Dylan Hixon '88 Prize for Teaching Excellence in the Natural Sciences. Awarded by Yale College, 2000.
IBM Graduate Fellowship, 1991–1992.
NSF Graduate Fellowship, 1987–1990.
Phi Beta Kappa, 1987.

Grants

NSF award CCF-1650596, 2016–2020. (PI, $265,044.)
NSF award CCF-1637385, 2016–2019. (Co-PI, $600,000.)
NSF award CCF-0916389, 2009–2013. (Co-PI, $500,000.)
NSF award CNS-0435201, 2004–2008. (Co-PI, $349,987.)
NSF award CNS-0305258, 2003–2006. (PI, $300,000.)
NSF award CCR-0098078, 2001–2004. (PI, $200,940.)
NSF award CCR-9820888, 1999–2002. (PI, $131,264.)
NSF award CCR-9415410, 1995–1997. (Co-PI, $122,318.)
NSF award CCR-9410228, 1994–1998. (PI, $78,568.)

Professional activities

Editorial board member: Algorithmica, 2004–2022; Distributed Computing, 2008–; SIAM Journal on Computing, 2011–2020.
Program committee chair: PODC 2005, DCOSS 2007.
Program committee co-chair: OPODIS 2017, SAND 2022.
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, OPODIS 2019, DISC 2020, SSS 2020, ICDCN 2021, PODC 2021, ICDCN 2022, PODC 2022, PODC 2023, IPDPS 2023.
Steering committee member: PODC, 2004–2007. OPODIS, 2017–2019. SAND, 2021–2024.
Advisory committee member: Collaborative Research Group on Algorithmic Theory of Networks, Pacific Institute for the Mathematical Sciences, 2012–2015.

Memberships

Association for Computing Machinery, SIGACT.

Publications

Also available as a BibTex file.

Privacy in population protocols with probabilistic scheduling, with Talley Amir. Stabilization, Safety, and Security of Distributed Systems (SSS 2023), October 2023, pp. 400–413. [PDF][bib]
Fast convergence of k-undecided state dynamics in the population protocol model, with Talley Amir, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. 2023 ACM Symposium on Principles of Distributed Computing, June 2023, pp. 13–23. Submitted to Distributed Computing (PODC 2022 special issue). [PDF][bib]
Approximate majority with catalyic inputs, with Talley Amir and John Lazarsfeld. 24th International Conference on Principles of Distributed Systems (OPODIS 2020), December 2020, pp. 19:1–19:16. Available as arXiv:2003.09532 [cs.DC]. [PDF][bib]
Message complexity of population protocols, with Talley Amir, David Doty, Mahsa Eftekhari H., and Eric Severson. 34th International Symposium on Distributed Computing (DISC 2020), pp. 6:1–6:18. Available as arXiv:2003.09532 [cs.DC]. [PDF][bib]
Consensus with max registers, with He Yang Er. 32nd International Symposium on Distributed Computing (DISC 2019), October 2019, pp. 1:1–1:19. [PDF][bib]
Why extension-based proofs fail, with Dan Alistarh, Faith Ellen, Rati Gelashvili, and Leqi Zhu. SIAM Journal on Computing 52(4):913–944, 2023. An earlier version appeared in 51st Annual ACM SIGACT Symposium on Theory of Computing, June 2019, pp. 986–996. [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. IEEE/ACM Transactions on Networking, 29(2):571–584, April 2021. An earlier version appeared in Thirty-Third AAAI Conference on Artificial Intelligence, January 2019, pp. 1674–1681. [PDF][bib]
Allocate-on-use space complexity of shared-memory 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 high-level programs on low-level datapaths, with Christopher Leet, Xin Wang, Y. Richard Yang, and Changjun Jiang. IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, April 2018. [PDF][bib]
Space-optimal majority in population protocols, with Dan Alistarh and Rati Gelashvili. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), January 2018, pp. 2221–2239. [PDF][bib]
Clocked population protocols. Journal of Computing and System Sciences 121:34–48, 2021. An earlier version appeared in ACM Symposium on Principles of Distributed Computing (PODC 2017), July 2017, pp. 431–440. [PDF][bib]
Time-space trade-offs in population protocols, with Dan Alistarh, David Eisenstat, Rati Gelashvili, and Ronald Rivest. Proceedings of the Twenty-Eighth Annual ACM-SIAM 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/TR-1527, August 2016. [PDF][bib]
Concurrent use of write-once memory, with Keren Censor-Hillel 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]
Communication-efficient 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 ACM-SIAM Symposium on Discrete Algorithms, January 2014, pp. 416–435. [PDF][bib]
Atomic snapshots in expected O(log³ n) steps using randomized helping, with Keren Censor-Hillel. 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. There is an important erratum for the proceedings 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 Twenty-Third International Converence on Algorithmic Learning Theory, October 2012, pp. 111–123. [PDF][bib]
A one-bit swap object using test-and-sets and a max register. Available as YALEU/DCS/TR-1464, October 2012. [PDF][bib]
Tight bounds for asynchronous renaming, with Dan Alistarh, Keren Censor-Hillel, 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]
Limited-use atomic snapshots with polylogarithmic step complexity, with Hagit Attiya, Keren Censor-Hillel, 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 restricted-use objects, with Hagit Attiya, Keren Censor-Hillel, and Danny Hendler. SIAM Journal on Computing 45(3):734–762, 2016. An earlier version appeared in Twenty-Fourth 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. Fifty-Second Annual IEEE Symposium on Foundations of Computer Science, October 2011, pp. 718–727. [PDF][bib]
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. [PDF][bib]
Sub-logarithmic test-and-set against a weak adversary, with Dan Alistarh. Distributed Computing: 25th International Symposium, DISC 2011. Lecture Notes in Computer Science 6950, Springer-Verlag, September 2011, pp. 97–109. [PDF][bib]
Optimal-time adaptive tight renaming, with applications to counting, with Dan Alistarh, Keren Censor-Hillel, Seth Gilbert, and Morteza Zadimoghaddam. Thirtieth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, June 2011, pp. 239–248. [PDF][bib]
Tight bounds for adopt-commit objects, with Faith Ellen. Theory of Computing Systems 55(3):451-474. (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.” [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, Springer-Verlag, May 2011, pp. 92–104. [PDF][bib]
Slightly smaller splitter networks. Available as YALEU/DCS/TR-1438, 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, Springer-Verlag, 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 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.) [PDF][bib]
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. [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, Springer-Verlag, 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 Twenty-Second 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 Censor-Hillel. 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.” [PDF][bib]
Approximate shared-memory 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 ACM-SIAM 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, Springer-Verlag, 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 Twenty-Seventh 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 Twenty-First 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 ACM-SIAM Symposium on Discrete Algorithms, January 2008, pp. 1066–1075. [PDF][bib]
O(log n)-time overlay network construction from graphs with out-degree 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. Springer-Verlag, December 2007, pp. 286–300. [PDF][bib]
Worm versus alert: Who wins in a battle for control of a large-scale 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. Springer-Verlag, 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., Springer-Verlag, 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 large-alphabet 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]
Path-independent load balancing with unreliable machines, with Yang Richard Yang and Yitong Yin. Eighteenth Annual ACM-SIAM 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/TR-1332, May 2006. [PDF][bib]
Stably computable predicates are semilinear, with Dana Angluin and David Eisenstat. Twenty-Fifth 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 Thirty-Eighth Annual ACM Symposium on Theory of Computing, May 2006, pp. 584–593. [PDF][bib]
On the power of anonymous one-way 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]
Self-stabilizing 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 B-trees, 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, Springer-Verlag, December 2005, pp. 253–272. Available as YALEU/DCS/TR-1326, December 2005. [PDF][bib]
Distributed data structures for P2P systems, with Gauri Shah. Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, Jie Wu, editor, CRC Press, 2005, pages 685–700. [bib]
Exposing computationally-challenged Byzantine impostors, with Collin Jackson and Arvind Krishnamurthy. Available as YALEU/DCS/TR-1332, 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, Springer-Verlag, June 2005, pp. 63–74. [PDF][bib]
Inoculation strategies for victims of viruses and the sum-of-squares 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 ACM-SIAM Symposium on Discrete Algorithms, January 2005, pp. 43–52. Available as YALEU/DCS/TR-1295, 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, Springer-Verlag, September 2004, pp. 177–192. [PDF][bib]
Computation in networks of passively mobile finite-state sensors, with Dana Angluin, Zoë Diamadi, Michael J. Fischer, and René Peralta. Distributed Computing 18(4):235–253, March 2006. (PODC 2004 special issue.) Awarded the 2020 ACM-EATCS Dijkstra Prize in Distributed Computing. An earlier version appeared in Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, July 2004, pp. 290–299. [PDF][bib]
Load balancing and locality in range-queriable data structures, with Jonathan Kirsch and Arvind Krishnamurthy. Twenty-Third 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, Springer-Verlag, 2004, pp. 32–44. Available as YALEU/DCS/TR-1282, April 2004. [PDF][bib]
Urn automata, with Dana Angluin, Zoë Diamadi, Michael J. Fischer, and René Peralta. Available as YALEU/DCS/TR-1280, 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 Large-Scale-Network 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 ACM-SIAM Symposium on Discrete Algorithms, January 2003, pp. 384–393. Available as arXiv:cs.DS/0306043. [PDF][bib]
Fault-tolerant routing in peer-to-peer systems, with Zoë Diamadi and Gauri Shah. Twenty-First ACM Symposium on Principles of Distributed Computing, July 2002, pp. 223–232. Available as arXiv:cs.DS/0302022. [PDF][bib]
Wait-free consensus with infinite arrivals, with Gauri Shah and Jatin Shah. Thirty-Fourth Annual ACM Symposium on Theory of Computing, May 2002, pp. 524–533. [PDF][bib]
Opportunity-cost algorithms for combinatorial auctions, with Karhan Akcoglu, Bhaskar DasGupta, and Ming-Yang Kao. 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. [PDF][bib]
A combinatorial toolbox for protein sequence design and landscape analysis in the Grand Canonical model, with Julia Hartling, Ming-Yang 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, Ming-Yang Kao, and Alok Kumar. Twelfth Annual ACM-SIAM 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 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. [PDF][bib]
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. [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 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.” [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 ACM-SIAM 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. 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.” [PDF][bib]
On-line 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 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.” [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 Thirty-Third IEEE Symposium on Foundations of Computer Science, October 1992, pp. 137–146. [PDF][bib]
Wait-Free Consensus. PhD thesis, Carnegie-Mellon University, 1992. Available as CMU-CS-TR-92-164. [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 Twenty-Third 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 Twenty-Third 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 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. [PDF][bib]
Wait-free 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 timestamp-based 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 November 1st, 2023

james.aspnes@gmail.com