> SCH - SMCA**-**-****.R*

Role Transfer Problems and Algorithms

Haibin Zhu, Senior Member, IEEE, and MengChu Zhou, Fellow, IEEE

play to deal with an emergency situation? Which roles should a

person play? What role-person mapping is effective in dealing

Abstract Role transfer is a usual activity in an organization,

especially in a crisis situation. Role assignment and transfer with an emergency situation? What group structures can avoid

regulations are important to accomplish it. This paper discusses crisis? There are no clear, exact answers for these questions

the general role transfer problem; proposes a role specification

hitherto. This paper intends to demonstrate that specially

mechanism; builds a set of terminologies for role transfer based

arranged role-person mapping can help a group survive better

on a revised E-CARGO (Environment-Class, Agent, Role, Group,

in an emergency situation. Our role-based collaboration model

and Object) model; and presents algorithms to validate role

E-CARGO (Environment-Class, Agent, Role, Group, and

transfer while maintaining group viability. The contributions

include formulating the problem of role transfer in a generalized Object) [17, 18] can be successfully adopted in processing such

form; developing a set of algorithms; and presenting a solution situations.

when group members are insufficient.

There are actually two aspects in the research of role transfer.

One is that when there are sufficient people and the other is not.

Index Terms Role, Role Transfer, Information Systems,

We need to investigate different methods to deal with them.

Organization, Emergency Management

Our solution for the latter is to introduce time intervals to solve

it. We call the latter temporal role transfer.

I. INTRODUCTION

The rest of this paper is arranged as follows: In Section II, we

R OLE transfer is a basic requirement for organizations [1]

discuss some relevant research. In Section III, we demonstrate

and emergency management systems [15]. It is used to

the revised E-CARGO model that aims at supporting role

evaluate and check the flexibility of a group when its

transfer. Section IV describes fundamental terminologies for

membership and/or roles change. Role transfer is a complex

role transfer; Section V discusses the role transfer problem and

event that may involve many relevant roles. When an

relevant theorems; Sections VI, VII, and VIII describe the

organization encounters a crisis situation, not every one can

algorithms and their implementation for role transfer. Section

transfer his/her roles. When one person transfers to a new role,

IX extends the role transfer problem to a temporal role transfer

his/her original role needs to be assumed by another if the role

problem and gives its solution algorithm. Section X concludes

is still required in the system. This change might initiate a series

the paper.

of role transfers. For example, in a battle field, if a high rank

officer is disabled, a similar or lower rank officer is needed to

II. RELATED RESEARCH

play his/her role. The role played by the similar or lower rank

Although role transfer is an important problem in

officer may need to be played by another, etc. A

management, organizational behavior and performance, and

highly-available computer system should meet the similar

system development, there is no comprehensive research on

requirement for computers, sub-systems, components to

role transfer theory, algorithms and practice. Some research

transfer their functions (or roles) to recover from a faulty state.

mentioning the similar problem uses different terms, for

We generally need duplicate them to tolerate faults.

example, resource assignment [5] and job assignment [10].

One specific role should be played by more than one person

Some related research is those in agent systems [14] and

(computer, sub-system, or system component). One person

wireless communications [2] using the term role assignment.

should be able to play more than one role [15, 17-20].

Others mainly investigate people s or organization s behaviors

However, how many roles should a person play or potentially

[7, 12] when role transfer happens and they use the term role

transition. The research by sociologists and psychologists

Manuscript received January 21, 2007, revised September 5, 2007, accepted mainly concerns the behavior of people and organizational

April 27, 2008. This work was supported in part by National Sciences and

performance when role transition occurs [1, 3, 4, 13].

Engineering Research Council of Canada (NSERC, No. 262075), IBM Eclipse

Research on the delegation of rights (tasks, authorization,

Innovation Grant, and Changjiang Scholars Program, PRC Ministry of

permissions, responsibilities, or even roles) [9, 11, 16] deals

Education.

H. Zhu is with the Department of Computer Science and Mathematics,

with the problem of transferring rights (permissions,

Nipissing University, 100 College Drive, North Bay, Ontario, P1B 8L7,

responsibilities or roles) to neighbor agents or subordinate

Canada(phone: 705-***-**** ext. 4434; fax: 705-***-****; e-mail: haibinz@

users. It mainly provides policies, rules or protocols to

nipissingu.ca).

M. C. Zhou is with the Department of Electrical and Computer Engineering, guarantee that the transfer (sometimes copy) process is

