4 papers
Obfuscated Consensus
James Aspnes, Shlomi Dolev, Amit Hendin
The classic Fischer, Lynch, and Paterson impossibility proof demonstrates that any deterministic protocol for consensus in either a message-passing or shared-memory system must vio…
Stochastic well-structured transition systems
James Aspnes
Extending well-structured transition systems to incorporate a probabilistic scheduling rule, we define a new class of stochastic well-structured transition systems that includes po…
Notes on Randomized Algorithms
James Aspnes
Lecture notes for the Yale Computer Science course CPSC 4690/5690 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergrad…
Stably computable relations and predicates
James Aspnes
A population protocol stably computes a relation R(x,y) if its output always stabilizes and R(x,y) holds if and only if y is a possible output for input x. Alternatively, a populat…