Nancy A. Lynch

Orcid: 0000-0003-3045-265X

Affiliations:
  • Massachusetts Institute of Technology (MIT), Computer Science and Artificial Intelligence Laboratory (CSAIL)


According to our database1, Nancy A. Lynch authored at least 318 papers between 1973 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of three.

Awards

ACM Fellow

ACM Fellow 1997, "For contributions to the theory of distributed computing, including mathematical models and proof techniques, algorithms and impossiblity results.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Swarm Algorithms for Dynamic Task Allocation in Unknown Environments.
CoRR, 2024

Using Single-Neuron Representations for Hierarchical Concepts as Abstractions of Multi-Neuron Representations.
CoRR, 2024

Parallel Algorithms for Exact Enumeration of Deep Neural Network Activation Regions.
CoRR, 2024

Multi-Neuron Representations of Hierarchical Concepts in Spiking Neural Networks.
CoRR, 2024

2023
Learning Hierarchically-Structured Concepts II: Overlapping Concepts, and Networks with Feedback.
Proceedings of the Structural Information and Communication Complexity, 2023

A Comparison of New Swarm Task Allocation Algorithms in Unknown Environments with Varying Task Density.
Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

ParSwarm: A C++ Framework for Evaluating Distributed Algorithms for Robot Swarms.
Proceedings of the 5th workshop on Advanced tools, 2023

2022
A superconducting nanowire-based architecture for neuromorphic computing.
Neuromorph. Comput. Eng., June, 2022

Ares: Adaptive, Reconfigurable, Erasure coded, Atomic Storage.
ACM Trans. Storage, 2022

The Power of Population Effect in <i>Temnothorax</i> Ant House-Hunting: A Computational Modeling Approach.
J. Comput. Biol., 2022

An Upper and Lower Bound for the Convergence Time of House-Hunting in <i>Temnothorax</i> Ant Colonies.
J. Comput. Biol., 2022

Emergence of Direction-Selective Retinal Cell Types in Task-Optimized Deep Learning Models.
J. Comput. Biol., 2022

Symbolic Knowledge Structures and Intuitive Knowledge Structures.
CoRR, 2022

A Basic Compositional Model for Spiking Neural Networks.
Proceedings of the A Journey from Process Algebra via Timed Automata to Model Learning, 2022

A Geometry-Sensitive Quorum Sensing Algorithm for the Best-of-N Site Selection Problem.
Proceedings of the Swarm Intelligence - 13th International Conference, 2022

2021
Learning hierarchically-structured concepts.
Neural Networks, 2021

A Spatially Dependent Probabilistic Model for House Hunting in Ant Colonies.
CoRR, 2021

Lack of Quorum Sensing Leads to Failure of Consensus in Temnothorax Ant Emigration.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2021

SNOW Revisited: Understanding When Ideal READ Transactions Are Possible.
Proceedings of the 35th IEEE International Parallel and Distributed Processing Symposium, 2021

2020
Leader election in SINR model with arbitrary power control.
Theor. Comput. Sci., 2020

On simple back-off in unreliable radio networks.
Theor. Comput. Sci., 2020

A superconducting nanowire spiking element for neural networks.
CoRR, 2020

Self-Stabilizing Task Allocation In Spite of Noise.
Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

How to Color a French Flag - Biologically Inspired Algorithms for Scale-Invariant Patterning.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019
Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory.
Proc. ACM Meas. Anal. Comput. Syst., 2019

Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits.
Neural Comput., 2019

How to Color a French Flag-Biologically Inspired Algorithms for Scale-Invariant Patterning.
CoRR, 2019

Winner-Take-All Computation in Spiking Neural Networks.
CoRR, 2019

Integrating Temporal Information to Spatial Information in a Neural Circuit.
CoRR, 2019

Brief Announcement: Integrating Temporal Information to Spatial Information in a Neural Circuit.
Proceedings of the 33rd International Symposium on Distributed Computing, 2019

2019 Principles of Distributed Computing Doctoral Dissertation Award.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Fast Lean Erasure-Coded Atomic Memory Object.
Proceedings of the 23rd International Conference on Principles of Distributed Systems, 2019

