Bias-resistant public randomness is a critical component in many (distributed) protocols. Generating public randomness is hard, however, because active adversaries may behave dishonestly to bias public random choices toward their advantage. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.

We propose an efficient remote biometric authentication protocol that gives strong protection to the user’s biometric data in case of two common kinds of security breaches: (1) loss or theft of the user’s token (smart card, handheld device, etc.), giving the attacker full access to any secrets embedded within it; (2) total penetration of the server. Only if both client and server are simultaneously compromised is the user’s biometric data vulnerable to exposure. The protocol works by encrypting the user’s biometric template in a way that allows it to be used for authentication without being decrypted by either token or server. Further, the encrypted template never leaves the token, and only the server has the information that would enable it to be decrypted. We have implemented our protocol using two iris recognition libraries and evaluated its performance. The overall efficiency and recognition performance is essentially the same compared to an unprotected biometric system.

In recent years Google’s MapReduce has emerged as a leading large-scale data processing architecture. Adopted by companies such as Amazon, Facebook, Google, IBM and Yahoo! in daily use, and more recently put in use by several universities, it allows parallel processing of huge volumes of data over cluster of machines. Hadoop is a free Java implementation of MapReduce. In Hadoop, files are split into blocks and replicated and spread over all servers in a network. Each job is also split into many small pieces called tasks. Several tasks are processed on a single server, and a job is not completed until all the assigned tasks are finished. A crucial factor that affects the completion time of a job is the particular assignment of tasks to servers. Given a placement of the input data over servers, one wishes to find the assignment that minimizes the total completion time. In this paper, an idealized Hadoop model is proposed to investigate the Hadoop task assignment problem. It is shown that there is no feasible algorithm to find the optimal Hadoop task assignment unless P = NP. Assignments that are computed by the round robin algorithm inspired by the current Hadoop scheduler are shown to deviate from optimum by a multiplicative factor in the worst case. A flow-based algorithm is presented that computes assignments that are optimal to within an additive constant.

Nancy Lynch has written over 400 scientific papers in a career spanning nearly four decades. She is best known for her seminal and continuing work in theory of distributed computing, a field that did not exist in 1971 when she wrote her first paper. Her first distributed computing paper was presented eight years later after she had already written 21 papers on other topics.

This article studies self-stabilization in networks of anonymous, asynchronously interacting nodes where the size of the network is unknown. Constant-space protocols are given for Dijkstra-style round-robin token circulation, leader election in rings, two-hop coloring in degree-bounded graphs, and establishing consistent global orientation in an undirected ring. A protocol to construct a spanning tree in regular graphs using O (log D ) memory is also given, where D is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.

We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition on interactions, we define the concept of stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all stably computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P ∩ RL. Several open problems and promising future directions are discussed.

No abstract available.

We study a new problem—the wakeup problem—that seems to be fundamental in distributed computing. We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader-election problem, and other related problems. The main question we try to answer is “How much memory is needed to solve the wakeup problem?” We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

Layered communicationprotocols frequently implement a FIFO message fiacility cm top of an unrehable non-FIFO serwce such as that provided hy a packet-swltchmg network.This paper investigates the possibdity of Implementing a reliable message layer on top of an underlying layer that can low packets and deliver them out of order, with the addltlonzd restriction that the implementatmn uses only a fixed fimte number of different packets.A new formalism is presented to spcclfy communication layers and their properties, the notion of their implementation by 1/0 automata.and the properties of such implementations.An 1/0 automaton that Implements a rellable layer over an unreliable layer is presented In this implementation, tbe number ot packets needed to deliver each succeeding message increases permanently as additional packet-loss and reordering faults occur.A proof is gwen that no protocol can avoid such performance degradatmn.

The Fishspear priority queue algorithm is presented and analyzed. Fishspear is comparable to the usual heap algorithm in its worst-case running time, and its relative performance is much better in many common situations. Fishspear also differs from the heap method in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it potentially attractive for implementation of very large queues on paged memory systems.

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{ℓ, logdt} + t), where ℓ is the height of the tree, and the placement is symmetric and fair.

