Search
Now showing items 1-4 of 4
Distributed FIFO Allocation of Identical Resources Using Small Shared Space
(1985-10)
We present a simple and efficient algorithm for the FIFO allocation of k identical resources among asynchronous processes which communicate via shared memory. The algorithm simulates a shared queue but uses exponentially ...
Probabilistic Analysis of a Network Resource Allocation Algorithm
(1985-06)
A distributed algorithm is presented, for allocating a large number of identical resources (such as airline tickets) to requests which can arrive anywhere in a distributed network. Resources, one allocated, are never ...
Impossibility of Distributed Consensus with One Faulty Process*atio
(1982-09)
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 Colored Ticket Algorithm
(1983-08)
Upper and lower bounds are proved for shared space requirements for solution of a problem involving resource allocation among asynchronous processes. The problem is to allocate some number, k≥1, of resources, in an environment ...