Ex Parte Sen et al

Board of Patent Appeals and Interferences

Jun 8, 2012

11691386 (B.P.A.I. Jun. 8, 2012)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
11/691,386 03/26/2007 Raj Kumar Sen 1933.1720001 5572
82515 7590 06/11/2012
Sterne, Kessler, Goldstein & Fox P.L.L.C.
1100 New York Avenue, N.W.
Washington, DC 20005
EXAMINER
BADAWI, SHERIEF
ART UNIT PAPER NUMBER
2167
MAIL DATE DELIVERY MODE
06/11/2012 PAPER
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
PTOL-90A (Rev. 04/07)

UNITED STATES PATENT AND TRADEMARK OFFICE
_____________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
______________

Ex parte RAJ KUMAR SEN and GANGAVARA PRASAD VARAKUR
______________

Appeal 2010-003788
Application 11/691,386
Technology Center 2100
______________

Before JOHN C. MARTIN, JAMESON LEE, and RICHARD TORCZON,
Administrative Patent Judges.

MARTIN, Administrative Patent Judge.

DECISION ON APPEAL

I. STATEMENT OF THE CASE
This is an appeal under 35 U.S.C. § 134(a) from the Examiner’s
rejection of claims 1-49, which are all of the pending claims.
We have jurisdiction under 35 U.S.C. § 6(b).
We REVERSE.

Appeal 2010-003788
Application 11/691,386

2
A. Appellants’ invention
Appellants’ invention relates to allocation and management of unique
identifiers, especially in distributed database environments. Specification
¶ 7. In a distributed system, all of the computers in the network need unique
identifiers for doing their computation, and objects processed by those
computers may themselves need to be uniquely identified across the multiple
computers that comprise the distributed system. Id. at ¶ 12. Thus, there is a
need for allocating and managing identifiers that are unique across the entire
distributed system. Id.
Appellants’ Specification explains that U.S. Patent 6,457,053 ( the
Satagopan reference relied on by the Examiner) employs a master-slave
approach to address this problem. Id. at ¶ 13. A single master server
allocates “pools” of unique identifiers to network servers upon request. Id.
The network servers, in turn, allocate unique identifiers from their pool as
necessary when the network server generates new system objects. Id. When
a network server’s pool of unique identifiers is nearly depleted, the network
server requests an additional pool of identifiers from the master server. Id.
The fact that this approach is not fully distributed (i.e., it requires centralized
management) leads to problems and limitations, including inefficient
messaging and inferior scalability. Id. at ¶ 14. For instance, if the master
server fails or is shut down, another server must take over the role of master,
including obtaining the information necessary to serve in the master role. Id.
Appellants’ system avoids these problems by assigning unique identifiers in
a manner that is not centralized. Id.
Appeal 2010-003788
Application 11/691,386

3
Appellants’ Figure 4 is reproduced below.

Figure 4 is a high-level block diagram illustrating a distributed system
environment 400 in which the system and methodology of Appellants’
invention may be implemented. Id. at ¶ 90. A cluster of four networked
server nodes (411-14) share access to data on shared disk storage 435. Id.
Each node includes an identity manager (e.g., 451 in node 411), an identity
data structure (e.g., 461), a cluster current value (e.g., 471), and a cluster
Appeal 2010-003788
Application 11/691,386

4
maximum value (e.g., 481). Id. This information is protected by a
distributed locking mechanism (OCM lock) that is not separately shown in
Figure 4. Id.
In operation, when identifiers (identity values) are needed at a node
the corresponding identity manager (e.g., 451 at node 411) obtains a block of
identifiers from the sysobjects row of a database table stored on shared disk
storage 435. Id. at ¶ 91. As part of this operation, identity manager 451
informs the other identity manager modules (e.g., 452-54 at nodes 412-14)
and the allocation of this block of identifiers is recorded at all of the nodes.
Id. The identity manager then divides up the block of identifiers (e.g., into
four equal parts) so that identifiers can be provided for use at a given node in
response to demand. Id. at ¶ 92. Identifiers allocated for use at a given node
are then made available to tasks needing them for performing operations. Id.
at ¶ 93. If sufficient identifiers are not already allocated for use at node 411,
identity manager 451 will allocate a block of identifiers for use at that node
and will update the identity managers at the other nodes (i.e., identity
managers 452-54) about this allocation. Id. Information about the allocation
is also stored at each of the nodes by updating the identity data structure 461
and cluster current value 471 at node 411 and in corresponding structures at
other nodes. Id.
A node updating the data structure will acquire the OCM lock, make
its updates to the values (e.g., to obtain additional identity values for use by
the updating node), push the updated values to the other nodes of the cluster,
and then release the lock. Id. at ¶ 115.
Appeal 2010-003788
Application 11/691,386

5

B. The Claims on Appeal
The claims on appeal include independent claims 1, 16, and 33, which
reads as follows:
1. In a distributed system having a plurality of nodes, a
method for allocating identifiers for use at nodes of the
distributed system, the method comprising:
allocating a pool of identifiers for use in the system;
maintaining a list of free identifiers in the pool at all
participating nodes in the system;
obtaining at a first node permission to update the list of
free identifiers;
upon receiving permission to update the list, the first
node allocating for itself a set of identifiers from the list of free
identifiers;
updating the list of free identifiers to reflect allocation of
the set of identifiers for the first node;
sending the updated list of free identifiers from the first
node to other participating nodes;
upon receiving the updated list of free identifiers at each
other participating node, updating each other participating
node's respective copy of the list of free identifiers; and
relinquishing the first node’s permission to update the list
of free identifiers.
16. A system for allocating identifiers for use at a
plurality of database server nodes sharing access to a database,
the system comprising:
Appeal 2010-003788
Application 11/691,386

6
a database;
a plurality of database server nodes connected to each
other via a network and sharing access to the database;
an identity data structure at each database server node for
maintaining information about identifiers allocated for use
among the plurality of database server nodes;
a distributed lock for regulating access to the identity
data structure at the plurality of server nodes; and
an identity manager, responsive to a request for
identifiers at a given node, for acquiring the distributed lock on
the identity data structure, allocating a set of identifiers to the
given node upon acquiring the distributed lock, updating the
identity data structure at said plurality of database server nodes
to reflect allocation of the set of identifiers for the given node,
and relinquishing the distributed lock after completion of
updates to the identity data structure at all database server
nodes.
33. In a distributed database system having a plurality of
nodes sharing access to a database, a method for allocating
identifiers for use at nodes of the distributed system, the method
comprising:
allocating a pool of identifiers from the database for use
among the plurality of nodes of the distributed database system;
maintaining information about the pool of identifiers at
each of the nodes in an identity data structure;
in response to a request for identifiers at a given node,
providing identifiers from a set of identifiers previously
allocated for use at the given node while identifiers remain in
the set allocated for the given node;
Appeal 2010-003788
Application 11/691,386

7
when no identifiers remain in the set, obtaining additional
identifiers for use at the given node by performing substeps of:
acquiring a lock on the identity data structure at
each of the nodes;
at the given node, allocating identifiers available in
the pool for use at the given node;
updating the identity data structure to reflect
allocation of the identifiers for the given node; and
upon updating the identity data structure at all
nodes, relinquishing the lock.
Claims App. (Br.1 19, 21, 24).

C. The Rejections
The rejections are stated in the Answer as follows:2
Claims 1-3, 5-13, and 33-49 stand rejected under 35 U.S.C. § 103(a)
for obviousness over Sidhu3 in view of Ernst.4 Answer 3, para. 2.

1 Appeal Brief filed June 16, 2008.
2 The rejections as stated in the Final Action additionally relied on Vauclair
U.S. Patent Application Publication 2007/0011116 A1, published January
11, 2007. Final Action 2, at para. 4; id. at 20, para. 5. The Examiner has
explained that “[the] Vauclair reference has been withdrawn from the
rejection since all the limitations cited and referenced by Vauclair are
addressed by Sidhu and Ernst.” Answer 30.
3 U.S. Patent 5,884,322 , issued March 16, 1999.
4 U.S. Patent Application Publication 2005/0086384 A1, published April
21, 2005.
Appeal 2010-003788
Application 11/691,386

8
Claims 14, 32, and 44 stand rejected under § 103(a) for obviousness
over Sidhu in view of Ernst and Satagopan.5 Id. at 21, para. 3.

II. DISCUSSION
A. Claims 1-3, 5-13, and 33-49 -- Sidhu in View of Ernst
Regarding Sidhu, described in more detail below, Appellants argue,
inter alia, that “Appellant's fully distributed solution for allocating
identifiers provides for maintaining the same list of free identifiers at each
node of the distributed system” and that “Sidhu's solution does not maintain
the same list of free identifiers at all server nodes.” (Emphasis in original.)
Br. 10. The Examiner responded by stating that “Appellant's claims do not
recite maintaining the same list of free identifiers at each node, it [sic] only
recites maintaining a list of free identifiers in the pool at all participating
nodes, which is clearly different.” Answer 24. Alternatively, the Examiner
concludes that the references suggest maintaining the same list of free
identifiers at each node. Id.
We agree with Appellants (Reply Br. 4-5) that claim 1 implicitly
requires maintaining the same list of free identifiers at each node of the
distributed system by reciting, inter alia, “upon receiving the updated list of
free identifiers at each other participating node, updating each other
participating node’s respective copy of the list of free identifiers.” Due to
the presence of similar “updating” recitations in independent claims 16 and

