Michael Merritt is Executive Director of the Cross-Layer Analytics and Design Research Department, responsible for applied research directed at application, network, and infrastructure design and performance with particular emphasis on interactions that cross layers of abstraction and technology. Michael has published over thirty-five research articles, co-authored a book on database concurrency control, holds five patents, and served for many years as an area editor of Distributed Computing and the Journal of the ACM. He is a recognized expert in distributed computing, computer security, and network traffic analysis. He has taught at Georgia Tech, MIT, Stevens Institute of Technology, and Columbia University.

A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in a network after removing k edges is the concatenation of at most k + 1 shortest paths in the original network.

We study wait-free computation using (read/write) shared memory under a range of assumptions on the arrival pattern of processes. We distinguish first between bounded and infinite arrival patterns, and further distinguish these models by restricting the number of arrivals minus departures, the concurrency. Under the condition that no process takes infinitely many steps without terminating, for any finite bound k > 0, we show that bounding concurrency reveals a strict hierarchy of computational models: a model in which concurrency is bounded by k + 1 is strictly weaker than the model in which concurrency is bounded by k, for all k ≱ 1. A model in which concurrency is bounded in each run, but no bound holds for all runs, is shown to be weaker than a k-bounded model for any k. The unbounded model is shown to be weaker still—in this model, finite prefixes of runs have bounded concurrency, but runs are admitted for which no finite bound holds over all prefixes. Hence, as the concurrency grows, the set of solvable problems strictly shrinks. Nevertheless, on the positive side, we demonstrate that many interesting problems (collect, snapshot, renaming) are solvable even in the infinite arrival, unbounded concurrency model.

Article Fast, wait-free (2k-1)-renaming Share on Authors: Yehuda Afek Tel Aviv University, Tel-Aviv, Israel Tel Aviv University, Tel-Aviv, IsraelView Profile , Michael Merritt AT&T Labs, 180 Park Av., Florham Park, NJ AT&T Labs, 180 Park Av., Florham Park, NJView Profile Authors Info & Claims PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computingMay 1999 Pages 105–112https://doi.org/10.1145/301308.301338Online:01 May 1999Publication History 43citation303DownloadsMetricsTotal Citations43Total Downloads303Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Sequentially consistent versus linearizable counting networks Share on Authors: Marios Mavronicolas Department of Computer Science and Engineering, University of Connecticut, Storrs, CT Department of Computer Science and Engineering, University of Connecticut, Storrs, CTView Profile , Michael Merritt AT&T Labs - Research, 180 Park Avenue, Florham Park, NJ AT&T Labs - Research, 180 Park Avenue, Florham Park, NJView Profile , Gadi Taubenfeld The Open University, 16 Klausner St., Tel-Aviv 61392, Israel The Open University, 16 Klausner St., Tel-Aviv 61392, IsraelView Profile Authors Info & Claims PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computingMay 1999 Pages 133–142https://doi.org/10.1145/301308.301342Online:01 May 1999Publication History 5citation224DownloadsMetricsTotal Citations5Total Downloads224Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A secure reliable multicast protocol enables a process to send a message to a group of recipients such that all honest destinations receive the same message, despite the malicious efforts of fewer than a third of them, including the sender. This has been shown to be a useful tool in building secure distributed services, albeit with a cost that typically grows linearly with the size of the system. For very large networks, for which such a cost may be too prohibitive, we present two approaches for bringing the cost down: First, we show a protocol whose cost is on the order of the number of tolerated failures. Secondly, we show how relaxing the consistency requirement to a selected probability level of guarantee can bring down the associated cost to a constant.

We consider the problem of implementing atomic operations on multiple shared memory objects, in systems which directly support only single-object atomic operations.Our motivation is to design algorithms that exhibit both low contention between concurrent operations and a high level of concurrency, by disentangling long chains of conflicting operations.That is, operations that access widely disjoint parts of a data structure, or are widely separated in time, should not interfere with each other.The algorithm reported here extends and is based on the work of Attiya and Dagan [A D96], where a nonblocking solution is presented for two-object atomic operations.For any number, k, we present a wait-free solution for atomically accessing up to k objects.Notions of local contention and local step complexity are defined, and it is shown that the solution has low local contention and local step complexity.Relations between multi-objects and the familiar resource allocation problem are explored-the algorithm presented also provides a solution to the resource allocation problem. Int roduct ionConsider a data structure stored in shared memory and accessed concurrently by n processes.The shared data structure is abstracted w an array of memory locations.To perform its operation, a process needs to get exclusive access to the set of locations necessary to carry out qComputer

