Causality and the Spatial-Temporal Ordering of Events in Mobile Systems

(1)

Causality and the Spatial-Temporal Ordering of Events in Mobile Systems

Ravi Prakash Roberto Baldoni

Computer Science Program Dipartimento di Informatica e Sistemistica The University of Texas at Dallas University of Rome ”La Sapienza”

Richardson, TX 75083-0688, U.S.A. Via Salaria 113, I-00198 Roma, Italy.

www.utdallas.edu/

ravip www.dis.uniroma1.it/

baldoni

Abstract

Several mobile computing applications require that both the order of occurrence of events, and the location of their occurrence, be taken into account during decision making.

Thus, processes need to track the location of nodes and syn- chronize their clocks. In this paper we present a frame- work, based on the capabilities of Global Positioning Sys- tem, which provides processes with a global virtual clock and a positioning service. We introduce then the notion of space-time vector used by processes to track the mobility of nodes.

1 Introduction

In the asynchronous model of distributed computation, where message passing is the sole means of communication, message propagation delay is finite but non-deterministic.

All the processes have their own clocks. In the absence of a global clock, Lamport proposed the idea of a logical scalar clock that captured the happened before relation be- tween events [7]. If event

^a

happened before event

^b

then the clock value associated with

^a

is less than the clock value associated with

^b

. However, the converse is not always true.

With the advancement of technology, it has become im- perative that we reconsider the traditional assumption re- garding the absence of a global clock in a distributed sys- tem. Now, we have Global Positioning Systems (GPS) sup- ported by a constellation of satellites that can provide very accurate clock information [4]. So, if all the nodes were to be equipped with GPS receivers, they could all be sharing a virtual global clock. Furthermore, GPS provides each node with its location information (latitude, longitude and eleva- tion) with a high degree of accuracy. The degree of accuracy for military domain is higher than the civilian domain, and it is steadily improving in both domains.

In the context of the capabilities provided by GPS, we

propose a framework for modeling and tracking locality in- formation of mobile nodes in a distributed system. We con- sider node mobility restricted to a two-dimensional space.

The location of a node can be expressed as an

^(x;^y)

co- ordinate with respect to a third dimension, namely time.

Thus, if at time

⁰

the location of a node is