5 U.S. Patent 6,457,053 B1, issued September 24, 2002.
Appeal 2010-003788
Application 11/691,386

9
33, we conclude that claim 16 implicitly requires maintaining the same
“information about identifiers allocated for use among the plurality of
database server nodes” at each of the “plurality of database server nodes
sharing access to a database” and that claim 33 implicitly requires
maintaining the same “information about the pool of identifiers . . . for use
among the plurality of nodes of the distributed database system” at each of
the “plurality of nodes sharing access to a database.”
Turning now to the references, Sidhu discloses a system for assigning
unique identifications to entities (e.g., servers) in a network and to items in a
catalog or other database. Sidhu 3:30-37. The rejection relies on Sidhu’s
description of Figure 3, reproduced below.
Appeal 2010-003788
Application 11/691,386

10

Figure 3 is a flowchart showing generally the steps performed to generate
unique server entity identifications in a network of computer systems
incorporating a first embodiment of Sidhu’s invention. Id. at 6:22-25.
These steps are performed in response to a request or other action initiating
an installation of a server entity onto the network. Id. at 8:27-29.
Appeal 2010-003788
Application 11/691,386

11
At decision block 50, it is determined whether the server entity being
installed, called the “new server entity,” is the first server entity to be
installed on the network system. Id. at 8:30-33. If it is the first server entity,
the new server entity at block 52 determines/forms/delineates the possible
unique server identifications in the network system, collectively referred to
herein as the “set of available server identifications” or the “available server
identifications.” Id. at 8:33-39. At block 54 the new server entity assigns to
itself an available server identification and removes that assigned server
identification from its set of available server identifications. Id. at 8:44-47.
If, on the other hand, it is determined at block 50 that the new server entity is
not the first server entity to be installed on the network, the new server entity
at block 56 finds or otherwise identifies a previously-installed server entity,
called herein an “assigning server entity,” which is capable of assigning a
server identification to the new server entity. Id. at 8:65-9:3.
The Examiner, in rejecting claim 1, finds that Sidhu satisfies all of the
claim limitations except that
Sidhu does not clearly disclose obtaining at a first node
permission; maintaining a list of free identifiers at all
participating nodes in the system; [s]ending the updated lists of
free identifiers from the first node to other participating nodes;
upon receiving the updated lists of free identifiers at each other
participating node, updating each other participating node's
respective copy of the lists of free identifiers; [r]elinquishing
the first node’s permission to update the lists of free identifiers.
Answer 4. To remedy these deficiencies, the Examiner relies on Ernst,
which discloses a system and method for replicating, integrating, and
Appeal 2010-003788
Application 11/691,386

12
synchronizing distributed information that facilitates the operation of any
decentralized system sharing information. Ernst ¶ 0039. Ernst employs
[a]n extensible protocol to replicate, integrate and synchronize
distributed information (called X-PRISOTM) as well as a system
and a method employing it . . . that allow an unlimited number
of nodes on a network . . . to participate in a distributed
collaboration with some or all collaboration-related information
shared, related, integrated and synchronized between some or
all of the participating nodes.
Id. at ¶ 0040. Any combination of nodes may come together at will, as long
as they all agree on conforming to the X-PRISO protocol and a core
information model for the information they wish to share. Id. at ¶ 0042.
The pieces of information to be shared are called objects. Id. at ¶ 0057.
Objects are always fully replicated and synchronized. Id. at ¶ 0066. All
replicas of a given object within the distributed system share exactly one
lock, i.e., only one of the replicas of a certain object may be updated at any
point in time. Id. at ¶ 0067. That is, no other replica of the same object can
perform an update unless it acquires the lock first from the replica that
currently holds the lock. Id.
The X-PRISO information modeling technique recognizes three major
concepts: Entity, Relationship, and Property. Id. at ¶ 0085. Each Entity is a
direct instance of exactly one EntityType; each Relationship is a direct
instance of exactly one RelationshipType; and each Property is defined by a
PropertyType. Id. at ¶¶ 0087, 0088, 0090. For a teaching of modifying
Sidhu to maintain the same list of free identifiers at all participating nodes in
the system, the Examiner (Answer 24) cites Ernst’s paragraph 0092:
Appeal 2010-003788
Application 11/691,386