Article The power of multi-objects (extended abstract) Share on Authors: Yehuda Afek Computer Science Dept., Tel-Aviv Univ., Israel 69978, and AT&T Bell Labs. Computer Science Dept., Tel-Aviv Univ., Israel 69978, and AT&T Bell Labs.View Profile , Michael Merritt AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Gadi Taubenfeld The Open Univ., 16 Klausner st., P.O.B. 39328, Tel-Aviv 61392, Israel, and AT&T Bell Labs. The Open Univ., 16 Klausner st., P.O.B. 39328, Tel-Aviv 61392, Israel, and AT&T Bell Labs.View Profile Authors Info & Claims PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computingMay 1996 Pages 213–222https://doi.org/10.1145/248052.248096Published:01 May 1996 6citation173DownloadsMetricsTotal Citations6Total Downloads173Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper investigates the effects of the failure of shared objects on distributed systems.First the notion of a faulty shared object is introduced.Then upper and lower bounds on the space complexity of implementing reliable shared objects are provided, Shared object failures are modeled as instantaneous and arbitraty changes to the state of the object.Several constructions of nonfaulty wait-free shared objects from a set of shared objects, some of which may suffer any number of faults, are presented.Three of these constructions are: (1) A reliable atomic read/write register from 20~+ 8 atomic read/write registers ~of which may be faulty, (2) a reliable test& set register for n processes from n + 10 primitive test & set registers, one of which may be faulty, and 3n + 13 reliable atomic registers, and (3) a reliable consensus object from 2f + 1 read-modify-write registers when f of these may be faulty.Using these constructions a universal construction of any linearizable shared object from a set of either A preliminary version of the results presented in this paper appeared in

The I/O automata model of Lynch and Turtle (1987) is summarized and used to formalize several types of system integrity based on the control of transitions to invalid starts. Type-A integrity is exhibited by systems with no invalid initial states and that disallow transitions from valid reachable to invalid states. Type-B integrity is exhibited by systems that disallow externally-controlled transitions from valid reachable to invalid states, Type-C integrity is exhibited by systems that allow locally-controlled or externally-controlled transitions from reachable to invalid states. Strict-B integrity is exhibited by systems that are Type-B but not Type-A. Strict-C integrity is exhibited by systems that are Type-C but not Type-B. Basic results on the closure properties that hold under composition of systems exhibiting these types of integrity are presented in I/O automata-theoretic terms. Specifically, Type-A, Type-B, and Type-C integrity are shown to be composable, whereas Strict-B and Strict-C integrity are shown to not be generally composable. The integrity definitions and compositional results are illustrated using the familiar vending machine example specified as an I/O automaton and composed with a customer environment. The implications of the integrity definitions and compositional results on practical system design are discussed and a research plan for future work is outlined.>

Exponential key exchange may be used to establish secure communications between two parties who do not share a private key. It fails in the presence of an active wiretap, however. Davies and Price suggest the use of Shamir and Rivest's "Interlock Protocol" to surmount this difficulty. The authors demonstrate that an active attacker can, at the cost of a timeout alarm, bypass the passwork exchange, and capture the passwords used. Furthermore, if the attack is from a terminal or workstation attempting to contact a computer, the attacker will have access before any alarm can be sounded.>

This article presents a solution to the first-come, first-enabled ℓ-exclusion problem of Fischer et al. [1979]. Unlike their solution, this solution does not use powerful read-modify-write synchronization primitives and requires only bounded shared memory. Use of the concurrent timestamp system of Dolev and Shavir [1989] is key in solving the problem within bounded shared memory.