We study a new problem, the wakeup problem, that seems to be very fundamental in distributed computing.We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader election problem, and other related problems.The main question we try to answer is, how much memory is needed to solve the wakeup problem?We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes that communicate via shared memory. The algorithm simulates a shared queue but uses exponentially fewer shared memory values, resulting in practical savings of time and space as well as program complexity. The algorithm is robust against process failure through unannounced stopping, making it attractive also for use in an environment of processes of widely differing speeds. In addition to its practical advantages, we show that for fixed k , the shared space complexity of the algorithm as a function of the number N of processes is optimal to within a constant factor.

This paper describes a cryptographic scheme for holding a secure secret ballot election in which all communication is public. Voters cast their votes electronically, suitably encrypted, and a “government” releases a tally and a proof of its correctness which can be verified by all.

A monotonic priority set is a new data structure which supports maximum-finding and deletions over a set of weighted points in the plane. Global updates to the weights can also be made, incrementing the weights of all points above a given threshold in one of the coordinates. The weights are assumed to be always monotonic in both coordinates. An efficient implementation of this structure is presented and two main applications are described. The first is to the problem of optimal assembly of code for computers with two kinds of jump instruction: long and short. The task in the second application is the implementation of a queuing discipline based on the ranks with respect to two different criteria.

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 consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.

The Fishspear priority queue algorithm is presented and analyzed. Fishspear makes fewer than 80% as many comparisons as heaps in the worst case, and its relative performance is even better in rnany common situations. The code itself embodies an unusual recursive structure which permits highly dynamic and data-dependent execution. Fishspear also differs from heaps in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it possibly attractive for implementation of very large queues on paged memory systems. (Details of the implementation are deferred to the full paper.)

We analyze the problem of constructing a network which will have a fixed routing and which will be highly fault tolerant. A construction is presented which forms a “product route graph” from two or more constituent “route graphs.” The analysis involves the surviving route graph, which consists of all non-faulty nodes in the network with two nodes being connected by a directed edge iff the route from the first to the second is still intact after a set of component failures. The diameter of the surviving route graph, that is, the maximum distance between any pair of nodes, is a measure of the worst-case performance degradation caused by the faults. The number of faults tolerated, the diameter, and the degree of the product graph are related in a simple way to the corresponding parameters of the constituent graphs. In addition, there is a “padding theorem” which allows one to add nodes to a graph and to extend a previous routing.

The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the "Byzantine Generals" problem.

article Free Access Share on Efficiency of Synchronous Versus Asynchronous Distributed Systems Authors: Eshrat Arjomandi Department of Computer Science, York University, Downsview, Ontario, Canada M3J 1P3 Department of Computer Science, York University, Downsview, Ontario, Canada M3J 1P3View Profile , Michael J. Fischer Department of Computer Science, Yale University, P.O. Box 2158, New Haven, CT and University of Washington, Seattle, Washington Department of Computer Science, Yale University, P.O. Box 2158, New Haven, CT and University of Washington, Seattle, WashingtonView Profile , Nancy A. Lynch Laboratory for Computer Science, M.I.T., Cambridge, MA Laboratory for Computer Science, M.I.T., Cambridge, MAView Profile Authors Info & Claims Journal of the ACMVolume 30Issue 3July 1983 pp 449–456https://doi.org/10.1145/2402.322387Published:01 July 1983Publication History 46citation865DownloadsMetricsTotal Citations46Total Downloads865Last 12 Months51Last 6 weeks9 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a simple algorithm for maintaining a replicated distributed dictionary which achieves high availability of data, rapid processing of atomic actions, efficient utilization of storage, and tolerance to node or network failures including lost or duplicated messages. It does not require transaction logs, synchronized clocks, or other complicated mechanisms for its operation. It achieves consistency contraints which are considerably weaker than serial consistency but nonetheless are adequate for many dictionary applications such as electronic appointment calendars and mail systems. The degree of consistency achieved depends on the particular history of operation of the system in a way that is intuitive and easily understood. The algorithm implements a "best effort" approximation to full serial consistency, relative to whatever internode communication has successfully taken place, so the semantics are fully specified even under partial failure of the system. Both the correctness of the algorithm and the utility of such weak semantics depend heavily on special properties of the dictionary operations.

