[Home]GDTL/Trade-Offs

BOOST WIKI | GDTL | RecentChanges | Preferences | Page List | Links List

Difference (from prior major revision) (minor diff, author diff)

Changed: 3c3
GDTL does its best to provide everything a user could want, but there are certain inherent constraints that limit what any temporal library can do. Specifically, a user much choose which two of the following three capabilities are desired in any particular application:
GDTL does its best to provide everything a user could want, but there are certain inherent constraints that limit what any temporal library can do. Specifically, a user must choose which two of the following three capabilities are desired in any particular application:

Added: 31a32
<html>

Changed: 38c39

<p>

Changed: 41c42

<p>

Changed: 44c45

<p>

Changed: 49c50

<p>

Changed: 53c54
For each xi, there must be a time ti and a value v
For each x<sub>i</sub>, there must be a time t<sub>i</sub> and a value v

Changed: 55,57c56,62
* v = true or v = false, and
* for all t < ti, is_member( xi, t ) returns dont_know, and
* for all t >= ti, is_member( xi, t ) returns v.
<ul>
<li>v = true or v = false, and
<li>for all t < t<sub>i</sub>, is_member( x<sub>i</sub>, t ) returns dont_know, and
<li>for all t >= t<sub>i</sub>, is_member( x<sub>i</sub>, t ) returns v.
</ul>
t<sub>i</sub> is thus the time when we "find out" whether x<sub>i</sub> is a
member of T.

Changed: 59,60c64,65

If for all xi, ti = negative infinity,
<p>
If for all x<sub>i</sub>, t<sub>i</sub> = negative infinity,

Changed: 62,63c67,68

If for some xi, ti = positive infinity,
<p>
If for some x<sub>i</sub>, t<sub>i</sub> = positive infinity,

Changed: 65c70

<p>

Changed: 67,68c72,73
implies that for some xi, ti is finite).

implies that for some x<sub>i</sub>, t<sub>i</sub> is finite).
<p>

Added: 73a79
</html>

Changed: 120c126
If you are working in a domain that uses 'physical durations' exclusively and events do not depend on civil clock measurements than a TAI based system is highly recommended. TAI has complete stability w.r.t calculation and storage and can be converted back to utc or local times on demand.
If you are working in a domain that uses 'physical durations' exclusively and events do not depend on civil clock measurements then a TAI based system is highly recommended. TAI has complete stability w.r.t calculation and storage and can be converted back to utc or local times on demand.

Unavoidable Trade-offs

GDTL does its best to provide everything a user could want, but there are certain inherent constraints that limit what any temporal library can do. Specifically, a user must choose which two of the following three capabilities are desired in any particular application:

Some libraries may implicitly promise to deliver all three, but if you actually put them to the test, only two can be true at once. This limitation is not a deficiency in the design or implementation of any particular library; rather it is a consequence of the way different time systems are defined by international standards. Let's look at each of the three cases:

If you want exact agreement with wall-clock time, you must use either UTC or local time. If you compute a duration by subtracting one UTC time from another and you want an answer accurate to the second, the two times must not be too far in the future because leap seconds affect the count but are only determined about 6 months in advance. With local times a future duration calculation could be off by an entire hour, since legislatures can and do change DST rules at will.

If you want to handle wall-clock times in the future, you won't be able (in the general case) to calculate exact durations, for the same reasons described above.

If you want accurate calculations with future times, you will have to use TAI or an equivalent, but the mapping from TAI to UTC or local time depends on leap seconds, so you will not have exact agreement with wall-clock time.

Stability, Predictability, and Approximations

Here is some underlying theory that helps to explain what's going on. Remember that a temporal type, like any abstract data type (ADT), is a set of values together with operations on those values.

Stability

The representation of a type is stable if the bit pattern associated with a given value does not change over time. A type with an unstable representation is unlikely to be of much use to anyone, so we will insist that any temporal library use only stable representations.

An operation on a type is stable if the result of applying the operation to a particular operand(s) does not change over time.