The encrypted key exchange (EKE) protocol is augmented so that hosts do not store cleartext passwords. Consequently, adversaries who obtain the one-way encrypted password file may (i) successfully mimic (spoof) the host to the user, and (ii) mount dictionary attacks against the encrypted passwords, but cannot mimic the user to the host. Moreover, the important security properties of EKE are preserved—an active network attacker obtains insufficient information to mount dictionary attacks. Two ways to accomplish this are shown, one using digital signatures and one that relies on a family of commutative one-way functions.

This paper introduces a general formulation of atomic snapshot memory , a shared memory partitioned into words written ( updated ) by individual processes, or instantaneously read ( scanned ) in its entirety. This paper presents three wait-free implementations of atomic snapshot memory. The first implementation in this paper uses unbounded (integer) fields in these registers, and is particularly easy to understand. The second implementation uses bounded registers. Its correctness proof follows the ideas of the unbounded implementation. Both constructions implement a single-writer snapshot memory, in which each word may be updated by only one process, from single-writer, n -reader registers. The third algorithm implements a multi-writer snapshot memory from atomic n -writer, n -reader registers, again echoing key ideas from the earlier constructions. All operations require Θ( n 2 ) reads and writes to the component shared registers in the worst case. — Authors' Abstract

This paper examines cache consistency conditions for multiprocessor shared memory systems. It states and motivates a weaker condition than is normally implemented. An algorithm is presented that exploits the weaker condition to achieve greater concurrency. The algorithm is shown to satisfy the weak consistency condition. Other properties of the algorithm and possible extensions are discussed.

This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simulate reliable shared-memory objects, despite the fact that the available memory objects (e.g. read/write registers, test-and-set registers, read-modify-write registers) may be faulty.

Classic cryptographic protocols based on user-chosen keys allow an attacker to mount password-guessing attacks. A combination of asymmetric (public-key) and symmetric (secret-key) cryptography that allow two parties sharing a common password to exchange confidential and authenticated information over an insecure network is introduced. In particular, a protocol relying on the counter-intuitive motion of using a secret key to encrypt a public key is presented. Such protocols are secure against active attacks, and have the property that the password is protected against offline dictionary attacks.>

Specificationsof shared memories generally assume that processors block, awaiting the response to each memory request, e.g.awaiting the return value for a read operation.On the other hand, studies have shown that substantial performance gain can be obtained by permitting a processor to have multiple memory readslwrites in progress at a time, and indeed high-performance multiprocessors such as the Tera Computer permit such nonblocking memory accesses.Formalizing correctness conditions for nonblocking shared memories requires a generalization of the processorimemory interface to specify accesses to be done concurrently, indicate when an order must be preserved even among concurrently-requested accesses, and permit out-of-order responses to memory requests.This paper provides the first formal definition of such an interface.Sequential consistency and linearizability are defined with respect to this generaf interface, as natural correctness conditions for nonblocking shared memories.Sequential consistency in turn is used in the formal specification of relaxed consistency models on nonblocking shared memories, models that support sequential consistency only for a class of well-behaved (data-race-free or PL) programs.Finally, the framework is illustrated by studying a particular relaxed consistency model, release consistency.Extending the results of a previous paper, we give a formal specification and correctness proof of a release consistent nonblocking shared memory.This work provides new insights into memory systems and programs for nonblocking shared memories, areas that are not well-understood.techniques.We present a formal specification of a nonblockingshared memory, Mwb, and define correctness conditions based on this specification.This requires a generalization of the processor/memory interface in three respects: 1.A processor conveys to the memory which of its accesses can be processed concurrently, *The discussion in Section 5 mentions some alternative uses of the term '(nonblocking" in the literature.

In a distributed system, node failures, network delays, and other unpredictable occurences can result in orphan computations—subcomputations that continue to run but whose results are no longer needed. Several algorithms have been proposed to prevent such computations from seeing inconsistent states of the shared data. In this paper, two such orphan management algorithms are analyzed. The first is an algorithm implemented in the Argus distributed-computing system at MIT, and the second is an algorithm proposed at Carnegie-Mellon. The algorithms are described formally, and complete proofs of their correctness are given. The proofs show that the fundamental concepts underlying the two algorithms are very similar in that each can be regarded as an implementation of the same high-level algorithm. By exploiting properties of information flow within transaction management systems, the algorithms ensure that orphans only see states of the shared data that they could also see if they were not orphans. When the algorithms are used in combination with any correct concurrency control algorithm, they guarantee that all computations, orphan as well as nonorphan, see consistent states of the shared data.