An analysis is made of the shared memory requirements for implementing mutual excluslon of N asynchronous parallel processes m a model where the only primitive communication mechamsm is a general test-and-set operation on a single shared variable.While two variable values suffice to tmplement simple mutual exclusion without deadlock, it is shown that any solution whJch avoids possJble lockout of processes requires at least 2~ + ½ values A technical restnctmn on the model increases this requtrement to N/2 values, while achieving a fixed bound on wamng further increases the reqmrement to N + 1 values.These bounds are shown to be nearly optimal, for algorithms are exhibited for the last two cases which use [N/2J + 9 and N + 3 values, respectively All of the lower bounds apply afortiori to the space requirements for weaker primitives, such as P and V, using busy waiting Categones and Subject Descnptors D 4 1 [Operating Systems]" Process Management--mutual exclusion; D 4 2 [Operating Systems]' Storage Management F ! ![Computation by Abstract Devices]: Models of Computation, F !.2 [Computation by Abstract Devices]" Modes ofComputaUon--parallehsm, F 2 [Theory of Computation] Analysis of Algorithms and Problem Complexity General Terms Algonthms, Performance, Theory

A property of Boolean functions of n variables is described and shown to imply lower bounds as large as $\Omega (n\log n)$ on the number of literals in any Boolean formula for any function with the property. Formulas over the full basis of binary operations $( \wedge , \oplus ,{\text{ etc.}})$ are considered. The lower bounds apply to all but a vanishing fraction of symmetric functions, in particular, to all threshold functions with sufficiently large threshold and to the “congruent to zero modulo k” function for $k > 2$. In the case $k = 4$, the bound is optimal.

A global state of a distributed transaction system is consistent if no transactions are in progress. A global checkpoint is a transaction which must view a globally consistent system state for correct operation. We present an algorithm for adding global checkpoint transactions to an arbitrary distributed transaction system. The algorithm is nonintrusive in the sense that checkpoint transactions do not interfere with ordinary transactions in progress; however, the checkpoint transactions still produce meaningful results.

The University of Washington's Eden project is a five-year research effort to design, build and use an “integrated distributed” computing environment. The underlying philosophy of Eden involves a fresh approach to the tension between these two adjectives. In briefest form, Eden attempts to support both good personal computing and good multi-user integration by combining a node machine / local network hardware base with a software environment that encourages a high degree of sharing and cooperation among its users.

A system of parallel processes is said to be synchronous if all processes run using the same clock, and it is asynchronous if each process has its own independent clock. For any s, n, a particular distributed problem is defined involving system behavior at n “ports”. This problem can be solved in time s by a synchronous system but requires time at least (s-1) log n on any asynchronous system.

We consider the problem of finding a minimal cost layout of a tree in Euclidian d-space. A tree is an acyclic undirected edge-weighted graph, and a layout is an assignment of a point in d-dimensional Euclidian space to each of the nodes of the tree. The “length” of an edge in the layout is the “distance” between its endpoints as measured by some norm. The cost of an edge is its length times its weight, and the cost of the whole layout is the sum of the costs of all the edges. We assume the positions of certain nodes are fixed in advance, and we wish to place the remaining nodes so as to minimize the cost of the layout.

The prefix problem is to compute all the products x t o x2 .... o xk for i ~ k .~n, where o is an associative operation A recurstve construction IS used to obtain a product circuit for solving the prefix problem which has depth exactly [log:n] and size bounded by 4n An application yields fast, small Boolean ctrcmts to simulate fimte-state transducers.By simulating a sequentml adder, a Boolean clrcmt which has depth 2[Iog2n] + 2 and size bounded by 14n Is obtained for n-bit binary addmon The size can be decreased significantly by permitting the depth to increase by an addmve constant KEY WORDS AND PHRASES automaton, binary addmon, clrcmt, combinational complexity, depth, fanout, parallehsm, size, transducer CR CATEGORIES 5.22, 5 25, 6 1, 6 32 X3 o X2.

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.

Upper and lower bounds are proved for the shared space requirements for solution of several problems involving resource allocation among asynchronous processes. Controlling the degradation of performance when a limited number of processes fail is of particular interest.

Various computational models (such as machines and combinational logic networks) induce various and, m general, different computational complexity measures Relations among these measures are established by studying the ways m which one model can "simulate" another It ts shown that a machine with k-dimensional storage tapes (respectively, with tree-structured storage media) can be simulated on-hne by a machine with onedimensional storage tapes m time O(n 2-ilk) (respectively, m time O(n2/log n)) An obhv:ous machine Is defined to be one whose head posmons, as functions of time, are independent of the input, and It Is shown that any machine with one-d~menslonal tapes can be simulated on-hne by an oblivious machine with two one-dimensional tapes in time O(n log n) All of these results are the best possible, at least insofar as on-hne simulation is concerned.By slmdar methods It is shown that n steps of the computation of an arbitrary machine with onedimensional tapes can be performed by a combinational logic network of cost O(n log n) and delay O(n)

AaSTancr.A recurslve padding technique is used to obtain conditions sufficient for separation of nondetermlmsttc multltape Turlng machine time complexity classes If T2 is a running time and Tl(n + 1) grows more slowly than T~(n), then there is a language which can be accepted nondetermmlstlcally within time bound T~ but which cannot be accepted nondetermlnlStlcally within time bound T1.If even T~(n + f(n)) grows more slowly than Tz(n), where f is the very slowly growing "rounded reverse" of some real-time countable function, then there is such a language over a single-letter alphabet.The strongest known dmgonalization results for both deterministic and nondetermlmstlc time complexity classes are reviewed and orgamzed for comparison with the results of the new padding technique KEY WOADS ^NO PHaASrS: Turlng machine, complexity class, complexity hierarchy, time complexity, nondetermmism, padding, recursmn theorem, dmgonahzatmn, single-letter alphabet CR CAa~ORIES 5 23, 5.25, 5.26, 5 27 This paper represents a portion of the first author's Ph D d~ssertatlon [25] written at M.

We introduce a fundamental propositional logical system for describing correctness, termination and equivalence of programs. We define a formal syntax and semantics for the propositional modal logic of programs and give several consequences of the definition. Principal conclusions are that deciding satisfiability requires time dn/log nfor some d > 1 and that satisfiability, even in an extended system, can be decided in nondeterministic time cnfor some c. We provide applications of the decision procedure to regular expressions, Ianov schemes, and classical systems of modal logic.

A solution to the critical section problem, first posed by Dijkstra [1], is a fundamental requirement for concurrent program control. The problem is to ensure that no two processes are in a specified area of their programs (the critical section) at the same time. Improvements to Dijkstra's solution were made by Knuth [2], deBruijn [3], and Eisenberg and McGuire [4]. The situation, for a distributed system was considered by Lamport [5]. Rivest and Pratt [6] presented a solution for a distributed system where processes may repeatedly fail. The algorithms to be presented will be further improvements, where the comparisons will be made according to three measures: message size—the number of values the variable for interprocess communication can take on; fairness—the sequence in which waiting processes enter their critical sections; and time—the amount of time a process spends attempting to enter its critical section.

Let C(n)k be the Boolean function of n variables that equals one iff the number of arguments equal to one is a multiple of k. It is shown that every Boolean expression for C(n)k, allowing all of the 16 binary connectives, has size exceeding εn log n/log log n, ε> 0. This result follows from a general criterion relating the minimum size expression for a Boolean function to the kinds of subfunctions obtainable through restriction. Lower bounds on formula size for several other functions are obtained. In some cases, the lower bounds are nearly achievable by known constructions.

The string-to-string correction problem is to determine the distance between two strings as measured by the minimum cost sequence of “edit operations” needed to change the one string into the other. The edit operations investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string. An algorithm is presented which solves this problem in time proportional to the product of the lengths of the two strings. Possible applications are to the problems of automatic spelling correction and determining the longest subsequence of characters common to two strings.

High level programming languages tend to free a programmer from concern about the underlying machine structure and permit him to talk about his problem domain in more direct terms. Thus, he may imagine that objects such as real numbers, character strings, and linear arrays really exist in the machine as atomic entities and he need not understand the details of how they are actually represented in the machine. Of course what distinguishes various kinds of objects are the operations that may be performed on them, so when talking about the domain of real numbers, we should include the basic arithmetic operations and constants, and for strings, operations such as length, concatenation and indexing.Unfortunately, existing languages do not permit a programmer to ignore completely questions of representation, for if his problem domain does not happen to be included already in the repertoire of domains supported by the language, the programmer must figure out a representation himself and remember it throughout his programming effort. For example, a FORTRAN programmer may know that it is not meaningful to multiply two integers that happen to represent insurance policy numbers, but he has no way of informing the compiler of this fact.Many extensible languages do provide a wide range of data types including structured types, enabling a programmer to choose a more natural representation of his external objects, but the structured data types reflect only the structure of the data, not its meaning. They still provide only one natural representation for both integers and dates, mass and speed, or planar vectors in cartesian or polar coordinates.Many domains that arise in practice have a great deal of similarity between them which one must employ in his programs. For example, the domain of length 3 vectors and the domain of length 4 vectors have the "same" rule of addition, that is, add componentwise, and it would be onerous to have to repeat this information for each new length vector. Thus, one needs both the ability to define brand new domains and also a method for expressing relations among them.We present here some mechanisms, collectively called Aleph-1, which allow the expansion of a programming language's repertoire of internal domains. Many of the ideas embodied in Aleph-1 have been described previously in the literature, and we acknowledge their influence on our thinking, in particular the work of Balzer [1] and Reynolds [5] suggesting the utility of separating out the abstract behavior of an object from its representation, the languages Pascal [10] and Simula-67 [3] which associate functions with data types and types with alternate representations, modular generic functions in Basel [2], Standish's wide variety of structured data [6], and the systematic (though not extensible) treatment of coercion in Algol-68 [8]. Our domain mechanisms bear certain strong similarities to those developed by Morris for the purposes of protection [4].

A Turing machine multiplies on-line if it receives its inputs low order digits first and it produces the k-th output digit before reading in the (k+1)-st inputs. We present a general method for converting any off-line multiplication algorithm which forms the product of two n-bit binary numbers in time F(n) into an on-line method, and the new algorithm requires time only 0(F(n) log n). Applying this technique to the fast multiplication algorithm of Schonhage and Strassen gives an upper bound of 0(n (log n)2 log log n) for on-line multiplication of integers. Other applications are to the on-line problems of products of polynomials over a finite ring, recognition of palindromes, and multiplication by a constant.

This paper contains several results yielding pairs of problems which don't help each other's solution, and therefore which may be said to be complex for “different reasons.” Statements are formalized and results proved within Blum complexity theory, generalized to relative algorithms. The approach is fairly intuitive; all details appear in [1] and [2].

The classes of languages definable by operator precedence grammars1 and by Wirth-Weber precedence grammars2 are studied. A grammar is backwards-deterministic3 if no two productions have the same right part. Operator precedence grammars have no more generative power than backwards deterministic operator precedence grammars, but Wirth-Weber precedence grammars (i.e., grammars having unique Wirth-Weber precedence relations) are more powerful than backwards-deterministic Wirth-Weber precedence grammars; indeed they can generate any context-free language. An algorithm is developed for finding a Wirth-Weber precedence grammar equivalent to a given operator precedence grammar, a result of possible practical significance. The operator precedence languages are shown to be a proper subclass of the backwards-deterministic Wirth-Weber precedence languages which in turn are a proper subclass of the deterministic context-free languages.