Arrow Research search

Author name cluster

Nancy A. Lynch

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

I&C Journal 2016 Journal Article

Dynamic input/output automata: A formal and compositional model for dynamic systems

  • Paul C. Attie
  • Nancy A. Lynch

We present dynamic I/O automata (DIOA), a compositional model of dynamic systems. In DIOA, automata can be created and destroyed dynamically, as computation proceeds, and an automaton can dynamically change its signature, i. e. , the set of actions in which it can participate. DIOA features operators for parallel composition, action hiding, action renaming, a notion of automaton creation, and a notion of behavioral subtyping by means of trace inclusion. DIOA can model mobility, using signature modification, and is hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. We also show that parallel composition, action hiding, action renaming, and (subject to some technical conditions) automaton creation are all monotonic with respect to trace inclusion: if one component is replaced by another whose traces are a subset of the former, then the set of traces of the system as a whole can only be reduced.

Details DOI

I&C Journal 1996 Journal Article

A Tradeoff between Safety and Liveness for Randomized Coordinated Attack

  • George Varghese
  • Nancy A. Lynch

We studyrandomized, synchronousprotocols for coordinated attack. Such protocols trade off the number of rounds (N), the worst-case probability of disagreement (U), and the probability that all generals attack ( L ). We prove a nearly tight bound on the tradeoff between L andU( L /U≤N) for astrongadversary that destroys any subset of messages. Our techniques may be useful for other problems that allow a non-zero probability of disagreement

Details DOI

FOCS Conference 1993 Conference Paper

A Tight Lower Bound for k-Set Agreement

  • Soma Chaudhuri
  • Maurice Herlihy
  • Nancy A. Lynch
  • Mark R. Tuttle

We prove tight bounds on the time needed to solve k-set agreement, a natural generalization of consensus. We analyze this problem in a synchronous, message-passing model where processors fail by crashing. We prove a lower bound of [f/k]+1 rounds of communication for solutions to k-set agreement that tolerate f failures. This bound is tight, and shows that there is an inherent tradeoff between the running time, the degree of coordination required, and the number of faults tolerated, even in idealized models like the synchronous model. The proof of this result is interesting because it is a geometric combination of other well-known proof techniques. >

Details

I&C Journal 1992 Journal Article

Optimal placement of identical resources in a tree

  • Michael J. Fischer
  • Nancy D. Griffeth
  • Leonidas Guibas
  • Nancy A. Lynch

The problem of placing a number t of identical resources at nodes of a tree so as to minimize the total expected cost of servicing a set of t requests arriving randomly at nodes is considered. The cost of servicing a particular set of requests is the total distance in the tree between each request and its assigned resource. Distance is measured by the number of edges along the unique path from the request to the resource. Optimal placements can be found in time O(mt), where m is the number of edges in the tree. Allowing resources to be split into fractional-sized pieces which can be placed separately neither reduces the cost of an optimal placement nor provides an obvious way to find optimal placements significantly faster. Simple, natural “fair” placements whose cost differs from optimality by at most the number of edges in the tree are described. For any fixed tree T, the cost of these placements grows as O( t ), where the constant implicit in the “O” notation depends on the size and shape of T. In the case of balanced trees with k leaves, that constant is at most 2k φ. The placement problem becomes somewhat simpler for a complete (rooted) d-ary tree with a symmetric probability density function for request arrivals, and in that case slightly stronger results are possible. For example, an optimal placement can be found in time O(min{ℓ, log d t} + t), where ℓ is the height of the tree, and the placement is symmetric and fair.

Details DOI

FOCS Conference 1990 Conference Paper

Are Wait-Free Algorithms Fast? (Extended Abstract)

  • Hagit Attiya
  • Nancy A. Lynch
  • Nir Shavit

The time complexity of wait-free algorithms in so-called normal executions, where no failures occur and processes operate at approximately the same speed, is considered. A lower bound of log n on the time complexity of any wait-free algorithm that achieves approximate agreement among n processes is proved. In contrast, there exists a non-wait-free algorithm that solves this problem in constant time. This implies an Omega (log n)-time separation between the wait-free and non-wait-free computation models. An O(log n)-time wait-free approximate agreement algorithm is presented. Its complexity is within a small constant of the lower bound. >

Details

I&C Journal 1989 Journal Article

A proof of the Kahn principle for input/output automata

  • Nancy A. Lynch
  • Eugene W. Stark

We use input/output automata to define a simple and general model of networks of concurrently executing, nondeterministic processes that communicate through unidirectional, named ports. A notion of the input/output relation computed by a process is defined, and determinate processes are defined to be processes whose input/output relations are single-valued. We show that determinate processes compute continuous functions, and that networks of determinate processes obey Kahn's fixed-point principle. Although these results are already known, our contribution lies in the fact that the input/output automata model yields extremely simple proofs of them (the simplest we have seen), in spite of its generality.

Details DOI

STOC Conference 1982 Conference Paper

Cryptographic Protocols

  • Richard A. DeMillo
  • Nancy A. Lynch
  • Michael Merritt

A cryptographic transformation is a mapping f from a set of cleartext messages, M, to a set of ciphertext messages. Since for m e M, f(m) should hide the contents of m from an enemy, f -1 should, in a certain technical sense, be difficult to infer from f(m) and public knowledge about f. A cryptosystem is a model of computation and communication which permits the manipulation of messages by cryptographic transformations.

Details

TCS Journal 1981 Journal Article

On describing the behavior and implementation of distributed systems

  • Nancy A. Lynch
  • Michael J. Fischer

A simple, basic and general model for describing both the (input/output) behavior and the implementation of distributed systems is presented. An important feature is the separation of the machinery used to describe the implementation and the behavior. This feature makes the model potentially useful for design specification of systems and of subsystems. The model's primitivity and generality make it a suitable basis for cost comparison of distributed system implementations.

Details DOI

STOC Conference 1980 Conference Paper

Fast Allocation of Nearby Resources in a Distributed System

  • Nancy A. Lynch

Dijkstra's informally-stated Dining Philosophers problem [D] involves a number n of philosophers sitting in a circle, a single fork between each pair of adjacent philosophers. The problem is to program the philosophers in ways which guarantee certain conditions of fairness and absence of deadlock.

Details

FOCS Conference 1979 Conference Paper

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines

  • Allan Borodin
  • Michael J. Fischer
  • David G. Kirkpatrick
  • Nancy A. Lynch
  • Martin Tompa

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

Details
v2026.09.13