Article Knowledge in shared memory systems (preliminary version) Share on Authors: Michael Merritt L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Gadi Taubenfeld L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium on Principles of distributed computingJuly 1991 Pages 189–200https://doi.org/10.1145/112600.112617Online:01 July 1991Publication History 8citation183DownloadsMetricsTotal Citations8Total Downloads183Last 12 Months5Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Relaxed consistency models such as weak consistency or release consistency may be understood as a contract between programmer and hardware designer, in which this release consistent memory.

An atomic snapshot memory is a shared data structure allowing concurrent processes to store information in a collection of shared registers, all of which may be read in a single atomic scan operation.This paper presents three wait-free implementations of atomic snapshot memory.Two constructions implement wait-free single-writer atomic snapshot memory from wait-free atomic single-writer, n-reader registers.A third construction implements a wait-free n-writer atomic snapshot memory from n-writer, n-reader registers.The first implementation uses unbounded

This paper examines cache consistency conditions (safety conditions) for multiprocessor shared memory systems.It states and motivates a weaker condition than is normally required.An algorithm is presented that exploits the weaker condition to achieve greater concurrency.The paper concludes with a proof that the algorithm satisfies the safety condition.

Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.

We give a clear yet rigorous correctness proof for Moss's algorithm for managing data in a nested transaction system. The algorithm, which is the basis of concurrency control and recovery in the Argus system, uses read- and write-locks and a stack of versions of each object to ensure the serializability and recoverability of transactions accessing the data. Our proof extends earlier work on exclusive locking to prove that Moss's algorithm generates serially correct executions in the presence of concurrency and transaction aborts. The key contribution is the identification of a simple property of cead operations, called transparency, that permits shared locks to be used for read operations.

Article Simple constant-time consensus protocols in realistic failure models (extended abstract) Share on Authors: Benny Chor MIT Cambridge, MA MIT Cambridge, MAView Profile , Michael Merritt AT&T Bell Labs, Murray Hill, NJ and MIT, Cambridge, MA AT&T Bell Labs, Murray Hill, NJ and MIT, Cambridge, MAView Profile , David B. Shmoys Harvard University, Cambridge, MA Harvard University, Cambridge, MAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 152–162https://doi.org/10.1145/323596.323610Online:01 August 1985Publication History 10citation211DownloadsMetricsTotal Citations10Total Downloads211Last 12 Months4Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Easy impossibility proofs for distributed consensus problems Authors: Michael J. Fischer Yale University, New Haven, CT Yale University, New Haven, CTView Profile , Nancy A. Lynch Mass. Inst. of Tech., Cambridge, MA Mass. Inst. of Tech., Cambridge, MAView Profile , Michael Merritt AT&T Bell Labs., Murray Hill, NJ and Mass. Inst. of Tech., Cambridge, MA AT&T Bell Labs., Murray Hill, NJ and Mass. Inst. of Tech., Cambridge, MAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 59–70https://doi.org/10.1145/323596.323602Online:01 August 1985Publication History 47citation743DownloadsMetricsTotal Citations47Total Downloads743Last 12 Months26Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The news media often bombards the public with forecasts of election results. Polls predict, sometimes years in advance; exit polls are more accurate, and unofficial tallies tend to be closer to the final results. If close elections are disputed, it may take the courts weeks to determine the actual outcome of an election. If the election is nearly unanimous, however, a few disputed votes can have no outcome on the final results. The time at which the final results may be known with certainty thus depends upon the accuracy of the forecast (the number of disputed votes), and the closeness of the election.

This paper presents two distributed algorithms for detecting and resolving deadlocks. By insuring that only one of the deadlock processes will detect it, the problem of resolving the deadlock is simplified. That process could simply abort itself. In one version of the algorithm, an arbitrary process detects deadlock; and in a second version, the process with the lowest priority detects deadlock.

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.