ARES: Adaptive, Reconfigurable, Erasure Coded, Atomic Storage.
Proceedings of the 39th IEEE International Conference on Distributed Computing Systems, 2019

2018
Task-structured probabilistic I/O automata.
J. Comput. Syst. Sci., 2018

The SNOW Theorem Revisited.
CoRR, 2018

On Simple Back-Off in Complicated Radio Networks.
CoRR, 2018

Collaboratively Learning the Best Option, Using Bounded Memory.
CoRR, 2018

Brief Announcement: On Simple Back-Off in Unreliable Radio Networks.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

2017
Ant-inspired density estimation via random walks.
Proc. Natl. Acad. Sci. USA, 2017

Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems.
PLoS Comput. Biol., 2017

Searching without communicating: tradeoffs between performance and selection complexity.
Distributed Comput., 2017

A coded shared atomic memory algorithm for message passing architectures.
Distributed Comput., 2017

Beeping a Maximal Independent Set Fast.
CoRR, 2017

Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

An Efficient Communication Abstraction for Dense Wireless Networks.
Proceedings of the 31st International Symposium on Distributed Computing, 2017

Ant-Inspired Dynamic Task Allocation via Gossiping.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2017

A Layered Architecture for Erasure-Coded Consistent Distributed Storage.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016
Dynamic input/output automata: A formal and compositional model for dynamic systems.
Inf. Comput., 2016

Ant-Inspired Density Estimation via Random Walks: Extended Abstract.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

RADON: Repairable Atomic Data Object in Networks.
Proceedings of the 20th International Conference on Principles of Distributed Systems, 2016

Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems.
Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium, 2016

2015
Bounded-Contention Coding for the additive network model.
Distributed Comput., 2015

Consensus using Asynchronous Failure Detectors.
CoRR, 2015

Computing in Additive Networks with Bounded-Information Codes.
Proceedings of the Distributed Computing - 29th International Symposium, 2015

A (Truly) Local Broadcast Layer for Unreliable Radio Networks.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

A Local Broadcast Layer for the SINR Network Model.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Distributed House-Hunting in Ant Colonies.
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

2014
Structuring unreliable radio networks.
Distributed Comput., 2014

Decomposing broadcast algorithms using abstract MAC layers.
Ad Hoc Networks, 2014

Task Allocation in Ant Colonies.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Trade-offs between selection complexity and performance when searching the plane without communication.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Multi-message broadcast with abstract MAC layers and unreliable links.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013
Special issue on DISC 2010.
Distributed Comput., 2013

Athena lecture: distributed computing theory for wireless networks and mobile systems.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

The cost of radio network broadcast for different models of unreliable links.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Timed and Probabilistic I/O Automata.
Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

2012
Leader election using loneliness detection.
Distributed Comput., 2012

Perspectives on the CAP Theorem.
Computer, 2012

Bounds on Contention Management in Radio Networks.
Proceedings of the Distributed Computing - 26th International Symposium, 2012

Bounded-Contention Coding for Wireless Networks in the High SNR Regime.
Proceedings of the Distributed Computing - 26th International Symposium, 2012

Asynchronous failure detectors.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Asynchronous leader election and MIS using abstract MAC layer.
Proceedings of the FOMC'12, 2012

2011
The impossibility of boosting distributed service resilience.
Inf. Comput., 2011

Modeling radio networks.
Distributed Comput., 2011

The abstract MAC layer.
Distributed Comput., 2011

Environment Characterization for Non-recontaminating Frontier-Based Robotic Exploration.
Proceedings of the Agents in Principle, Agents in Practice - 14th International Conference, 2011

Partial reversal acyclicity.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Engineering the Virtual Node Layer for Reactive MANET Routing.
Proceedings of The Tenth IEEE International Symposium on Networking Computing and Applications, 2011

MAC design for analog network coding.
Proceedings of the FOMC'11, 2011

2010
The Theory of Timed I/O Automata, Second Edition
Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, ISBN: 978-3-031-02003-2, 2010

Rambo: a robust, reconfigurable atomic memory service for dynamic networks.
Distributed Comput., 2010

