Home. Help index. Up.
A Logiweb server state is a rooted tree. For each node of a server state, edges of the node that point in the direction of the root are termed "ascending" edges of the node and the other ones are termed "descending". The root has no ascending edges and all other nodes (if any) have exactly one.
Edges of a server state are labeled 0 or 1. A descending edge of a node is a "left" or a "right" edge of the node if the edge is labelled 0 or 1, respectively. All nodes of a server state have at most one ascending edge, at most one left edge, and at most one right edge.
The list of edge labels of the path from the root to a node N is said to be the "address" of N. In particular, the address of the root itself is the empty list.
Nodes of a server state are labelled by "attribute functions". The domain of an attribute function is finite and consists of cardinals. The range of an attribute functions consists of "attribute lists".
An attribute list is a list of pairs of timestamps and "attributes". Attribute lists must be sorted chronologically with the oldest timestamp first. Some attribute lists are required to be "strictly chronological" in the sense that no two timestamps of the list are allowed to represent the same time instant.
Whenever attributes are added to an attribute list, they are added to the end of the list with the current Logiweb time as timestamp. Whenever an attribute is removed from an attribute list, it is removed without permuting the other attributes.
Among other, timestamps make it very efficient to do incremental mirroring of the state of a Logiweb server.
If a node N is labelled by an attribute function f and if n is in the domain of f, then f(n) is an attribute list. The j'th attribute of that list will be referred to as the "j'th attribute of N of type n", the oldest attribute having j=1.
The newest attribute of type n is the q'th attribute where q is the length of the the attribute list f(n). The newest attribute, however, may also be referred to as the 0'th attribute of type n or as the p'th attribute for all p>q.
Attributes may retrieve the attributes of a server state using attribute requests.
Layer 0 of the Logiweb protocol allows attributes to have type n for all cardinals n. The Logiweb server, however, merely stores attributes of type 0, 1, 2, 3, 4, and 5. The present implementation of the server does not even support attributes of type 4.
If a node has no left subtree, then the node has no attributes of type 2. Otherwise, the node has exactly one attribute of type 2 and that attribute equals the left subtree. The timestamp of the attribute equals the server time for which the left subtree was last changed. Attributes of type 2 are referred to as "left" attributes.
Attribute type 3 is analogous to type 2 but concerns the right subtree of the node. Attributes of type 3 are referred to as "right" attributes.
Attributes of type 5 are uniform resource locators (urls) represented as byte vectors. Attributes of type 5 of a node N are urls of Logiweb pages whose reference equals the address of N. The timestamp of an url indicates the server time when the url was added to the state. Attributes of type 5 are referred to as "url" attributes. The url attribute list is required to be strictly chronological to allow future extensions of the Logiweb layer 0 protocol in which url attributes are referenced by timestamp.
Logiweb servers perform their main task - translating a reference R to an url U - by looking up an url attribute of the node with address U.
Any node has exactly one attribute of type 1. That attribute is a cardinal stored as a little endian byte vector. The attribute is 0 (i.e. the empty byte vector) if the node has no left, right, or url attributes. Otherwise, the attribute is 1 (i.e. a byte vector of length 1 whose sole byte has value 1).
Attributes of type 1 are referred to as "node type" attributes. A node whose node type attribute is empty is referred to as a "leaf" node, and other nodes are referred to as "proper" nodes. Proper nodes must have a left and a right attribute but needs not have url attributes.
Attributes of type 4 are referred to as "sibling" attributes and are unsupported by the present implementation of the server.
Logiweb servers should be cooperate on maintaining a world-wide catalog of all Logiweb pages. Unfortunately, the current implementation of the server merely indexes pages it has direct access to.
The intension of sibling attributes is described in the following.
If server S has a proper or leaf node N with address A, then the sibling attributes of node N should be urls of servers that have proper nodes with address A.
All servers must cooperate on maintaining sibling pointers such that one can reach all Logiweb servers that have a proper nodes N with address A by following sibling links from any server with a node with address A.
In particular, all servers have a root node. We require the root node to be a proper node. Following sibling links of proper nodes one should be able to reach all Logiweb servers there are.
As mentioned, when a Logiweb server translates a Logiweb reference R to an url, it first looks up the node with address R. The server does so by starting at the root and then moving along left and right edges as directed by the bits of R. During that process, the server may reach a leaf node in which case the server is unable to translate the reference. If the leaf node has no siblings, then the server reports that the reference cannot be translated. But if the leaf node does have siblings, then the server refers the request to one of the siblings.
Attributes of type 0 are cardinals stored as little endian byte vectors. Each cardinal equals an attribute type and the associated time stamp equals the server time the attribute list of the given type was last modified. Attributes of type 0 can have one of the values 1, 2, 3, or 5 in the present implementation of the server. Attributes of type 0 are referred to as "update" attributes.
Whenever the attribute list of type n (for some n>0) is modified, the change is noted in the update attribute list. That gives rise to a change of the update attribute list itself, but the latter change is not noted in the update attribute list.
If an attribute list of type n (for some n>0) becomes empty, then the change can be noted in one of two ways. Either, an update attribute with value n is created with the current server time as timestamp, or the update attribute with value n is deleted and an update attribute with value 0 is created with the current server time as timestamp. The present server implementation never uses the latter option and, hence, update attributes cannot have value 0.
To do incremental mirroring of a server state, one should first look up attribute 0 (the last attribute) of type 0 to see if anything has changed since last. If so, then one should read attributes of type 0 in reverse chronological order until one knows which attribute types have changed since last.
If attributes of type 2 or 3 have changed since last then one should traverse the left and right subtrees, respectively.
If attributes of other types have changed since last then one should read their associated attribute lists in reverse chronological order until all changes are found.
Each attribute has a timestamp and an index. Whenever an attribute is deleted from an attribute list, all indices of newer attributes are decremented. When reading an attribute list in reverse chronological order one may get the same attribute twice in case an older attribute is deleted simultaneously. Furhtermore, if an attribute has unchanged index since last, then one can be sure that no older attributes have been deleted.
Changing an attribute is done by deleting the old value and adding a new value. The new value will get a timestamp different from the old one.
Logiweb time is strictly increasing. Two different updates of a server state must have different timestamps. But a single update that affects several attributes do have the same timestamp.
Logiweb time can have arbitrary resolution. For that reason, there are no problems requiring Logiweb time to be strictly increasing.
Klaus Grue, GRD-2004-08-03