A name service maps a name of an individual, organization or facility into a set of labeled properties, each of which is a string. It is the basis for resource location, mail addressing, and authentication in a distributed computing system. The global name service described…
This paper describes a deceptively (almost embarrassingly) simple technique, that of cryptographic capsules, which allows Alice to convince Bob that either X or Y is true without giving Bob any information as to which is the case. Capsules are an instrumental part of the machinery…
We investigate the expressive power of constant-depth polynomial-size circuit models. In particular, we construct a circuit model whose expressive power is precisely that of first-order logic.
In "Crusade for Better Notation" [1], Gilles Brassard calls one-way equations involving big omicron, big omega, etc. "bad, irrational and confusing notation". He promotes the following alternative that seems to him better and more natural: define O(t(n)), Ω (t(n)), etc. as sets and "use them…
We show that almost any non-linear quantifier, applied to quantifier-free first-order formulas, suffices to express an NP- complete predicate; the remaining non-linear quantifiers express exactly co-NL predicates (NL is Nondeterministic Log-space).
This paper describes a design for an authentication service for a very large scale, very long lifetime, distributed system. The paper introduces a methodology for describing authentication protocols that makes explicit the trust relationships amongst the participants. The authentication protocol is based on the primitive…
This paper describes a system which locates and grasps parts from a pile. The system uses photometric stereo and binocu lar stereo as vision input tools. Photometric stereo is used to make surface ...
Over the last several years, teams working on expert systems have been exploring formal approaches for belief revision and information acquisition. The formalization of major components of expert systems operation is useful for understanding and characterizing system behavior and for predicting changes with modification. Formalization…
The advantages of user-defined distfix operators – a syntactic convenience that enhances the readability of programs – can be obtained as an extension of almost any programming language without requiring dynamic changes to the parser.
For some time I had been looking for a mutual exclusion algorithm that satisfied my complete list of desirable properties. I finally found one--the N!-bit algorithm described in this paper. The algorithm is wildly impractical, requiring N! bits of storage for N processors, but practicality…
The paper examines the stability of a model divertor tokamak equilibrium to MHD ballooning and interchange modes. The combined effects of the magnetic separatrix and a finite edge current density can result in coalescence of the first and second stable regions. This leads to a…
We have been working on a design for an authentication service for a distributed system. The design has three goals that we fed have not been met simultaneously by any previous design. First, the service must be able to grow to cover an arbitrarily large…