Distributed computation in dynamic networks.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Broadcasting in unreliable radio networks.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Reliably Detecting Connectivity Using Local Graph Traits.
Proceedings of the Principles of Distributed Systems - 14th International Conference, 2010

Automated Formal Verification of the DHCP Failover Protocol Using Timeout Order Abstraction.
Proceedings of the 15th IEEE International Conference on Engineering of Complex Computer Systems, 2010

2009
Self-stabilizing robot formations over unreliable networks.
ACM Trans. Auton. Adapt. Syst., 2009

Automated implementation of complex distributed algorithms specified in the IOA language.
Int. J. Softw. Tools Technol. Transf., 2009

On the weakest failure detector ever.
Distributed Comput., 2009

Keeping Mobile Robot Swarms Connected.
Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Reliable distributed computing on unreliable radio channels.
Proceedings of the 2009 MobiHoc S³ workshop on MobiHoc S³, 2009

Brief announcement: hardness of broadcasting in wireless networks with unreliable communication.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

Brief announcement: minimum spanning trees and cone-based topology control.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

Simulating Fixed Virtual Nodes for Adapting Wireline Protocols to MANET.
Proceedings of The Eighth IEEE International Symposium on Networking Computing and Applications, 2009

Neighbor discovery in mobile ad hoc networks using an abstract MAC layer.
Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008
Verifying average dwell time of hybrid systems.
ACM Trans. Embed. Comput. Syst., 2008

A general characterization of indulgence.
ACM Trans. Auton. Adapt. Syst., 2008

Modeling Computational Security in Long-Lived Systems, Version 2.
IACR Cryptol. ePrint Arch., 2008

Analyzing Security Protocols Using Time-Bounded Task-PIOAs.
Discret. Event Dyn. Syst., 2008

Consensus and collision detectors in radio networks.
Distributed Comput., 2008

Specifying and proving properties of timed I/O automata using Tempo.
Des. Autom. Embed. Syst., 2008

Self-stabilizing Mobile Robot Formations with Virtual Nodes.
Proceedings of the Stabilization, 2008

Connectivity Service for Mobile Ad-Hoc Networks.
Proceedings of the Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems, 2008

Virtual infrastructure for collision-prone wireless networks.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

2007
The virtual node layer: a programming abstraction for wireless sensor networks.
SIGBED Rev., 2007

Observing Branching Structure through Probabilistic Contexts.
SIAM J. Comput., 2007

On the Role of Scheduling in Simulation-Based Security.
IACR Cryptol. ePrint Arch., 2007

Modeling Computational Security in Long-Lived Systems.
IACR Cryptol. ePrint Arch., 2007

DISC 20th Anniversary: Invited Talk My Early Days in Distributed Computing Theory: 1979-1982.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Distributed computing theory: algorithms, impossibility results, models, and proofs.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Self-stabilization and Virtual Node Layer Emulations.
Proceedings of the Stabilization, 2007

A Virtual Node-Based Tracking Algorithm for Mobile Networks.
Proceedings of the 27th IEEE International Conference on Distributed Computing Systems (ICDCS 2007), 2007

Safety Verification of an Aircraft Landing Protocol: A Refinement Approach.
Proceedings of the Hybrid Systems: Computation and Control, 10th International Workshop, 2007

Trace-Based Semantics for Probabilistic Timed I/O Automata.
Proceedings of the Hybrid Systems: Computation and Control, 10th International Workshop, 2007

The DHCP Failover Protocol: A Formal Perspective.
Proceedings of the Formal Techniques for Networked and Distributed Systems, 2007

Compositional Security for Task-PIOAs.
Proceedings of the 20th IEEE Computer Security Foundations Symposium, 2007

2006
The Theory of Timed I/O Automata
Synthesis Lectures on Computer Science, Morgan & Claypool Publishers, 2006

Switched PIOA: Parallel composition via distributed scheduling.
Theor. Comput. Sci., 2006

Proving Approximate Implementations for Probabilistic I/O Automata.
Proceedings of the Combined Proceedings of the Fourth Workshop on Pragmatics of Decision Procedures in Automated Reasoning (PDPAR 2006) and the First International Workshop on Probabilistic Automata and Logics (PaUL 2006), 2006

