Backoff protocols and methods for distributed mutual exclusion and ordering

• US 7,155,524 B1
• Filed: 12/04/2001
• Issued: 12/26/2006
• Est. Priority Date: 12/04/2000
• Status: Active Grant

• Current Assignee: Yissum Research Development Company of the Hebrew University of Jerusalem Ltd. (Hebrew University of Jerusalem), Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Hebrew University, Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Malkhi, Dahlia, Chockler, Gregory, Reiter, Michael Kendrick
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US10/005,508
• Time in Patent Office: 1,848 Days
• Field of Search: 709/223, 709/229, 709/249, 709/225, 709/226, 340/10.1, 340/10.2, 340/229, 717/101, 710/200, 707/8
• US Class Current: 709/229
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A system for and method of implementing a backoff protocol and a computer network incorporating the system or the method. In one embodiment, the system includes: (1) a client subsystem that generates a request for access to a shared resource and (2) a server subsystem that receives the request, returns a LOCKED indicator upon an expectation that the shared resource is unavailable and otherwise returns a FREE indicator, the client subsystem responding to the LOCKED indicator by waiting before regenerating the request for the access.

Claims

1. A system for implementing a backoff protocol, comprising:

a client subsystem configured to generate a request for access to a shared resource; and

a server subsystem configured to receive said request, return a LOCKED indicator upon an expectation that said shared resource is unavailable and otherwise return a FREE indicator, said client subsystem further configured to respond to said LOCKED indicator by waiting an amount of time proportional to twice a previous amount of time associated with said waiting before regenerating said request for said access.

2. The system as recited in claim 1 wherein said server subsystem has said expectation when said server subsystem returned said FREE indicator less than Δ

+2δ

time units previously.

3. The system as recited in claim 1 wherein said server subsystem is replicated among a plurality of separate servers.

4. The system as recited in claim 1 wherein said system is coupled to a synchronous computer network.

5. The system as recited in claim 1 wherein a unique rank is associated with said request.

6. The system as recited in claim 1 wherein said shared resource is an Ethernet channel.

7. The system as recited in claim 1 wherein said request is independent of digital signatures.

8. The system as recited in claim 1 having an amortized system response time independent of a maximum number of possible requests for access to said shared resource.

9. A method of implementing a backoff protocol, comprising:

generating a request to a server subsystem for access to a shared resource;

determining if said shared resource has an expectation of being unavailable;

returning a LOCKED indicator based upon said expectation when said shared resource is unavailable and otherwise returning a FREE indicator; and

responding to said LOCKED indicator by waiting an amount of time proportional to twice a previous amount of time associated with said waiting before regenerating said request for said access.

10. The method as recited in claim 9 wherein said server subsystem has said expectation when said server subsystem returned said FREE indicator less than Δ

+2δ

time units previously.

11. The method as recited in claim 9 wherein said method is carried out in a synchronous computer network.

12. The method as recited in claim 9 wherein a unique rank is associated with said request.

13. The method as recited in claim 9 wherein said shared resource is an Ethernet channel.

14. The method as recited in claim 9 wherein said request is independent of digital signatures.

15. A computer network, comprising:

a plurality of clients;

a plurality of servers coupled to said plurality of clients;

at least one shared resource coupled to said plurality of servers;

a system for implementing a backoff protocol with respect to said at least one shared resource, including;

a client configured to generate a request for access to a shared resource, and

a server configured to receive said request, return a LOCKED indicator upon an expectation that said shared resource is unavailable and otherwise return a FREE indicator, said client further configured to respond to said LOCKED indicator by waiting an amount of time proportional to twice a previous amount of time associated with said waiting before regenerating said request for said access.

16. The computer network as recited in claim 15 wherein said server subsystem has said expectation when said server subsystem returned said FREE indicator less than Δ

+2δ

time units previously.

17. The computer network as recited in claim 15 wherein said computer network is synchronous.

18. The computer network as recited in claim 15 wherein a unique rank is associated with said request.

19. The computer network as recited in claim 15 wherein said one of said at least one shared resource is an Ethernet channel.

20. The computer network as recited in claim 15 wherein said request is independent of digital signatures.