Global Ordering Note.

Abstract

Push Logic and Tuple Space computation both require a global partial order to be constructed and maintained on the fly. This ordering constrains both code and data to be organised in a global DAG (directed acyclic graph). A distributed protocol based on insertion sort is used to maintain the ordering. This note looks at its efficiency, suitability for embedding in ubiquitous devices and its security against denial of service attacks.

Details

The global ordering protocol assigns objects a negative integer called level. Objects are arranged as nodes in a DAG (directed acyclic graph) such that none points to another object with higher level. Strongly connected components (SCCs) of equal level are allowable when desired.

Negative integers are chosen since they are more intuitive and it aids explanation. A higher level number is one closer to the top of the DAG, whereas leaves will have the lowest (most negative) values.

The essence of the protocol is that the highest layers are held by trusted agencies that make infrequent updates, whereas the lower layers are localised and are happy to bear the cost of their own insertions when necessary.

This note is written with the assumption that all wire protocols will be 'future proof' in allowing unlimited negative integers to be used to express levels and suggests how a 33 bit number space may be sensibly used to start with. Further, cliques of low-cost embedded devices are expected to use a small cluster of adjacent level numbers, and so a wire protocol that allows a compressed representation of this is preferable, especially if it can be leveraged to reduce RAM use in the devices.

Level Allocation

In the long run, the primary naming agencies (w3c and dns and so on) will effectively own all of the highest level numbers, from zero down to say -32768. ISPs and other service providers that can be expected to behave responsibly will own the following numbers down to -65535. Private domains will use the numbers from 64K downwards, probably in a compact or clustered way. However, we present the protocol without reference to these practical aspects.

Where a new object is created in vacuo (which is totally unlikely in reality) it is free to chose any level number. When the first link is established between two objects, or disjoint subgraphs, the originator of the link (upper component) sends it level number to the referenced object. If the referenced object is currently at a higher (or equal) level, then it must decrease its level number accordingly. We call this a pushdown. The referenced object chooses an amount to pushdown by. Before reducing its own level, an object must pushdown all those ojects it references that have insufficient level gap. This can take some time, which is the main potential downside of this protocol, but the frequency of this is minimised by choosing suitable pushdown gaps to start with. When the referenced object has pushed down, as necessary, its referenced objects, it can set its new level and report back to its new parent, to complete the process. Although we are envisaging a distributed system with millions of embedded devices hosting billions of objects, the number of levels in practical trees is expected to make sparse use of a 33 bit number space.

How to ensure there are no loops ? When an object attempts to reference another object that is its own parent, it will have to attempt a pushdown of that object, which in turn will cause it to experience a pushdown. Every pushdown message contains a 64 bit nonce and when an object receives a request for pushdown that contains a nonce it has used in a currently outstanding locally generated pushdown, then it can detect the loop and reply with failure. Provided a node does not commit its own new level until all consequentially required pushdowns have reported success, no level changes will be committed. This is tolerant to concurrent pushdowns from different sources.

In practice, major service providers will not process pushdown messages from untrusted clients, using a firewall or other overlay protection mechanism. In addition, pushdown messages may optionally contain a secure access capability using RSA or similar that denies access. These protection mechanisms are necessary to prevent denial of service attacks, where a malicious entity sends frequent pushdowns that gradually erode the number space, but they would not be necessary otherwise, given the assumptions on total number of levels really needed.

White Paper

A white paper with further details and analysis will be added here.