New Jersey Institute of Technology, Newark, NJ 07102, USA and School of

possible, complete, trustable and secure. The results are mainly

Electro-Mechanical Engineering, Xidian University, Xi an, 710071, China

(e-mail: abp65w@r.postjobfree.com).

> SCH - SMCA07-01-0025.R1 where n is the

used for computer security.

identification of the group; e is an environment for the group to

The current research shows that there are indeed strong

needs to investigate the role transfer problem. The research work; and J is a set of tuples of an agent, role, and complex

results presented in this paper are expected to apply in many object, i.e., J {

=

q, (o ) ( e.B )

different fields, such as, information systems, management, }.

production, and manufacturing industry.

In a crisis, the E-CARGO model can be used to demonstrate

the states of a group of people using an emergency system. The

III. REVISED E-CARGO MODEL FOR EMERGENCY SYSTEMS

agents and related roles in the system clearly tell the people

Without a clear specification of components, there would be their responsibilities and rights. If one person is called out of

no real successful system. By establishing a formal model to the group, another in it must take the position of that person.

define and specify a role, we can obtains a clear view of The computer system can quickly show the new roles to the

systems. A well-defined internal structure is a guarantee for a people in the group if an efficient role transfer mechanism is in

successful system. It supports the robustness, efficiency and place.

correctness of the entire system. By E-CARGO [17, 18], we

mean Environments, Classes, Agents, Roles, Groups and IV. BASIC DEFINITIONS

Objects. A role-based system is described as a 9-tuple. ::= In some situation, especially a crisis, the agent-role, where, C is a set of classes; O is a set relationships need to be changed. Only some agents, roles or

of objects; A is a set of agents who are representatives of human groups are critical. We need to discern the differences in order

users; M is a set of messages; R is a set of roles; E is a set of to deal with a crisis effectively. To understand the problem of a

environments; G is a set of groups; s0 is the initial state; and H is crisis situation, we need to define some common terms. In the

a set of users. following discussion, we use agents or people interchangeably

To deal with the role transfer problem in organizations and and are mainly concerned about Ac and Ap of a role r, and rc and

systems, we emphasize the relationships among roles and Rp of an agent a.

agents in a group. Therefore, we restate the details of an agent, Definition 1: Role r is current to agent a if a is currently

role, environment and group. The definitions of these playing r, i.e., r =a.rc; and a is called as a current agent of r, i.e., a

components are given as follows, where, if x is a set, x is its r.Ac. Role r is potential to a if a is qualified to play but not

cardinality: a.b means b of a or a s b: currently playing it, i.e., r a.Rp; and a is called as a potential

A role is defined as r ::= where n is the agent of r, i.e., a r.Ap. The current role and all potential roles

identification of the role; I ::= denotes a set of of an agent is called as its role repository, i.e., {rc} Rp. Role r

messages, where Min expresses the incoming messages to the is critical if it has only enough agents currently playing it, i.e.,

g, ( g.e.B) ( r.Ac = q.l).

relevant agents, and Mout expresses a set of outgoing messages

or message templates to roles, i.e., Min, Mout M; Ac is a set of Definition 2: Group g is workable if for each role r there are

agents who are currently playing this role; Ap is a set of agents

enough agents to play it, i.e., r R ( q, ( g.e.B)) ( r.Ac q.l)). If a role loses its current agent(s), g

including classes, environments, roles, and groups that can be

re-distributes the agents to play roles. Such re-distribution is

accessed by the agents playing this role.

called as a role transfer. A role transfer is successful if g is

An agent is defined as a ::=, where n is the

workable after it.

identification of the agent; ca is a special class that describes the

Definition 3: An agent is critical if there is no successful

common properties of users; s is the profile of the person whom

role transfer to make group g workable once it leaves g. When

the agent is representing; rc means a role that the agent is

an agent leaves g, g loses this agent and this agent is a lost agent

currently playing. If it is empty, then this agent is free; Rp means

of g. Group g is critical if every agent in it is a critical one. A

a set of roles that the agent has potential to play (rc a.Rp); and

level-n emergency occurs if g has lost n ( 1) agents. g is

Ng means a set of groups that the agent belongs to.

level-n strong if it is workable via successful role transfer after

An environment e ::= where n is the identification of

a level-n emergency occurs.

the environment; and B = {} is a set of 3-tuples of role,

Definition 4: A graph of group g is defined as a tuple, G =

number range and an object set. The number range q tells how, where, V is the node set and E is the arc set, and V =