Testing Self-Similar Networks.
Proceedings of the Second Workshop on Model Based Testing, 2006

Gradient clock synchronization.
Distributed Comput., 2006

Time-Bounded Task-PIOAs: A Framework for Analyzing Security Protocols.
Proceedings of the Distributed Computing, 20th International Symposium, 2006

An Omega (<i>n</i> log <i>n</i>) lower bound on the cost of mutual exclusion.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Specifying and proving properties of timed I/O automata in the TIOA toolkit.
Proceedings of the 4th ACM & IEEE International Conference on Formal Methods and Models for Co-Design (MEMOCODE 2006), 2006

Verifying Average Dwell Time by Solving Optimization Problems.
Proceedings of the Hybrid Systems: Computation and Control, 9th International Workshop, 2006

Proving Safety Properties of an Aircraft Landing Protocol Using I/O Automata and the PVS Theorem Prover: A Case Study.
Proceedings of the FM 2006: Formal Methods, 2006

2005
Using Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol.
IACR Cryptol. ePrint Arch., 2005

GeoQuorums: implementing atomic memory in mobile <i>ad hoc</i> networks.
Distributed Comput., 2005

Proving Atomicity: An Assertional Approach.
Proceedings of the Distributed Computing, 19th International Conference, 2005

Self-stabilizing Mobile Node Location Management and Message Routing.
Proceedings of the Self-Stabilizing Systems, 2005

Brief announcement: virtual stationary automata for mobile networks.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Timed Virtual Stationary Automata for Mobile Networks.
Proceedings of the Principles of Distributed Systems, 9th International Conference, 2005

Reconciling the Theory and Practice of (Un)Reliable Wireless Broadcast.
Proceedings of the 25th International Conference on Distributed Computing Systems Workshops (ICDCS 2005 Workshops), 2005

Translating Timed I/O Automata Specifications for Theorem Proving in PVS.
Proceedings of the Formal Modeling and Analysis of Timed Systems, 2005

Motion Coordination using Virtual Nodes.
Proceedings of the 44th IEEE IEEE Conference on Decision and Control and 8th European Control Conference Control, 2005

2004
Using simulated execution in verifying distributed algorithms.
Int. J. Softw. Tools Technol. Transf., 2004

Virtual Mobile Nodes for Mobile Ad Hoc Networks.
Proceedings of the Distributed Computing, 18th International Conference, 2004

Brief announcement: virtual mobile nodes for mobile ad hoc networks.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Brief announcement: STALK: a self-stabilizing hierarchical tracking service for sensor networks.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Clock Synchronization for Wireless Networks.
Proceedings of the Principles of Distributed Systems, 8th International Conference, 2004

A Hierarchy-Based Fault-Local Stabilizing Algorithm for Tracking in Sensor Networks.
Proceedings of the Principles of Distributed Systems, 8th International Conference, 2004

Compiling IOA without Global Synchronization.
Proceedings of the 3rd IEEE International Symposium on Network Computing and Applications (NCA 2004), 30 August, 2004

Switched Probabilistic I/O Automata.
Proceedings of the Theoretical Aspects of Computing, 2004

Decomposing Verification of Timed I/O Automata.
Proceedings of the Formal Techniques, 2004

2003
Hybrid I/O automata.
Inf. Comput., 2003

Some perspectives on PODC.
Distributed Comput., 2003

Efficient Replication of Large Data Objects.
Proceedings of the Distributed Computing, 17th International Conference, 2003

Timed I/O Automata: A Mathematical Framework for Modeling and Analyzing Real-Time Systems.
Proceedings of the 24th IEEE Real-Time Systems Symposium (RTSS 2003), 2003

Working with mike on distributed computing theory, 1978--1992.
Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

Brief announcement: efficient replication of large data objects.
Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, 2003

Safety Verification of Model Helicopter Controller Using Hybrid Input/Output Automata.
Proceedings of the Hybrid Systems: Computation and Control, 2003

RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks.
Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN 2003), 2003

Compositionality for Probabilistic Automata.
Proceedings of the CONCUR 2003, 2003