Predictability

Sets are most often classified into two categories: well-defined and ill-defined. Since a type is a set, we can extend these definitions to cover types. For any type T, there must be a predicate is_member( x ) which determines whether a value x is a member of type T. This predicate must return true, false, or dont_know.

If for all x, is_member( x ) returns either true or false, we say the set T is well-defined.

If for any x, is_member( x ) returns dont_know, we say the set T is ill-defined.

Those are the rules normally used in math. However, because of the special characteristics of temporal types, it is useful to refine this view and create a third category as follows:

For any temporal type T, there must be a predicate is_member( x, t ) which determines whether a value x is a member of T. The parameter t represents the time when the predicate is evaluated. For each xi, there must be a time ti and a value v such that:

ti is thus the time when we "find out" whether xi is a member of T. Now we can define three categories of temporal types:

If for all xi, ti = negative infinity, we say the type T is predictable.

If for some xi, ti = positive infinity, we say the type T is ill-formed.

Otherwise we say the type T is unpredictable (this implies that for some xi, ti is finite).

Ill-formed sets are not of much practical use, so we will not discuss them further. In plain english the above simply says that all the values of a predictable type are known ahead of time, but some values of an unpredictable type are not known until some particular time.

Stability of Operations

Predictable types have a couple of important properties:

The practical effect of this is that duration calculations can be implemented with simple integer subtraction. Examples of predictable types are TAI timepoints and Gregorian dates.

Unpredictable types have exactly the opposite properties:

Examples of unpredictable types are UTC timepoints and Local Time timepoints.

We can refine this a little by saying that a range within an unpredicatable type can be predictable, and operations performed entirely on values within that range will be stable. For example, the range of UTC timepoints from 1970-01-01 through the present is predictable, so calculations of durations within that range will be stable.

Approximations

These limitations are problematical, because important temporal types like UTC and Local Time are in fact unpredictable, and therefore operations on them are sometimes unstable. Yet as a practical matter we often want to perform this kind of operation, such as computing the duration between two timepoints in the future that are specified in Local Time.

The best the library can do is to provide an approximation, which is generally possible and for most purposes will be good enough. Of course the documentation must specify when an answer will be approximate (and thus unstable) and how big the error may be. In many respects calculating with unpredictable sets is analogous to the use of floating point numbers, for which results are expected to only be approximately correct. Calculating with predictable sets would then be analagous to the user of integers, where results are expected to be exact.

For situations where exact answers are required or instability cannot be tolerated, the user must be able to specify this, and then the library should throw an exception if the user requests a computation for which an exact, stable answer is not possible.

 - msk

It is important to note that there are a subset of problems that involve calculations involving 'actual durations' or 'physical durations' in which correct calculations can be performed. However, storing these results can result in errors. For example in the plane flight scenario the beginning time of the flight is a local time adjusted according to the rules of the locality including timezones and daylight savings times. This time is 'stable' when stored as year-month-day hour-minute-second because if UTC leapseconds are adjusted we want this time to change to when the clock in the local zone reads the given departure time. (Note, that the airline will need to re-evaluate the departure times if something radical such as DST rule changes are introduced; they might now want to change the local departure time). Regardless, the duration of the flight is obviously unaffected by changes to local clocks, so the derivation of local arrival time can always be derived by converting the departure time to UTC, adding the flight duration, and converting to the local destination time. The problems start if the arrival time is stored. Changes to rules with either departure or arrival timezone/DST regulations will invalidate the results of the stored calculations and hence result in errors. Thus in this case it is advised not to store the results of the calculation but rather the departure time and the duration rederiving the arrival time as needed.

If you are working in a domain that uses 'physical durations' exclusively and events do not depend on civil clock measurements then a TAI based system is highly recommended. TAI has complete stability w.r.t calculation and storage and can be converted back to utc or local times on demand.


BOOST WIKI | GDTL | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited October 12, 2002 9:48 am (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers