Method and apparatus for bus arbitration using a pseudo-random sequence

Claim 1

A second level bus arbitration apparatus for use with a distributed computing network, said distributive computing network comprising a first level of contention and a plurality of computing elements, said second level bus arbitration apparatus being initiated when at least one computing element successfully completes the first level of contention, said second level bus arbitration apparatus comprising: a common data bus operably connected to each of said plurality of computing elements; a common line; a plurality of locally clocked arbitration means operably connected to said common line for allowing one of said plurality of computing elements access to said common data bus, wherein each one of said plurality of arbitration means is associated with a corresponding one of said computing elements, said each one of said plurality of arbitration means further comprising, a means for generating a pseudo-random sequence and transmitting said generated sequence over said common line when said corresponding computing element requests access to said common data bus and prior to the transmission of actual data on said common data bus; and, a collision detection means operably connected to said generating means and said common line for withdrawing said corresponding computing element from said common line when a composite signal appearing on said common line differs from said generated sequence, if no such difference is detected said corresponding computing element proceeds to transmit actual data on said common data bus.

Claim 5

A method of second level bus arbitration for a distributed computing network, said distributive computing network comprising a first level of contention and a plurality of computing elements with each computing element connected over a common bus, said method of second level bus arbitration initiated when at least one computing element successfully completes the first level of contention and comprising the steps of: each of said computing element requiring access to said common bus generates a separate pseudo-random sequence, each sequence generated by a particular computing element being transmitted over a common line; each particular computing element comparing a sequence appearing on said common line with said sequence generated by said particular computing element; a particular computing element withdrawing from the common open collector if a mismatch occurs between said sequence generated by said particular computing element and said sequence appearing on said common collector; and, instructing a particular computing element to access said common bus if said sequence generated by said particular computing element is completed with no mismatch detected between said sequence generated by said particular computing element and said sequence appearing on said common line thereby performing second level bus arbitration without the use of centralized control or centralized clocking.

Claim 6

A method of second level bus arbitration for a distributed computing network, said distributive computing network comprising a first level of contention and a plurality of computing elements with each computing element connected over a common bus, said method of second level bus arbitration initiated when at least one computing element successfully completes the first level of contention and comprising the steps of: each of said computing element requiring access to said common bus generates a separate pseudo-random sequence, each sequence generated by a particular computing element being transmitted over a common line; each particular computing element comparing a sequence appearing on said common line with said sequence generated by said particular computing element; a particular computing element withdrawing from the common open collector if a mismatch occurs between said sequence generated by said particular computing element and said sequence appearing on said common collector; and, instructing a particular computing element to access said common bus if said sequence generated by said particular computing element is completed with no mismatch detected between said sequence generated by said particular computing element and said sequence appearing on said common line thereby performing second level bus arbitration without the use of centralized control or centralized clocking.