Input/Output Automata: Basic, Timed, Hybrid, Probabilistic, Dynamic, ...
Proceedings of the CONCUR 2003, 2003

Communication and Data Sharing for Dynamic Distributed Systems.
Proceedings of the Future Directions in Distributed Computing, 2003

2002
An inheritance-based technique for building simulation proofs incrementally.
ACM Trans. Softw. Eng. Methodol., 2002

Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services.
SIGACT News, 2002

RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks.
Proceedings of the Distributed Computing, 16th International Conference, 2002

Early-Delivery Dynamic Atomic Broadcast.
Proceedings of the Distributed Computing, 16th International Conference, 2002

Atomic Data Access in Distributed Hash Tables.
Proceedings of the Peer-to-Peer Systems, First International Workshop, 2002

A Formal Venture into Reliable Multicast Territory.
Proceedings of the Formal Techniques for Networked and Distributed Systems, 2002

Mechanical Translation of I/O Automaton Specifications into First-Order Logic.
Proceedings of the Formal Techniques for Networked and Distributed Systems, 2002

2001
Specifying and using a partitionable group communication service.
ACM Trans. Comput. Syst., 2001

The BG distributed simulation algorithm.
Distributed Comput., 2001

Implementing atomic objects in a dynamic environment.
Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Dynamic input/output automata, a formal model for dynamic systems.
Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Hybrid I/O Automata Revisited.
Proceedings of the Hybrid Systems: Computation and Control, 4th International Workshop, 2001

2000
Revisiting the PAXOS algorithm.
Theor. Comput. Sci., 2000

High-level modeling and analysis of the traffic alert and collision avoidance system (TCAS).
Proc. IEEE, 2000

Tight bounds for <i>k</i>-set agreement.
J. ACM, 2000

Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study.
Distributed Comput., 2000

Totally Ordered Multicast with Bounded Delays and Variable Rates.
Proceedings of the Procedings of the 4th International Conference on Principles of Distributed Systems, 2000

On Formal Modeling of Agent Computations.
Proceedings of the Formal Approaches to Agent-Based Systems, First International Workshop, 2000

1999
Timing Conditions for Linearizability in Uniform Counting Networks.
Theor. Comput. Sci., 1999

Eventually-Serializable Data Services.
Theor. Comput. Sci., 1999

NSF workshop on a software research program for the 21st century.
ACM SIGSOFT Softw. Eng. Notes, 1999

A Dynamic Primary Configuration Group Communication Service.
Proceedings of the Distributed Computing, 1999

Specifications and Proofs for Ensemble Layers.
Proceedings of the Tools and Algorithms for Construction and Analysis of Systems, 1999

High-Level Modeling and Analysis of TCAS.
Proceedings of the 20th IEEE Real-Time Systems Symposium, 1999

High-Level Modeling and Analysis of an Air-Traffic Management System (Abstract).
Proceedings of the Hybrid Systems: Computation and Control, Second International Workshop, 1999

I/O Automaton Models and Proofs for Shared-Key Communication Systems.
Proceedings of the 12th IEEE Computer Security Foundations Workshop, 1999

1998
Implementing Sequentially Consistent Shared Objects using Broadcast and Point-to-Point Communication.
J. ACM, 1998

Liveness in Timed and Untimed Systems.
Inf. Comput., 1998

Multicast Group Communication as a Base for a Load-Balancing Replicated Data Service.
Proceedings of the Distributed Computing, 12th International Symposium, 1998

A Proof of Burns <i>N</i>-Process Mutual Exclusion Algorithm Using Abstraction.
Proceedings of the Tools and Algorithms for Construction and Analysis of Systems, 1998

A Dynamic View-Oriented Group Communication Service.
Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

Strings of Vehicles: Modeling and Safety Conditions.
Proceedings of the Hybrid Systems: Computation and Control, First International Workshop, 1998

Formal Verification of Safety-Critical Hybrid Systems.
Proceedings of the Hybrid Systems: Computation and Control, First International Workshop, 1998

Proving Correctness of a Controller Algorithm for the RAID Level 5 System.
Proceedings of the Digest of Papers: FTCS-28, 1998

