Author name cluster

Michael Merritt

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.

4 papers

2 author rows

I&C Journal 2013 Journal Article

Computing with infinitely many processes

Michael Merritt
Gadi Taubenfeld

We explore four classic problems in concurrent computing (election, mutual exclusion, consensus, and naming) when the number of processes which may participate is unbounded. Partial information about the number of processes actually participating and the concurrency level is shown to affect the computability and complexity of solving these problems when using only atomic registers. We survey and generalize work carried out in models with known bounds on the number of processes, and prove several new results. These include improved bounds for election when participation is required and a new adaptive starvation-free mutual exclusion algorithm for unbounded concurrency. We also survey results in models with shared objects stronger than atomic registers, such as test&set bits, semaphores or read–modify–write registers, and update them for the unbounded case.

Details DOI

I&C Journal 1999 Journal Article

The Power of Multiobjects

Yehuda Afek
Michael Merritt
Gadi Taubenfeld

We consider shared memory systems that support multiobject operations in which processes may simultaneously access several objects in one atomic operation. We provide upper and lower bounds on the synchronization power (consensus number) of multiobject systems as a function of the type and the number of objects that may be simultaneously accessed in one atomic operation. These bounds imply that known classifications of component objects fail to characterize the synchronization power of their combination. In particular, we show that in the context of multiobjects, fetch & add objects are less powerful than swap objects, which in turn are less powerful than queue objects. This stands in contrast to the fact that swap can be implemented from fetch & add. Herein we introduce a restricted notion of implementation, called direct implementation. We show that, if objects of type Y have a direct implementation from objects of type X, then Y-based multiobjects can also be implemented from X-based multiobjects. Using this observation, we derive results such as: there are no direct implementations of swap or queue objects from any collection of commutative objects (e. g. , fetch & add, test & set).

Details DOI

TCS Journal 1986 Journal Article

Introduction to the theory of nested transactions

Nancy Lynch
Michael Merritt

A new formal model is presented for studying concurrency and resiliency properties for nested transactions. The model is used to state and prove correctness of a well-known locking algorithm.

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