13
[0092] Each EntityType, RelationshipType, and
PropertyType has a permanent unique identifier that constitutes
its respective identity (i.e. the identity of the type, as opposed to
the identity of the instance). During operation of the Distributed
System, all EntityTypes, RelationshipTypes and PropertyTypes
are identified by their unique identifiers. All Nodes in the
Distributed System must agree on those identifiers, and the
underlying information model during the operation of the
Distributed System.
(Emphasis added.) We agree with Appellants that
these teachings are not comparable to Appellant's claim
limitations . . . of maintaining a copy of the list of free
identifiers at each participating node. For one thing, Ernst
makes no mention of a “list” of any sort, much less the specific
teachings of a “list of free identifiers.”
Reply Br. 6. Thus, the Examiner’s reliance (Answer 5) on the above
teaching in Ernst is misplaced. So, too, is the Examiner’s reliance, for a
teaching of sending updated lists of free identifiers from the first node to
other participating nodes, on Ernst paragraph 0203:
[0203] To cancel a Lease for a Replica for Object X, Node A
sends a cancellation request to Node B containing Object X's
identifier. Node B will stop notifying Node A of changes
affecting Object X, Node A will discard its Replica of Object X,
and Node B will remove Object X from its internal list of
members of the LeaseGroup. There is no acknowledgement sent
back from Node B to Node A, other than regular Message
confirmation (see above).
We agree with Appellants that
[i]t is unclear how Ernst’s teachings of “Replicas” of objects
held by Node B being maintained at Node A are at all
Appeal 2010-003788
Application 11/691,386

14
analogous to Appellant’s claim limitations of sending an
updated list of free identifiers from one node to other
participating nodes. . . . Ernst does not mention any list of free
identifiers or describe making updates to any such list. Instead,
what Ernst describes is a cancellation message including a
single object identifier being sent from a first node (Node A) to
a second node (Node B). . . . Additionally, the only “list”
described by Ernst is an “internal list of members of the
LeaseGroup” which is maintained at Node B. No mention is
made of a similar list at Node A or of any update being made to
any such list at Node A and given the normal definition of
“internal” it can be assumed that this list is only maintained at a
single node (e.g., Node B).
Reply Br. 8-9.
For the foregoing reasons, we do not sustain the rejection of any of
independent claims 1, 16, and 33 and dependent claims 2-13,15, 17-31, 34-
43, and 45-49 for obviousness over Sidhu in view of Ernst.

B. Dependent Claims 14, 32, and 44 -- Sidhu in View of Ernst and
Satagopan
Dependent claims 14, 32, and 44 are directed to migration of a task
having an identifier from one node to another node.
Claim 14 and claims 12 and 13, through which claim 14 depends on
claim 1, read as follows:
12. The method of claim 1, further comprising: allocating one or more
identifiers to a task running at the first node from the set of identifiers
allocated to the first node when the task needs identifiers.
Appeal 2010-003788
Application 11/691,386

15
13. The method of claim 12, wherein said step allocating one or more
identifiers to the task includes maintaining information about identifiers
allocated to the task at the first node, without updating other participating
nodes about identifiers allocated to the task.
14. The method of claim 13, further comprising: upon migration of the
task from the first node to a second node of the distributed system, sending
information about identifiers allocated to the task to the second node, so that
the task may use such identifiers after migration to the second node.
Claims App. (Br. 20-21).
Satagopan discloses a system for multi-master unique identifier (e.g.,
RID or relative identifier) allocation. Satagopan 2:44-45, 60-61. A single
master server, upon request, allocates “pools” of unique identifiers to
network servers, which in turn allocate unique identifiers from the pool of
identifiers received from the master server. Id. at 2:45-49. The physical
server machine that performs the role of master server may be transferred as
needed to ensure that a master server is always available to allocate pools of
identifiers to the other, non-master servers. Id. at 2:52-55.
The Examiner (Answer 22) bases the rejection of claims 14, 32, and
44 on the following passages in Sidhu and Satagopan:
[T]he server can assign all of its identifications or a portion
thereof to another server, preferably one which is more likely to
use the identifications. This mechanism provides a means for
appropriating identifications in a manner which is consistent
with network use, thereby reducing the number of
identifications that remain dormant because of inactivity on the
server which owns those identifications.
Sidhu 4:15-21.
Appeal 2010-003788
Application 11/691,386

16
Although multiple server machines in a network may be
capable of performing a particular network-wide task such as
RID Master, at any particular moment, only one machine is
designated as the master server with exclusive authority to
perform the task. The master server for a task can be changed or
“floated” to other servers in the system and the remaining
servers automatically notified of the change.
Satagopan 8:67-9:7.
We agree with Appellants (Br. 15-16) that these passages do not cure
the deficiencies of Sidhu and Ernst as applied in the rejection of independent
claims 1, 16, and 33. We therefore do not sustain the rejection of any of
dependent claims 14, 32, and 44 for obviousness over Sidhu in view of Ernst
and Satagopan.

III. DECISION
The Examiner’s decision that claims 1-49 are unpatentable over the
applied prior art is reversed.

REVERSED

Sterne, Kessler, Goldstein & Fox P.L.L.C.
1100 New York Avenue, N.W.
Washington DC 20005