International Business Machines Corporation

Kenneth J Perry

Brent Tzion Hailpern

Dennis Gerard Shea

Ashok Malhotra

Lee W Hoevel

Juan Alberto Garay

Yannick J Thefaine

This invention includes a consensus protocol, a broadcast protocol and a fault tolerant computer system created by using the two protocols together in combination. The protocols and system use the minimum number of processors to create a system tolerant of concurrent processor crash and byzantine failures. The protocols are subject to certain validity conditions. The system in the state of consensus is guaranteed to have all non-faulty processors in agreement as to what action the system should take. The system and protocols can tolerate up to t total number of processor failures, no more than b of which may fail in the byzantine mode.

Computer system resilient to a wide class of failures

An apparatus and method is disclosed for efficiently clustering program objects on a unit of storage in a secondary memory, e.g., a page of memory on a disc. The objects are clustered so that a set of queries (query set) can access the stored objects with a minimum number of page transfers from secondary storage to main memory. To determine how the objects are clustered together on each memory page, queries in the query set and the objects that they access are identified. The queries are ranked by a number of factors including the query weight, the memory space required to store objects accessed by a query, and the number of objects a query has in common with other queries. The objects accessed by the query set are clustered on secondary memory pages according to the query ranking. Partially packed memory pages can be combined to minimize the cost of the query set accessing the stored objects.

Storage clustering and packing of objects on the basis of query workload

A system for establishing connections between processors in a distributed system of processors connected by a multiple multi-drop network. No wires are needed in addition to those already present in an existing network. In such a network connecting n processors, each processor is connected to all others by n identical multi-drop links. Links are assigned to processors on a one-to-one basis and a processor may transmit messages only on its assigned link. Processors may receive messages on any of these links, thereby enabling a processor to communicate with all others. The advantage of such a network over a single multi-drop link is that there is no contention for a shared link since each processor has a unique transmit line. In addition, no central control means is required for the network, as completely distributed control is utilized.

Growing community of inventors

Riverdale, NY, United States of America

Kenneth J Perry