1997
Verification of the Randomized Consensus Algorithms of Aspnes and Herlihy: A Case Study.
Proceedings of the Distributed Algorithms, 11th International Workshop, 1997

In Memory of Anna Pogosyants.
Proceedings of the Distributed Algorithms, 11th International Workshop, 1997

Safety Verification for Automated Platoon Maneuvers: A Case Study.
Proceedings of the Hybrid and Real-Time Systems, 1997

Robust Emulation of Shared Memory Using Dynamic Quorum-Acknowledged Broadcasts.
Proceedings of the Digest of Papers: FTCS-27, 1997

1996
A Tradeoff Between Safety and Liveness for Randomized Coordinated Attack.
Inf. Comput., 1996

Forward and Backward Simulations, II: Timing-Based Systems.
Inf. Comput., 1996

Action Transducers and Timed Automata.
Formal Aspects Comput., 1996

Correctness of vehicle control systems-a case study.
Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), 1996

Counting Networks are Practically Linearizable.
Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

On the Borowsky-Gafni Simulation Algorithm (Abstract).
Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

On the Borowsky-Gafni Simulation Algorithm.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

A Toolbox for Proving and Maintaining Hybrid Specifications.
Proceedings of the Hybrid Systems IV, 1996

Computer-Assisted Verification of an Algorithm for Concurrent Timestamps.
Proceedings of the Formal Description Techniques IX: Theory, 1996

Distributed Algorithms
Morgan Kaufmann, ISBN: 1-55860-348-4, 1996

1995
Forward and Backward Simulations: I. Untimed Systems
Inf. Comput., September, 1995

Hybrid Atomicity for Nested Transactions.
Theor. Comput. Sci., 1995

Probabilistic Simulations for Probabilistic Processes.
Nord. J. Comput., 1995

A Comparison of Simulation Techniques and Algebraic Tachniques for Verifying Concurrent Systems.
Formal Aspects Comput., 1995

Trade-offs between Message Delivery and Quiesce Times in Conection Management Protocols (Preliminary Report).
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Verification of Automated Vehicle Protection Systems.
Proceedings of the Hybrid Systems III: Verification and Control, 1995

Hybrid I/O Automata.
Proceedings of the Hybrid Systems III: Verification and Control, 1995

Modelling and Verification of Automated Transit Systems, Using Timed Automata, Invariants and Simulations.
Proceedings of the Hybrid Systems III: Verification and Control, 1995

Proving Safety Properties of the Steam Boiler Controller.
Proceedings of the Formal Methods for Industrial Applications, 1995

A Tight Lower Bound for Processor Coordination.
Proceedings of the Responsive Computer Systems: Steps Toward Fault-Tolerant Real-Time Systems, 1995

1994
Time Bounds for Real-Time Process Control in the Presence of Timing Uncertainty
Inf. Comput., April, 1994

Quorum Consensus in Nested Transaction Systems.
ACM Trans. Database Syst., 1994

Are Wait-Free Algorithms Fast?
J. ACM, 1994

Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty.
J. ACM, 1994

Reliable Communication Over Unreliable Channels.
J. ACM, 1994

Number of faults a system can withstand without repairs.
CoRR, 1994