many users may play role r in this environment and q is a tuple R A, and E = { a A } { a A r

of number, where l means the lower bound of the a.Rp}. There is a partition in g if its graph is not connected [8].

number of agents to play this role and u the upper bound. The Note that, a.Rp is a set of all the potential roles of an agent a.

object set expresses the objects accessed by the agents who The agent can directly serve the requests relevant to its current

play the relevant role. The objects in are mutually exclusive, role. For an agent, a potential role can become current and vice

i.e., one complex object in this set can only be accessed by one versa. An agent can have only one current role. That is to say,

agent (user). For each tuple, q.l q.u. In an emergency an agent can hold many potential roles at the same time but only

system, we are more interested in l.

> SCH - SMCA07-01-0025.R1 SCH - SMCA07-01-0025.R1 0 return TRUE;

0 0 0 1 0 1 0 0

4) A[i]=1;//The first agent is added to the agent array; 0 0 0 0 1 0 1 0

5) R[j]=1;// The first role is added to the role array;

0 1 0 0 0 1 0 1

6) Set a tag T :=1 to show that at least one new agent is

Fig. 7. A potential roles matrix

added to the agent array and one new role to the agent

Output: Success - an M N current role matrix C1 in which

array;

there is no column with all zeros. Failure - an M N current role

7) Collect all the roles touched by agent i;

matrix C1 in which there is still a column with all zeros.

8) While (T==1) // A new role is added

Process (C0, C1, Q, M, N):

{ T := 0;

{//Note: := means assignment from right to left and

Collect all the agents touched by the roles in array R

= //means that the left is equal to the right.

and set T=1 if a new agent is added;

If (M=0 or N = 0) then return failure;

If (T==1) // A new agent is added.

If (in matrix Z=Q+C0 there is one column with all zeros,

{T := 0;

i.e., Z[j, i]=0 (j =0, 1,, N-1)) then return failure;

Collect all the roles touched by the agents in array A

C1:=C0;

and set T=1 if a new role is added;

For (all columns of C1)

}

{ If (column j has all zeros in C1)

}

{ From Q, find row number i Q[i, j] =1;

9) If (all agents are added into the array A and all the roles

In C1, check if this agent (i) has no current role, i.e., it

to R) return FALSE else TRUE.

is a free agent;

The algorithm is of complexity O(MN2). It seems more If (Yes)

complex than a typical DFS (Depth First Search) algorithm [6] { C1[i, j]:= 1, Q[i, j]:=0;

as DFS has complexity O((M+N)2) when an adjacency matrix C0 := C1 and Q := Q;

is used. However, if M is a constant, it is similar to the typical Delete row i and column j from C0 and Q ;

DFS algorithm, i.e., O(N2); if N is a constant, it is better than M := M -1, N := N-1;

DFS, i.e., O(M). Call Process(C0, C1, Q, M, N);

Q:= Q and C1 := C1 with keeping the original row i

VII. ROLE TRANSFER ALGORITHM WITH MATRICES and column j;

A role transfer can be expressed by converting matrix C0 into Return;

C1 mathematically. For example, if C0 is shown as in Fig. 6 (a) }

and C1 Fig. 6 (b), a successful transfer exists, i.e., agent A2 is Else

{ Find the column index k such that C1 [i, k]=1;

now playing R2 and the group is workable. An example of

current role matrix C0 and C1 (M = 8, N = 8) is shown in Fig. 1. If (Yes)

{ C1[i, j]:= 1, Q[i, j]:=0, Q[i, k]:=1, C1 [i, k] := 0;

Fig. 6(a) (C0) expresses the situation of Fig. 2(a) when A8 is lost

C0 :=C1and Q := Q; delete row i and column j

and Fig. 6(b) (C1) expresses a solution of Fig. 6(a). From C0 and

from C and Q ;

0

C1, there is a role transfer, i.e., A2 acquires a new current role

M :=M -1, N:= N-1;

R2.

Call Process(C0, C1, Q, M, N);

To make a group workable, a successful transfer is needed and

Q:= Q and C1 := C1 but keeping original row i

can be conducted with the help of matrix Q. Q expresses the

and column j;

potential roles of each agent. For example, Fig. 7 shows such a

Return;

matrix for Fig. 1(b) after A8 leaves.

}

1 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 Else

1 0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 Return failure;

0 0 0 0 0 0 0 1 0 0 0 0

}

0 0 1 0 0 0 0

0 0 0 0 0 0 0 1

0

0 0 0 0 }

0 0 1 0 0 0 0 0 1 0 0 0

0 0 0 0

0 0 0 1 0 0 0 0 0 1 0 0 }

