Nancy A. Lynch

According to our database1, Nancy A. Lynch
  • authored at least 325 papers between 1973 and 2017.
  • has a "Dijkstra number"2 of two.

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 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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

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

Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks.
CoRR, 2017

A Layered Architecture for Erasure-Coded Consistent Distributed Storage.
CoRR, 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.
CoRR, 2016

Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks.
CoRR, 2016

RADON: Repairable Atomic Data Object in Networks.
CoRR, 2016

Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems.
CoRR, 2016

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation.
CoRR, 2016

Dynamic Input/Output Automata: a Formal and Compositional Model for Dynamic Systems.
CoRR, 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 Computing, 2015

Consensus using Asynchronous Failure Detectors.
CoRR, 2015

A Local Broadcast Layer for the SINR Network Model.
CoRR, 2015

Distributed House-Hunting in Ant Colonies.
CoRR, 2015

Computing in Additive Networks with Bounded-Information Codes.
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 Computing, 2014

Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication.
CoRR, 2014

Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links.
CoRR, 2014

A Coded Shared Atomic Memory Algorithm for Message Passing Architectures.
CoRR, 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

A Coded Shared Atomic Memory Algorithm for Message Passing Architectures.
Proceedings of the 2014 IEEE 13th International Symposium on Network Computing and Applications, 2014

2013
Special issue on DISC 2010.
Distributed Computing, 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 Computing, 2012

Bounded-Contention Coding for Wireless Networks in the High SNR Regime
CoRR, 2012

Bounds on Contention Management in Radio Networks
CoRR, 2012

Perspectives on the CAP Theorem.
IEEE 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 Computing, 2011

The abstract MAC layer.
Distributed Computing, 2011

Leader Election Using Loneliness Detection.
Proceedings of the Distributed Computing - 25th International Symposium, 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

Structuring unreliable radio networks.
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, 2010

Rambo: a robust, reconfigurable atomic memory service for dynamic networks.
Distributed Computing, 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

Decomposing broadcast algorithms using abstract MAC layers.
Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2010

2009
Self-stabilizing robot formations over unreliable networks.
TAAS, 2009

Automated implementation of complex distributed algorithms specified in the IOA language.
STTT, 2009

On the weakest failure detector ever.
Distributed Computing, 2009

The Abstract MAC Layer.
Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Keeping Mobile Robot Swarms Connected.
Proceedings of the Distributed Computing, 23rd International Symposium, 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

Modeling Radio Networks.
Proceedings of the CONCUR 2009 - Concurrency Theory, 20th International Conference, 2009

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

A general characterization of indulgence.
TAAS, 2008

Modeling Computational Security in Long-Lived Systems, Version 2.
IACR Cryptology ePrint Archive, 2008

Analyzing Security Protocols Using Time-Bounded Task-PIOAs.
Discrete Event Dynamic Systems, 2008

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

Specifying and proving properties of timed I/O automata using Tempo.
Design Autom. for Emb. Sys., 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

Modeling Computational Security in Long-Lived Systems.
Proceedings of the Theoretical Foundations of Practical Information Security, 30.11., 2008

Modeling Computational Security in Long-Lived Systems.
Proceedings of the CONCUR 2008 - Concurrency Theory, 19th International Conference, 2008

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

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

On the Role of Scheduling in Simulation-Based Security.
IACR Cryptology ePrint Archive, 2007

Modeling Computational Security in Long-Lived Systems.
IACR Cryptology ePrint Archive, 2007

Proving Approximate Implementations for Probabilistic I/O Automata.
Electr. Notes Theor. Comput. Sci., 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

On the weakest failure detector ever.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 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

Testing Self-Similar Networks.
Electr. Notes Theor. Comput. Sci., 2006

Gradient clock synchronization.
Distributed Computing, 2006

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

A General Characterization of Indulgence.
Proceedings of the Stabilization, 2006

An Omega (n log n) 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 Cryptology ePrint Archive, 2005

GeoQuorums: implementing atomic memory in mobile ad hoc networks.
Distributed Computing, 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

The Impossibility of Boosting Distributed Service Resilience.
Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS 2005), 2005

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

Automated Implementation of Complex Distributed Algorithms Specified in the IOA Language.
Proceedings of the ISCA 18th International Conference on Parallel and Distributed Computing Systems, 2005

2004
Using simulated execution in verifying distributed algorithms.
STTT, 2004

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

Gradient clock synchronization.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 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 Computing, 2003

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

GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks.
Proceedings of the Distributed Computing, 17th International Conference, 2003

Using Simulated Execution in Verifying Distributed Algorithms.
Proceedings of the Verification, 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 Computing, 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

Dynamic Input/Output Automata: A Formal Model for Dynamic Systems.
Proceedings of the CONCUR 2001, 2001

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

Tight bounds for k-set agreement.
J. ACM, 2000

Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study.
Distributed Computing, 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

An inheritance-based technique for building simulation proofs incrementally.
Proceedings of the 22nd International Conference on on Software Engineering, 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 Software Engineering 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 N-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
Revisiting the Paxos Algorithm.
Proceedings of the Distributed Algorithms, 11th International Workshop, 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

Specifying and Using a Partitionable Group Communication Service.
Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, 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 Asp. 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

Eventually-Serializable Data Services.
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 Asp. 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

Implementing Sequentially Consistent Shared Objects Using Broadcast and Point-to-Point Communication.
Proceedings of the 15th International Conference on Distributed Computing Systems, Vancouver, British Columbia, Canada, May 30, 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

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

Proving time bounds for randomized distributed algorithms.
CoRR, 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

Liveness in Timed and Untimed Systems.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 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

Probabilistic Simulations for Probabilistic Processes.
Proceedings of the CONCUR '94, 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 Computing, 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, 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 Computing, 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

Hybrid Atomicity for Nested Transactions.
Proceedings of the Database Theory, 1992

Action Transducers and Timed Automata.
Proceedings of the CONCUR '92, 1992

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

1991
Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 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

Using Mappings to Prove Timing Properties.
Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 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.
Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), 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

Time Bounds for Real-Time Process Control in the Presence of Timing Uncertainty.
Proceedings of the Real-Time Systems Symposium, 1989

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

Commutativity-Based Locking for Nested Transactions.
Proceedings of the Persistent Object 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

Quorum Consensus in Nested Transaction Systems.
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
Information and Control, 1986

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

Concurrency Control for Resilient Nested Transactions.
Advances in Computing Research, 1986

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

Introduction to the Theory of Nested Transactions.
Proceedings of the ICDT'86, 1986

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

Easy Impossibility Proofs for Distributed Consensus Problems.
Proceedings of the Fault-Tolerant Distributed Computing [Asilomar Workshop 1986], 1986

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

Easy Impossibility Proofs for Distributed Consensus Problems.
Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

1984
An Upper and Lower Bound for Clock Synchronization
Information and 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

Reaching Approximate Agreement in the Presence of Faults.
Proceedings of the Third Symposium on Reliability in Distributed Software and Database Systems, 1983

Concurrency Control for Resilient Nested Transactions.
Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1983

Impossibility of Distributed Consensus with One Faulty Process.
Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 1983

1982
An Efficient Algorithm for Byzantine Agreement without Authentication
Information and 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.
Mathematical Systems 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.
Mathematical Systems 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 Difference in Expressive Power Between Flowcharts and Recursion Schemes.
Mathematical Systems Theory, 1979

On Describing the Behavior and Implementation of Distributed Systems.
Proceedings of the Semantics of Concurrent Computation, 1979

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

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines
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.
Mathematical Systems 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

"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...