^(0;⁰⁾

, then its location at time

^t

will be restricted to the interior of a circle of radius of

^s^t

centered at

^(0;⁰⁾

, where

^s

is the upper bound on the speed of mobile nodes.

This paper is organized as follows. In Section 2 we briefly describe the Navstar Global Positioning System.

Then, in Section 3, we state how GPS can be used to pro- vide a virtual global clock for a distributed mobile system.

In Section 4 we revisit the happened before relation [7] and

show how GPS synchronized clocks at individual nodes can

be used to capture this relation. Such scalar clocks can

eliminate vector clocks [2, 9] that have been used until now

in distributed computing to capture the symmetric relation

between causal precedence and timestamps of events. Then,

in the same section we present the concept of space-time

vectors, enumerate their properties and draw parallels to

Lamport’s logical clock. GPS, which provides a node with

its own space-time co-ordinates, does not provide any infor-

mation about the location of other nodes. We explain how

the space-time vectors can be used to refine a node’s knowl-

edge of the location of other nodes in the system. A pro-

cess

^Pi

can inform another process

^Pj

of its location only

if there exists a chain of messages originating at

^Pi

and ter-

minating at

^Pj

. Processes stamp their own space-time co-

ordinates and also piggyback their latest knowledge of the

space-time co-ordinates of other processes on the outgoing

messages. The location information about other nodes is

imprecise as the recipient is only aware of a node’s location

in the past and it could have moved since then. In Section 5

we describe how the location information, along with times-

tamps can be used to determine the spatial-causal relations

between events. Finally, the conclusions are presented in

Section 6.

(2)

2 The Global Positioning System

The Navstar Global Positioning System (GPS) is funded, designed and controlled by the U. S. Department of Defense [4]. However, there are thousands of civilian users of GPS world-wide.

The GPS constellation provides two basic services: a po- sitioning services and a clock service. Both of them have two distinct classes of quality of services: (i) the Standard Positioning Service (SPS) which is used for civilian pur- poses and (ii) Precise Position Service (PPS) used by mil- itary or selected civilian users specifically approved by the U. S. Government. The PPS predictable accuracy is of the order of centimeters and tens of nanoseconds [4].

The GPS Navigation Message consists of time-tagged data bits marking the time of transmission from the satellite of each subframe. Data frames (1500 bits) are sent every thirty seconds (one bit each 20 msec.). Each frame consists of five subframes. Data bit subframes (300 bits transmit- ted over six seconds) contain parity bits that allow for data checking and limited error correction. The first subframe contains the amount by which the GPS Time is offset from Universal Coordinated Time. This correction can be used by the receiver to set Universal Coordinated Time (UTC) to within 100 ns. All the six subframes contains clock infor- mation bits that allows the receiver to have a high degree of accuracy.

A receiver can compute its position using signals from four distinct GPS satellites. Satellite

ⁱ

’s position,

^(xi

;y

i

;z

i )

can be precisely computed by the receiver using the bits received in a frame despite of relativistic time delays and ionospheric and tropospheric distotions (see [4]).

3 The Computational Model

Mobile Nodes. The system is composed of a set of

ⁿ

in- dependent nodes with the ability to move at a maximum admissible speed

^s¹

. No base station exists to coordinate the activities of subsets of nodes. Due to mobility, a node’s neighborhood changes with time. As the mobility of nodes may not be predictable, changes in network topology over time are arbitrary. Nodes communicates only by exchang- ing messages and all communication is over wireless links.

A mobile node has a link with another mobile node if they are within wireless range of each other. We assume that a single or multiple wireless hop path exists between every pair of mobile nodes. However, these paths may change over time. At the logical level paths corresponds to chan- nels. Each pair of mobile nodes is connected by an asyn- chronous logical channel and transmission delays are finite,

1The maximum admissible speed depends on the underlying network system, e.g., DECT, GSM, PCS, ETACS. For example, in a DECT micro- cellular system^sis less than 40 km/hours (approximately^11m=s). For GSM and PCS systems^sis bounded by maximum highway traffic speeds (about^50m=s).

unpredictable and greater than a minimum transmission de- lay

^Tc

.

Mobile Node Internal Clock. Each mobile node is equipped with an internal clock (e.g. quartz crystal) which has a maximum drift rate,

, with respect to an External Physical Time, EPT, (e.g. atomic time), of

¹⁰ ⁵

. The syn- chronization between the External Physical Time and the internal clock is done every

^t

seconds. So an internal clock of a mobile node may diverge from the EPT by at most

^t

[5]. However, thanks to some compensation techniques, the divergence of the internal clock can actually be bound by

0

t

, where

⁰

.

If each mobile node is equipped with a GPS receiver the maximum drift of a non-faulty internal clock (without any compensation for errors in crystal frequency) with respect to the Universal Coordinated Time (UTC), which acts as EPT, is 0.3 msec as the internal clock is synchronized to UTC each 30 seconds.

Processes. A process is a software entity running on a mo- bile node. We assume, without loss of generality, that there is one process per mobile node. Execution of a process

^Pi

produces a sequence of events

^ei0

;e

i1

;:::e

iw

which can be classified as: send events, delivery events and internal events. An internal event may change only local variables;

send or delivery events involve communication. We assume that the minimum time between two successive events in a process is

^Tp

. Finally, the set of all events produced by all processes is called

^E

. Figure 1 shows the evolution of three processes denoting events as black circles.

Virtual Global Clock. Processes are endowed with a vir- tual global clock, formed by the set of internal clocks one for each mobile node. The virtual global clock is a software representation of the EPT.

Even though all the internal clocks are periodically syn- chronized with the EPT, internal clock values are not ex- actly the same all the time: they differ at most by the clock precision

[12], which represents the maximum difference between any two internal clock values. Indeed, internal clocks of two mobile nodes drifting in opposite directions may diverge by at most

^2t

. The latter value represents the upper bound on

for the virtual global clock.

A virtual global clock is also characterized by its gran- ularity

^g

(the time between two successive ticks). In order to avoid the overlapping of distinct global ticks in different nodes Kopetz introduced the granularity condition stating that the granularity of a global clock must be greater than or equal to the global clock precision (i.e.,

^g

) [6].

Figure 1 shows the global clock tick in a distributed exe- cution as vertical dotted lines when the precision,

, is equal to zero.

When each mobile node is equipped with a GPS receiver

the maximum drift between two internal (non-faulty) clocks

with respect to UTC is 0.6 msec (

²¹⁰ ⁵³⁰

seconds).

(3)

g Pk Pj Pi

0 1 2 3 4 5 6

Figure 1. Execution of events in a syn- chronous 3-process system.

So, the granularity of the virtual global clock can be safely assumed to be of the order of a few milliseconds. Many clock synchronization protocols on wired networks provide a virtual global clock that bounds the value of the sum of the precision and granularity within a few milliseconds (5- 10 msec.) [1, 3, 8, 10]. However, the advantage of using GPS based clock synchronization is that the GPS receiver of a node is a passive listening device, and is not required to send messages to other nodes. This results in substantial energy savings.

Timestamping of Events. Using the virtual global clock, each event

^eiw

of a node is associated with a global time value (timestamp) at which the event occurred. Neverthe- less, granularity and non-zero precision of a virtual global clock could lead to errors like timestamping of two distinct events of a process with the same value or, if communica- tion is involved, the timestamp of the send event of a mes- sage could be greater than or equal to the timestamp of the corresponding receive event. In [12] Verissimo observed that given two events

^a

and

^b

at distinct nodes, timestamped by a global clock with precision

and granularity

^g

, their timestamps reflect their relative temporal ordering only if

T

c

+g

and

^Tp

+g

.

²

With these two basic assumptions, we force each event

^eiw

at a process to have a unique timestamp value, and

^eiw

could potentially affect another event

^ejh

in its future such that

^eiw

occurred before

e

jh

with respect to the global clock value. Here, we denote as

^eih

an event that occurred in process

^Pi

at time

^th

. Fig- ure 1 shows a communication pattern in which each event at each process has a distinct timestamp and communication delay are greater than

⁺^g

.

Let us now state a temporal ordering relation between events, denoted by

. Note that causal order, to be dis- cussed later, implies temporal order, but the converse is not true.

definition 3.1 Let

^eiw

and

^ejh

be two events in

^E

with vir- tual global timestamps of

^tw

and

^th

, respectively. Then,

2Note that this assumption is not strictly necessary. We only need that the time interval between two successive communication events be greater than⁺^g. The reason we use that assumption is to assign an unique timestamp to each event in each process.

e

iw

e

jh

iff

^tw

<t

h

.

Two events

^eiw

and

^ejh

are concurrent if

^:(eiw

e

jh )^

:(e

jh

e

iw

)

. In other words, if two events are concurrent then

^tw

=t

h

. The relation

defines a partial ordering on events

^(E;⁾

.

Positioning Service. Each process may access an internal positioning service provided by the mobile node. In particu- lar, each mobile node is equipped with an internal position- ing system (using GPS, for example) that provides the three basic coordinates X, Y, Z. We assume that all the nodes are at the same elevation. So, without loss of generality, only two coordinates X, and Y of the positioning system need to be considered for location purposes. In particular

^Li

(T)

returns the location of

^Pi

at time

^T

. Overloading the termi- nology a little, we assume that

^Li

(e

iw

)

denotes the location of

^Pi

while executing event

^eiw

at time

^tw

. We assume that each process knows the initial position of every other pro- cess and the minimum distance between two nodes

L

is greater than the accuracy provided by the positioning ser- vice. In other words each node has a distinct location.

4 Spatial-Temporal Ordering

In some applications it is crucial to define a total or- der among the events of a distributed execution. Until now the usual approach has been to order events based on their scalar or vector timestamps, and if two events were mutu- ally concurrent the tie was broken using the identities of the processes on which they occurred. In a mobile application the impact of an event occurring in a process also depends on the location of the process at that time. Therefore, in such systems the total order should be influenced by the lo- cation of a process, as well as by the virtual clock time when the event occurs in the process and the process identity.

For example, let there be a competition for a possibly mobile resource among two processes residing on different nodes, mobile or stationary. Both processes issue a request during the same virtual global clock tick. In some situations a higher priority should be assigned to a request made by the process closer to the resource. In this case a timestamp tie, which defines concurrent events, should be broken by using the distance of the mobile node from the location of the mobile resource.

Let us now introduce the spatial-temporal total ordering of events with respect to a given reference point

^R

located at position

^r

(denoted

r

).

definition 4.1 Let

^eiw

and

^ejh

be any two events belonging to

^E

, and let

^R

be a reference point whose location is

^r

,

e

iw

r e

jh

iff:

(1)

^tw

<t

h

or, (2)

^tw

=t

h

and

^jL(eiw

) rj<jL(e

jh

) rj

or (3)

^tw

=t

h

and

^jL(eiw

) rj=jL(e

jh

) rj

and

ⁱ^<^j

(4)

L(e

i3

)=(1;5) r=(6;5) R P

i

P

k

L(e

k 3

)=(13;3)

X Y

L(e

j3

)=(11;5)

P

j

Figure 2. Positions of the three processes of Figure 1 at virtual global time 3.

Here,

^ja ^bj

denotes the distance between locations

^a

and

^b

. Rule (3) is introduced to order events with the same times- tamp and at the same distance from the reference point. It is easy to see that

r

is a total order and that

⁾ r

. As an example, Figure 2 shows the position of the three pro- cesses of Figure 1 with respect to the reference

^R

located at coordinate

^(6;⁵⁾

at global virtual time 3. Then, we have

e

j3

r e

i3

r e

k 3

.

Space-Time Vectors. We propose to use a space-time vector

^ST

to help determine the spatial-temporal ordering among events. This vector is an extension of the vector clock proposed by Mattern and Fidge [2, 9] and consists of

ⁿ

2-tuples, where

ⁿ

is the number of nodes that we need to track in the system. Each tuple corresponds to (time, lo- cation) information.

Let

^STi [j] =(t

j

;l

j

)

. This means that

^Pi

’s most recent information about

^Pj

corresponds to

^Pj

being at location

l

j

at virtual global clock time

^tj

. The value of

^STi [i]

is always current, while

^STi

[j]

for

^j ⁶⁼ ⁱ

may be outdated.

Initially,

⁸^i; ^j ^: ^STi

[j] = (0; initiallocationof P

j )

. When a node sends a message, the message is stamped with its space-time vector. We refer to this operation as time- location stamping. A space-time vector is updated in the following manner:

1. Periodically, and definitely before sending a message and on receiving a message,

^Pi

sets the value of

^STi

[i]

to be equal to (current time, current location) where these com- ponents are obtained using the virtual global clock and the positioning service.

2. On receiving a message

^m

carrying the time-location stamp

^m^l

,

^Pi

performs the following operation:

8j 6=i:

if

^m^l^[j]:time^>^STi

[j]:time

then replace

^S^Ti [j]

with

^m^l^[j]

. Thus location information about nodes can be propagated through messages.

Note that

^STi

[j]:location

represents the last position of

P

j

known to

^Pi

.

5 Causality in Mobile Systems

Space is also an important aspect to define cause-effect relationship. As an example, let a person be suspected of a crime executed at 10:00 pm and this person has an alibi at 11:00 pm. This person could have committed the crime only if the site of the crime and the alibi site are close enough to be reachable in one hour. Otherwise the person is innocent.

In terms of causality, if the alibi event is included in the fu- ture

^s

cone of causality starting at the crime event, then that person could be a suspect when considering

^s

the maximum speed at which the suspect can move.

Processes may be executing events while moving at a maximum speed of

^s

. This means that if a process

^Pi

exe- cutes an event

^eiw

at time

^tw

, at a later time

^t⁰

the position of

^Pi

is somewhere in a circle centered at

^L(eiw

)

with a di- ameter of

^2s(t⁰ ^tw

)

. From the point of view of a process

P

j

, the uncertainty in the position of

^Pi

will depend on

^Pi

’s event with the highest timestamp that causally precedes an event of

^Pj

(the last event of

^Pi

“seen” by

^Pj

). Let

^eiw

be that event. The last known position of

^Pi

with respect to

^Pj

will then be

^L(eiw

)

. Let us now formally state the concept of uncertainty interval.

definition 5.1 Let

^t⁰

be the clock value at

^Pj

and let

^L(eiw )

be the last known position of

^Pi

with respect to

^Pj

. An un- certainty interval, denoted

^Ij

(e

iw

;t 0

)

, represents the region in which

^Pi

will be positioned from

^Pj

’s viewpoint at time

t

0

, and is equal to a circle centered at

^L(eiw

)

with a radius of

^s(t⁰ ^tw

+2)

.

Let

^eiw

and

^ejh

be two events such that

^eiw

!e

jh

, as shown in Figure 3 (for simplicity this figure is drawn assum- ing a one-dimensional space). At the time of execution of event

^ejh

, process

^Pj

knows that process

^Pi

is somewhere in the uncertainty interval

^Ij

(L(e

iw );t

h

)

. Of course, the larger the difference

^th

t

w

is, the larger the interval will be. Uncertainty can be reduced only if a more recent causal relationship, by means of a chain of messages, is established between an event of

^Pi

(later than

^eiw

) and an event of

^Pj

(later than

^ejh

).

definition 5.2 A process

^Pi

could be within distance

^d

of process

^Pj

at time

^t⁰

(from

^Pj

’s viewpoint), denoted

^Pi

d;t 0

u

P

j

, if

^I(L(eiw );t

0

)

and a circle centered at

^Lj (t

0

)

with ra- dius

^d

intersect.

The non-intersection of the two circles rules out the pos- sibility of the two processes being within distance

^d

of each other. However, the intersection between the two circles does not always imply that the two processes are within dis- tance

^d

of each other at time

^t⁰

. If

^I^(L(eiw

);t 0

)

is entirely within the circle with center

^Lj

(t 0

)

and radius

^d

then the two processes are definitely within distance

^d

of each other.

Figure 3 shows an example in which

^:(Pi d;th

u P

j )

. We

are now in the position to introduce the spatial-causality

(5)

X

t L(e

jh ) L(eiw)

eiw

tw th

Ij(ejh;d) e

jh I

j (e

iw

;t

h )

Figure 3. Distance between process

^Pj

and

^Pi

at time

^th

(case greater than

^d

).

relation among events denoted

^!^d;t

. This relation is based on the happened-before relation ([7]) with the addition of a spatial dimension:

definition 5.3 Let

^d

be an integer,

^t

an instant of time and

e

iw

and

^ejh

be two events in

^E

,

^eiw d;t

!e

jh

iff:

(1)

^eiw

!e

jh

, and (2)

^Pi

d;t

u P

j

It is interesting to observe that the structure of the par- tial order defined by the relation

^!^d;t

changes with time (i.e., events which are concurrent with respect to

^d;t^!

can be re- lated by

^d;t

0

!

, with

^t ^<^t⁰

, and vice versa). For example, in Figure 3,

^eiw

is concurrent with

^ejh

at time

^th

with respect to the

^d;t^!^h

relation even though

^eiw

!e

jh

. In other words, a causal relation can be hidden to the spatial-causality rela- tion for certain periods of time. It takes time for causal re- lations to propagate. Such relations become visible only if processes are close enough and/or enough time has elapsed.

A Property of Space-Time Vectors. According to prop- erties of Mattern-Fidge vector times [2, 9], we have:

^eiw

!

e

jh

iff

^STiw

<ST

jh

where

^STiw

is the space-time vector associated with event

^eiw

, and

STiw<ST

jh ,

(8`) :: ST

iw

[`]:timeST

jh [`]:time

and

9y : ST

iw

[y]:time<ST

jh [y]:time

Hence, we can show that:

e

iw d;t

!e

jh

iff

^STiw d;t

<ST

jh

where

STiw d;t

<STjh , ST

iw

<ST

jh

and

Pi d;t

u Pj

6 Conclusion

Clock synchronization through message passing is an ex- pensive operation and does not scale well. We have pro- posed using the Global Positioning System to accurately de- termine time, and to keep the local clocks of participating nodes in synchrony with each other. This does not require any message transmission by the mobile nodes and is en- ergy efficient.

We have also introduced the concept of space-time vec- tor to track the mobility of nodes. Using this vector nodes can prioritize resource requests on the basis of request time as well as the requester’s distance from the resource. Due to lack of space the interested reader may refer to [11] for the description of two distributed mutual exclusion algorithms that employ the space-time information.

References

[1] K. Arvind. Probabilistic Clock Synchronization in Dis- tributed Systems. IEEE Transactions on Parallel and Dis- tributed Systems, 5(5):474–487, May 1994.

[2] C. Fidge. Logical time in distributed computing systems.

IEEE Computer: 28–33, August 1991.

[3] R. Gusella and S. Zatti, The accuracy of the clock synchro- nization achieved by TEMPO in Berkeley UNIX 4.3BSD, IEEE Transactions on Software Engineering, 15(7):847–

853, 1989.

[4] Hoffmann-Wellenhof, B. H. Lichtenegger, and J. Collins.

GPS: Theory and Practice. 3rd ed.New York: Springer- Verlag, 1994.

[5] H. Kopetz and W. Ochsenreiter, Clock synchronization in distributed real-time systems, IEEE Transactions on Com- puters, (8):933–940, 1987.

[6] H. Kopetz. Sparse Time versus Dense Time in Real-Time Systems, Proc. ICDCS’92, 460–467, 1992.

[7] L. Lamport. Time, Clocks and the Ordering of Events in a Distributed System. Communications of the ACM, 21(7):558–565, July 1978.

[8] L. Lundelius and N. Lynch. An Upper and Lower Bound for Clock Synchronization. Inform. Control, 62:190–204, 1984.

[9] F. Mattern. Virtual time and global states of distributed sys- tems. In Proceedings of the International Workshop on Par- allel and Distributed Algorithms, LNCS series, pages 215–

226, North Holland, 1989.

[10] A. Olson and K.G. Shin. Fault-Tolerant Clock Synchroniza- tion in Large Multicomputer Systems. IEEE Transactions on Parallel and Distributed Systems, 5(9):912–923, September 1994.