0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0

Report success;

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1

}

(a) (b)

> SCH - SMCA07-01-0025.R1 mapping for current agents U and a set of role

transferRoles is used to transfer roles in the group (Step 2).

mapping for qualified agents V, and a role w

The key point of the implementation is that we need a graph

without a current agent, i.e., a A ( U).

retrieval algorithm and a back traceable search algorithm.

Output: Success - a group G with a set of roles R, a set of

O(M+N) +

The complexity of the algorithm is C(M, N) =

agents A, a set of mapping for current agents U, a

set of role mapping for qualified agents V, r O(M) C(M-1, N-1). Treating N and M as a constant, we have

R, a ( U). Failure - a group G with a set of roles R, a C(M) = O(M!) and C(N) = O(N2), respectively. Compared with

set of agents A, a set of mapping for current

the algorithm using matrices, this one is more affected by the

agents U and a set of role mapping for qualified

agent number. The difference comes from the recursive

agents V and a role without current agent w, i.e., a A U). latter searches in the agent space.

Process:

Step 1: Preparing for role transfer: IX. TEMPORAL ROLE TRANSFER

1) Build R a set of all the roles in group G.

Section V and VII discuss the methods how to check if a

2) Build A a set of all the agents in group G.

group has a successful role transfer when there are enough

3) Set w the role currently without a playing agent.

agents to play roles. That is to say, we assume that there are

4) If RA report failure, i.e., there is no successful

sufficient agents or people to avoid a crisis situation, i.e., A

role transfer.

R . In fact, in an emergency situation, scarcity is often more

5) Else proceed to Step 2.

than sufficiency, i.e., AR . In this situation, the intuitive

Step 2: RoleTransfer(A, R, w):

solution is letting a person play more than one roles in different

1) If A = and R then report failure and exit.

time segments.

2) If R = then report success and stop.

3) For all a A do To express temporal role transfers, we actually have three

{ If w a.Rp (i.e., V) then parameters, i.e., roles, agents, and intervals. The problem

becomes: could we check if a group is workable in a period

{

If a.rc is empty then set a.rc with w. when we allow time sharing agents? That is to say, if every role

has enough agents to play at one in p (p = n ), the group is

Report success and exit.

} considered workable. For example, in a crisis, an office still

} works if each position has at least two hours with a person

4) For all a A do working on it in a 24-hour day, where, p = 24 hours, and = 2

If w a.Rp (i.e., V) then

{ hours and n = 12.

Save a.rc to q;

{ We can understand this problem with an example shown in

// Note that, q is a temporary space to store the Fig. 8. In Fig. 8(a), the group is not workable and has no

//current role. successful transfer after A7 is lost, because there is no other

Set a.rc with w; agent that can play role R7, i.e., A7 is a critical agent. If A6 is lost,

Set A with A.remove(a); the group can be scheduled workable in a period p at scale 2.

Set R with R.remove(w); That is to say, for any period p, we can separate it into 2

Set w with q; intervals and make the group temporally workable shown in

Call RoleTransfer(A, R, w); Fig. 8(b) and Fig. 8(c). In this period, A5 transfer back and forth

> SCH - SMCA07-01-0025.R1, where Cr replaces the original rc to express a agent Ai plays role Rj at interval k.

list of current roles, i.e., a list of tuples in a form of ; and Properties of role playing matrices for a workable group are:

0 i =0 C k [i, j ] n, j = 0, 1,, l-1, k = 0, 1,, n-1. (1)

m 1

r ::=, where At replaces the original Ac to

express a list of tuples of .

Definition 5: Suppose that a period is divided into n

m 1

C k [i, j ] = 1, i = 0, 1,, n-1, k = 0, 1,, l-1. (2)

intervals, i.e., = { 0, 1,, n-1}. When an agent a plays role r at an j =0

interval i (i =0, 1,, n-1), is called an agent-interval for r

0 k =0 C k [i, j ] n, i = 0, 1,, m-1, j = 0, 1,, l-1. (3)

n 1

and is called a role-interval for a. A group g is temporally

workable in at scale n if for each role r there are enough

agent-intervals to play it, i.e., r R ( q, ( g.e.B) ( i ( r. At)) ( At q.l)).

role at one interval; and (3) tells if there is role transfer for a

Before developing an algorithm for temporal role transfer, it

specific agent and role.

is needed to understand the inherent properties of the

Contact this candidate