Abstract:
A distributed locking apparatus for a collaborative computing system permits members of a collaborative session to obtain and transfer a lock without the use of a central lock server. Each member of the collaborative session has a lock engine, which transitions among four states depending on the location of the lock. An Available state indicates that the lock is available. A Pending state indicates that the member has requested the lock. A Held state indicates that the member currently holds the lock. A Locked state indicates that another member currently holds the lock. A message structure permits the members to obtain and release the lock and to resolve conflicts over the lock between members of the session.

Description:
FIELD OF THE INVENTION 
     This invention relates to the field of collaborative computing and, more particularly, to the control of processes in a collaborative computing system. 
     BACKGROUND OF THE INVENTION 
     In desktop video conferencing and other desktop collaboration systems, it is often necessary that certain processes be implemented only by a single member of the collaborative session. For example, setting the global conference settings or adding a new member to a video conference generally should be performed only by a single member. 
     In conventional video conferencing systems, a lock is established for these processes by a central lock server. Under the T.120 standard, the top provider serves as the lock server. 
     With a central lock server, the video conferencing session is dependent upon successful communication with, and the non-failure of, the central lock server. Failure of that lock server can cause the video conferencing session to end. 
     The present invention overcomes this and other deficiencies, as will be shown in the remainder of the specification, referring to the attached drawings. 
     SUMMARY OF THE INVENTION 
     The present invention provides a robust locking system through the use of a distributed locking apparatus. 
     In a preferred embodiment, each member of a collaborative session has a separate lock engine for each lock. The collaborative session can be implemented, for example, through the collaborative computing system described in commonly-assigned U.S. patent application Ser. No. 08/401,922, entitled “Apparatus for Collaborative Computing,” which is incorporated herein by reference. With this implementation, the lock engine may be implemented as a lock plugin. Alternatively, other collaborative computing architectures can be used. 
     The lock engine can be in any of four states at any time during a collaborative session: AVAILABLE, PENDING, HELD, or LOCKED. The AVAILABLE state indicates that the session member is not aware of any member who holds the lock. Hence, the lock is available. The PENDING state indicates that the session member has sent a request for the lock to the other session members and is awaiting acknowledgment from the other members. The HELD state indicates that the session member currently holds the lock. The LOCKED state indicates that another session member currently holds the lock. 
     In order to obtain the lock, a member sends a Request for Lock message, which normally will be acknowledged by the other members. If another member has the lock, it will send a Negative Acknowledgment message back to the requesting member. If the lock is available, the requesting member will receive acknowledgments from each other member, and transition to the HELD state. 
     In order to release the lock, a member sends a Release Lock message to the other members, which will cause them to transition from the LOCKED state to the AVAILABLE state. 
     When a new member joins the collaborative session, a member that holds the lock will send a Claim message to the new member, informing the new member that the lock is held. The new member will then transition from its initial AVAILABLE state to the LOCKED state. 
     Preferably, conflicts between session member requests are resolved by giving preference to the member with the lower handle. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a collaborative session using a distributed locking apparatus according to the present invention. 
     FIG. 2 is a state diagram illustrating a transition between states using a distributed locking apparatus according to the present invention. 
     FIGS. 3A,  3 B, and  3 C illustrate a first message sequence for a distributed locking apparatus according to the present invention. 
     FIGS. 4A and 4B illustrate a second message sequence for a distributed locking apparatus according to the present invention. 
     FIGS. 5A,  5 B,  5 C illustrate a third message sequence for a distributed locking apparatus according to the present invention. 
     FIGS. 6A,  6 B, and  6 C illustrate a fourth message sequence for a distributed locking apparatus according to the present invention. 
     FIGS. 7A and 7B illustrated a fifth message sequence for a distributed locking apparatus according to the present invention. 
     FIGS. 8A and 8B illustrate a sixth message sequence for a distributed locking apparatus according to the present invention. 
     FIGS. 9A and 9B illustrate a seventh message sequence for a distributed locking apparatus according to the present invention. 
     FIGS. 10A and 10B illustrate an eighth message sequence for a distributed locking apparatus according to the present invention. 
     FIG. 11 illustrates the format of a message used with a distributed locking apparatus according to the present invention. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     A collaborative computing session is shown in FIG.  1 . The user of each workstation  10  (indicated individually as  10   a ,  10   b ,  10   c , and  10   d ) is joined in a video conferencing session over network  12 . Each workstation includes a series of collaborative computing modules  14 ,  16 ,  18 , and  20 , and a series of corresponding lock engines  24 ,  26 ,  28 , and  30 , one for each collaborative module. This enables there to be a separate lock for each collaborative module. Where appropriate, a collaborative computing module may have no corresponding lock engine or more than one corresponding lock engine, or a lock engine may be shared by multiple collaborative computing modules. Collaborative module  14  may be, for example, for video conferencing, while collaborative module  16  is for a whiteboard session, collaborative module  18  is for audio conferencing, and collaborative module  20  is for a text tool. These collaborative computing modules may include both software and hardware, and are described in more detail in commonly-assigned U.S. patent application Ser. No. 08/401,922, entitled “Apparatus for Collaborative Computing,” which is incorporated herein by reference In the example shown, workstation  10   a  has the lock for software module  14 , and thus the lock engine  24  for software module  14  is in the HELD state (indicated by the letter H in the Figures) and the lock engine  24  for software module  14  of each other workstation in the session (i.e., workstations  10   b ,  10   c , and  10   d ) is in the LOCKED state (indicated by the letter L in the Figures). 
     Although the lock engines are described as separate entities from the collaborative computing modules, it is understood that the lock engine and the collaborative computing module could be two parts of an integrated collaborative module. 
     Lock engines  24 ,  26 ,  28 , and  30  each contain a state machine  34 , which at any time can be in AVAILABLE state  40 , PENDING state  50 , HELD state  60 , or LOCKED state  70 . A state diagram for the state machine  34  of lock engines  24 ,  26 ,  28 , or  30  of FIG. 1, illustrating the transitions between the states, is shown in FIG.  2 . When a member of a collaborative session is not aware of any member of the session that has the lock, the member will be in the AVAILABLE state  40 . Generally, in the absence of exceptions and after all members have transitioned, if one member is in the AVAILABLE state  40  then all members will be in the AVAILABLE state  40  or the PENDING state  50 . AVAILABLE state  40  indicates that the lock is available. 
     PENDING state  50  indicates that the session member has sent a request for the lock to the other session members and is awaiting acknowledgment. In a preferred embodiment, a session member will send a request for the lock only if it is in the AVAILABLE state  40 . 
     HELD state  60  indicates that the session member currently holds the lock. LOCKED state  70  indicates that another session member currently holds the lock. Generally, in the absence of exceptions, if one member of a collaborative session is in the HELD state  60 , the other members will be in the LOCKED state  70 . 
     Once in the HELD state  60 , a member remains in that state until it releases the lock and transitions to the AVAILABLE state  40 . 
     In a preferred embodiment, a member will request the lock only if it is in the AVAILABLE state  40 . However, as described in more detail below, a member could be permitted to request the lock from the LOCKED state  70 , which would require the member in the HELD state  60  first to transfer or release the lock. 
     From the AVAILABLE state  40  (and, alternatively, from the LOCKED state  70 ), a member  10   a  can send a Request for Lock message  42  to the other members ( 10   b ,  10   c , and  10   d ), as illustrated in FIGS. 2 and 3A. Upon sending the Request for Lock message  42 , member  10   a  transitions to the PENDING state  50  (indicated by the letter P in the Figures). The other members ( 10   b ,  10   c , and  10   d ), if they are in the AVAILABLE state  40  (indicated by the letter A in the Figures), respond to the Request for Lock message  42  by sending an Acknowledgment message  44  to member  10   a  and transitioning from the AVAILABLE state  40  to the LOCKED state  70 , as illustrated in FIGS. 2 and 3B. The other members ( 10   b ,  10   c , and  10   d ) also store the identity of the member ( 10   a ) that holds the lock. When requesting member  10   a  has received the Acknowledgment  44  from each other member ( 10   b ,  10   c , and  10   d ), it transitions from the PENDING state  50  to the HELD state  60 , as illustrated in FIGS. 2 and 3C. 
     Preferably, all messages include the identity of the member sending the message and the identities of each member that is to receive the message. In addition, each message for the distributed locking mechanism includes a field indicating the lock to which it applies, so it will be delivered to the proper lock engine. The format for a Request for Lock message  42  is shown in FIG.  11 . Sender field  92  identifies the member sending the message. Recipients field  94  identifies the intended recipients of the message, which for Request for Lock message  42  are each member of the collaborative session. Preferably, Recipients field  94  is in the form of a bit-mapped list of the members of the collaborative session. Message Type field  96  identifies the type of message. Lock Engine field  98  provides the identity of the particular lock engine (e.g., the lock engine for a video conferencing collaborative session) within workstation  10  that is to receive the message. 
     In a preferred embodiment, each lock engine maintains a list  36  of each member of the collaborative session and a record of acknowledgments in the form of a bit-mapped list  38  of the members. As each acknowledgment to a Request for Lock message  42  is received, member  10   a  switches the appropriate bit from a 0 to a 1. If any of the bits are still 0, member  10   a  remains in the PENDING state  50 . Once all of the bits are 1, indicating that all members have acknowledged, member  10   a  transitions to the HELD state  60 . 
     When a new member joins a collaborative session already in progress, it initially will be in the AVAILABLE state  40 . Preferably, the new member immediately sends an Accepted message  82  to the other members, indicating that it has been accepted into the collaborative session. In a preferred embodiment, the Accepted message  82  is also used outside of the distributed locking system and is sent to the appropriate collaborative computing module in addition to being routed to the lock engine of each other member. The other members respond to the Accepted message by updating their lists of members. If a member has the lock, then upon receiving the Accepted message  82 , it will send a Claim message  62  to the new member. As illustrated in FIGS. 2,  4 A, and  4 B, member  10   a  holds the lock and is in the HELD state  60  when it receives the Accepted message  82  from new member  10   e . The other members ( 10   b ,  10   c , and  10   d ) are in the LOCKED state  70 , and also receive the Accepted message from new member  10   e . Upon receiving the Accepted message  82 , member  10 a sends the Claim message  62  to new member  10   e . Upon receipt of Claim message  62 , new member  10   e  transitions to the LOCKED state  70 . 
     When the lock is not held (i.e., the members are in the AVAILABLE state  40 ), two members might request the lock before either receives the Request for Lock message. As illustrated in FIGS. 2 and 5A, members  10   a  and  10   b  each send a Request for Lock message  42  and transition from the AVAILABLE state  40  to the PENDING state  50 . Member  10   c  responds only to the first Request for Lock message  42  that it receives. Accordingly, member  10   c  sends an Acknowledgment  44  to member  10   b , whose Request for Lock message  42  it received first, and transitions to the LOCKED state  70 . As explained below, if the resolution of the conflict over the lock between members  10   a  and  10   b  is that member  10   a  receives the lock, then member  10   c  will send an Acknowledgment  44  to member  10   a  upon receipt of notice of the resolution, and will change its record of the member that holds the lock. 
     Member  10   a  receives the Request for Lock message  42  from member  10   b  and checks whether it has a lower handle than member  10   b . Since member  10   a  has a lower handle, it sends a Negative Acknowledgment message  52  to member  10   b , as illustrated in FIGS. 2 and 5B. Alternatively, other methods could be used to determine which member receives the lock. For example, in case of conflict, both lock requests could fail with each requesting member required to wait a random time period before sending another Request for Lock message  42 . This method is similar to the algorithm used when collisions are detected on an Ethernet local area network. 
     Member  10   b  receives the Request for Lock message  42  from member  10   a  and likewise checks whether it has the lower handle. Since member  10   a  has the lower handle, member  10   b  sends a Transfer message  54  to the other members ( 10   a  and  10   c ), indicating that it has transferred its Request for Lock to member  10   a . Transfer message  54  includes a field indicating the member ( 10   a ) to whom member  10   b  is transferring its Request for Lock. Preferably, member  10   b  also sends an Acknowledgment  44  to member  10   a . However, Transfer message  54  could also serve as an acknowledgment. Upon receipt of the Transfer message  54  from member  10   b , member  10   c  sends its Acknowledgment  44  to member la, as illustrated in FIGS. 2 and 5C. 
     If new member  10   e  sends a Request for Lock message  42  before receiving the Claim message  62  (as illustrated in FIGS.  2  and  6 A), it will transition to the PENDING state  50 . New member  10   e  will then receive the Claim message  62  and a Negative Acknowledgment message  52  from member  10   a  (as illustrated in FIGS.  2  and  6 B). Upon receipt of either the Claim message  62  or the Negative Acknowledgment  52 , new member  10   e  sends a Transfer message  54  to the other members and an Acknowledgment  44  to member  10   a , as illustrated in FIGS. 2 and 6C. Because Transfer message  54  indicates that the lock is being transferred to member  10   a , which members  10   b ,  10   c , and  10   d  already recognize as holding the lock, it is not necessary for members  10   b ,  10   c , and  10   d  to send a new Acknowledgment to member  10   a.    
     If a member ( 10   a ) receives a Request for Lock message  42  (from member  10   c ) when the member ( 10   a ) is in the HELD state  60  (FIGS.  2  and  7 A), the member ( 10   a ) will send a Negative Acknowledgment  52  to the sending member ( 10   c ) (FIGS.  2  and  7 B). This could occur, for example, if a new member joins the collaborative session and immediately sends a Request for Lock message  42  while it is in its initial AVAILABLE state  40 . Preferably, if a member is in the LOCKED state  70 , it will not send a Request for Lock message  42 . Alternatively, a member in the LOCKED state  70  could send a Request for Lock message  42 , to which the member in the HELD state  60  could respond with a Negative Acknowledgment  52  (indicating that the member in the HELD state  60  will keep the lock), a Transfer message  54  (indicating that the member in the HELD state  60  is transferring the lock to the member that sent the Request for Lock message  42 ), or a Release message  64  (indicating that the member in the HELD state  60  is releasing the lock, but not guaranteeing that the requesting member will receive the lock). 
     To release a lock it holds, member  10 a sends a Done message  66  to its lock engine, as illustrated in FIGS. 2 and 8A. Member  10   a  then responds to the Done message  66  by sending a Release message  64  to the other members ( 10   b  and  10   c ) and transitioning to the AVAILABLE state  40 , as illustrated in FIGS. 2 and 8B. Members  10   b  and  10   c , upon receipt of the Release message  64 , transition from the LOCKED state  70  to the AVAILABLE state  40 . 
     Preferably, if a member leaves the collaborative session, it sends a Left Session message  84  to the other members. As with Accepted message  82 , Left Session message  84  is also used outside of the distributed locking system, but is also routed to the lock engine of each other member. The other members respond to the Left Session message  84  by updating their lists of members. In addition, if the member that sent the Left Session message  84  (member  10   a ) was in the HELD state  60  and left without first sending a Release message  64 , the other members,  10   b  and  10   c  (which keep a record of the member that holds the lock), will transition to the AVAILABLE state  40 , as illustrated in FIGS. 2 and 9A. If a member ( 10   c ) was in the PENDING state  50  and another member ( 10   b ) sends a Left Session message  84  without first sending an Acknowledgment message  44 , the member ( 10   c ) requesting the lock will update its list of members. If, as a result, all remaining members have now acknowledged the Request for Lock message  42 , the member ( 10   c ) requesting the lock will transition to the HELD state  60 . As illustrated in FIGS. 2 and 9B, member  10   a  has already acknowledged Request for Lock message  42  and has transitioned to the LOCKED state  70 . Record of acknowledgments  38  of member  10   c  indicates that member  10   a  has acknowledged but member  10   b  has not acknowledged. Upon receipt of Left Session message  84  from member  10   b  and the updating of the list of members  36 , member  10   b  will be removed from the record of acknowledgments  38 . At this point, all remaining members have acknowledged and member  10   c  transitions to HELD state  60 . 
     When a member is in the LOCKED state  70 , it will not respond to a Request for Lock message  42 . It will remain in the LOCKED state  70  and let the member in the HELD state  60  respond to the Request for Lock message  42 . If a member (shown as  10   a  in FIG. 10A) in the LOCKED state  70  receives a Transfer message  54  (from member  10   c ) indicating that the lock is being transferred to another member ( 10   b ), it will send an Acknowledgment message  44  to the member that is receiving the lock ( 10   b ), and will remain in the LOCKED state  70  (as shown in FIGS.  2  and  10 B). Member  10   a  will also update its record of the identity of the member that holds the lock. After member  10   b  in the LOCKED state  70  receives the Transfer message  54  (from member  10   c ) indicating that the lock is being transferred to member  10   b , member  10   b  responds by transitioning to the HELD state  60 . 
     Although for purposes of clarity the Figures and preceding discussion identify only a few members, it is understood that the distributed locking system may be implemented with any size collaborative session. 
     While there have been shown and described examples of the present invention, it will be readily apparent to those skilled in the art that various changes and modifications may be made therein without departing from the scope of the invention as defined by the appended claims. Accordingly, the invention is limited only by the following claims and equivalents thereto.