The Generalized Railroad Crossing: A Case Study in Formal Verification of Real-Time Systems.
Proceedings of the 15th IEEE Real-Time Systems Symposium (RTSS '94), 1994

Proving Time Bounds for Randomized Distributed Algorithms.
Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

Proving performance propterties (even probabilistic ones).
Proceedings of the Formal Description Techniques VII, 1994

Verifying timing properties of concurrent algorithms.
Proceedings of the Formal Description Techniques VII, 1994

Atomic Transactions for Multiprocessor Programming: A Formal Approach.
Proceedings of the Specification of Parallel Algorithms, 1994

1993
Bounds on Shared Memory for Mutual Exclusion
Inf. Comput., December, 1993

The Impossibility of Implementing Reliable Communication in the Face of Crashes.
J. ACM, 1993

A Modular Drinking Philosophers Algorithm.
Distributed Comput., 1993

Simulation Techniques for Proving Properties of Real-Time Systems.
Proceedings of the A Decade of Concurrency, Reflections and Perspectives, 1993

Designing Algorithms for Distributed Systems with Partially Synchronized Clocks.
Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, 1993

Correctness of At-Most-Once Message Delivery Protocols.
Proceedings of the Formal Description Techniques, VI, Proceedings of the IFIP TC6/WG6.1 Sixth International Conference on Formal Description Techniques, 1993

A Tight Lower Bound for k-Set Agreement
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Computer-Assisted Simulation Proofs.
Proceedings of the Computer Aided Verification, 5th International Conference, 1993

Atomic Transactions
Morgan Kaufmann series in data management systems, Morgan Kaufmann, ISBN: 1-55860-104-X, 1993

1992
Optimal Placement of Identical Resources in a Tree
Inf. Comput., January, 1992

On the Correctness of Orphan Management Algorithms.
J. ACM, 1992

Using Mappings to Prove Timing Properties.
Distributed Comput., 1992

Timing-Based Mutual Exclusion.
Proceedings of the Real-Time Systems Symposium, 1992

A Tradeoff Between Safety and Liveness for Randomized Coordinated Attack Protocols.
Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992

Concurrent Timestamping Made Simple.
Proceedings of the Theory of Computing and Systems, 1992

At-Most-Once Message Delivery. A Case Study in Algorithm Verification.
Proceedings of the CONCUR '92, 1992

1991
Forward and Backward Simulations for Timing-Based Systems.
Proceedings of the Real-Time: Theory in Practice, 1991

1990
Commutativity-Based Locking for Nested Transactions.
J. Comput. Syst. Sci., 1990

A Serialization Graph Construction for Nested Transactions.
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1990

Modelling Shared State in a Shared Action Model
Proceedings of the Fifth Annual Symposium on Logic in Computer Science (LICS '90), 1990

Are Wait-Free Algorithms Fast? (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

The Need for Headers: An Impossibility Result for Communication over Unreliable Channels.
Proceedings of the CONCUR '90, 1990

Distributed Computing: Models and Methods.
Proceedings of the Handbook of Theoretical Computer Science, 1990

1989
A Proof of the Kahn Principle for Input/Output Automata
Inf. Comput., July, 1989

Distributed FIFO Allocation of Identical Resources Using Small Shared Space.
ACM Trans. Program. Lang. Syst., 1989

Multivalued Possibilities Mappings.
Proceedings of the Stepwise Refinement of Distributed Systems, 1989

A Hundred Impossibility Proofs for Distributed Computing.
Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989

1988
A New Fault-Tolerance Algorithm for Clock Synchronization
Inf. Comput., April, 1988

Introduction to the Theory of Nested Transactions.
Theor. Comput. Sci., 1988

Consensus in the presence of partial synchrony.
J. ACM, 1988

A Theory of Timestamp-Based Concurrency Control for Nested Transactions.
Proceedings of the Fourteenth International Conference on Very Large Data Bases, August 29, 1988

A Lattice-Structured Proof of a Minimum Spanning.
Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

Data Link Layer: Two Impossibility Results.
Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

A Theory of Atomic Transactions.
Proceedings of the ICDT'88, 2nd International Conference on Database Theory, Bruges, Belgium, August 31, 1988

Reliable Broadcast in Networks with Nonprogrammable Servers.
Proceedings of the 8th International Conference on Distributed Computing Systems, 1988

1987
Discarding Obsolete Information in a Replicated Database System.
IEEE Trans. Software Eng., 1987

Electing a leader in a synchronous ring.
J. ACM, 1987

A Modular Proof of Correctness for a Network Synchronizer (Research Summary).
Proceedings of the Distributed Algorithms, 1987

Nested Transactions and Read/Write Locking.
Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1987

Hierarchical Correctness Proofs for Distributed Algorithms.
Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

1986
Reaching approximate agreement in the presence of faults.
J. ACM, 1986

Probabilistic Analysis of a Network Resource Allocation Algorithm
Inf. Control., 1986

Easy Impossibility Proofs for Distributed Consensus Problems.
Distributed Comput., 1986

Concurrency Control for Resilient Nested Transactions.
Adv. Comput. Res., 1986

Correctness Conditions for Highly Available Replicated Databases.
Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

An Overview of Clock Synchronization.
Proceedings of the Fault-Tolerant Distributed Computing [Asilomar Workshop 1986], 1986

1985
Impossibility of Distributed Consensus with One Faulty Process
J. ACM, April, 1985

1984
An Upper and Lower Bound for Clock Synchronization
Inf. Control., 1984

The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

A New Fault-Tolerant Algorithm for Clock Synchronization.
Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984

Consensus in the Presence of Partial Synchrony (Preliminary Version).
Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984

1983
Efficiency of Synchronous Versus Asynchronous Distributed Systems
J. ACM, July, 1983

Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control.
ACM Trans. Database Syst., 1983

A Technique for Decomposing Algorithms Which Use a Single Shared Variable.
J. Comput. Syst. Sci., 1983

1982
An Efficient Algorithm for Byzantine Agreement without Authentication
Inf. Control., March, 1982

Global States of a Distributed System.
IEEE Trans. Software Eng., 1982

Accessibility of Values as a Determinant of Relative Complexity in Algebras.
J. Comput. Syst. Sci., 1982

Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable.
J. ACM, 1982

A Lower Bound for the Time to Assure Interactive Consistency.
Inf. Process. Lett., 1982

Cryptographic Protocols
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Multilevel Atomicity.
Proceedings of the ACM Symposium on Principles of Database Systems, 1982

1981
On Describing the Behavior and Implementation of Distributed Systems.
Theor. Comput. Sci., 1981

Relative Complexity of Algebras.
Math. Syst. Theory, 1981

Upper Bounds for Static Resource Allocation in a Distributed System.
J. Comput. Syst. Sci., 1981

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.
J. Comput. Syst. Sci., 1981

Efficient Searching Using Partial Ordering.
Inf. Process. Lett., 1981

A Difference in Efficiency between Synchronous and Asynchronous Systems
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Optimal Placement of Identical Resources in a Distributed Network.
Proceedings of the 2nd International Conference on Distributed Computing Systems, 1981

The Design and Analysis of Cryptographic Protocols.
Proceedings of the Advances in Cryptology: A Report on CRYPTO 81, 1981

1980
Relative Complexity of Operations on Numeric and Bit-String Algebras.
Math. Syst. Theory, 1980

Straight-Line Program Length as a Parameter for Complexity Analysis.
J. Comput. Syst. Sci., 1980

Fast Allocation of Nearby Resources in a Distributed System
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
A time-space tradeoff for sorting and related non-oblivious computations.
SIGACT News, 1979

A Difference in Expressive Power Between Flowcharts and Recursion Schemes.
Math. Syst. Theory, 1979

Resource Allocation with Immunity to Limited Process Failure (Preliminary Report)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Log Space Machines with Multiple Oracle Tapes.
Theor. Comput. Sci., 1978

On Structure Preserving Reductions.
SIAM J. Comput., 1978

Straight-Line Program Length as a Parameter for Complexity Measures
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978

1977
Derivation Complexity in Context-Free Grammar Forms.
SIAM J. Comput., 1977

Log Space Recognition and Translation of Parenthesis Languages.
J. ACM, 1977

Efficient Reducibility Between Programming Systems: Preliminary Report
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

1976
Relativization of Questions About Log Space Computability.
Math. Syst. Theory, 1976

Complexity-Class-Encoding Sets.
J. Comput. Syst. Sci., 1976

Size complexity in context-free grammars forms.
J. ACM, 1976

1975
A Comparison of Polynomial Time Reducibilities.
Theor. Comput. Sci., 1975

A quantifier characterization for nondeterministic log space.
SIGACT News, 1975

"Helping": Several Formalizations.
J. Symb. Log., 1975

On Reducibility to Complex or Sparse Sets.
J. ACM, 1975

Comparative Complexity of Grammar Forms
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

1974
Approximations to the Halting Problem.
J. Comput. Syst. Sci., 1974

Comparisons of Polynomial-Time Reducibilities
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973
Sets that Don't Help
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973


  Loading...