Narugn is a lightweight distributed computer, composed by one or more cells that are connected locally.


Each cell in the Narugn cluster is a PostgreSQL database, and runs on top of a Narugn cell server, which is a PostgreSQL database server running on a GNU/Linux host.

The Narugn cluster is distributed, in the sense that there is no hierarchy between cells: the user interacts via any cell.

The Narugn server is locally connected: each server talks only with neighbouring servers. Therefore a Narugn cluster can have a large number of cells, connected by a large number of small networks.


The Narugn cluster is accessed via a standard PostgreSQL connection, so it can be used from the command line, as well as by an application.

The function

execute_sync ( cell_function IN text , payload VARIADIC text[] DEFAULT '{}' , c OUT cds , z OUT bigint , dt OUT interval , output OUT text ) RETURNS SETOF RECORD

crawls the currently known cells, executes the given cell function on each cell, and then return the results. An optional variadic payload can be specified, and will be transmitted to the cell function. An absolute version "execute_sync_abs" is available, where dt is replaced by a timestamp "t".

The function named in "cell_function" must be a Narugn cell function; "cell_" will be prepended to its name. For example, by specifying cell_function := "ping" the following function will be used:

CREATE OR REPLACE FUNCTION cell_ping ( payload IN text[] , walked IN cdt[] , z OUT bigint , t OUT timestamp with time zone , output OUT text ) RETURNS SETOF RECORD

All the cell functions have the same input and output parameters.

The second input parameter "walked" is the path that has been walked from the starting cell to reach that cell. It is provided to the cell function, in case it is needed (e.g. traceroute). The "cdt" data type contains a pair of cell coordinates and a timestamp with time zone.

The output of execute_sync is a set of rows, union of all the sets of rows produced by each cell. The first column separates cells, while the other columns come directly from the cell function:

c : cds = coordinates of the cell that produced this row z : integer = order of this row among rows produced by this cell t : timestamp with time zone = when the row was produced output : text = contents of the row


narugn_cell_3_7=# SELECT * from execute_sync('version'); c | z | t | output
-------+---+-------------------------------+--------------------------------------------------------------------------------------- (3,7) | 1 | 2012-07-05 13:40:52.254033+01 | PostgreSQL 9.1.4 on i686-pc-linux-gnu, compiled by gcc (Debian 4.7.0-9) 4.7.0, 32-bit (3,7) | 2 | 2012-07-05 13:40:52.254255+01 | Narugn 0.1.0 (3,8) | 1 | 2012-07-05 13:40:52.280048+01 | PostgreSQL 9.1.4 on i686-pc-linux-gnu, compiled by gcc (Debian 4.7.0-9) 4.7.0, 32-bit (3,8) | 2 | 2012-07-05 13:40:52.280127+01 | Narugn 0.1.0 (4,8) | 1 | 2012-07-05 13:40:52.346649+01 | PostgreSQL 9.1.4 on i686-pc-linux-gnu, compiled by gcc (Debian 4.7.0-9) 4.7.0, 32-bit (4,8) | 2 | 2012-07-05 13:40:52.347096+01 | Narugn 0.1.0 (4,7) | 1 | 2012-07-05 13:40:52.28376+01 | PostgreSQL 9.1.4 on i686-pc-linux-gnu, compiled by gcc (Debian 4.7.0-9) 4.7.0, 32-bit (4,7) | 2 | 2012-07-05 13:40:52.283852+01 | Narugn 0.1.0 (8 rows)


At present there are no privileges or user profiles. The distributed nature of the Narugn cluster requires a separate analysis before introducing such notions.

Cluster, Server, Cell

A Narugn cell is a PostgreSQL database satisfying certain conditions. Each cell is endowed with a pair of (integer) global coordinates. Each cell belongs to a Narugn server (see below). There is an adjacency notion between cells, encoded in the Narugn location graph.

A Narugn server is a PostgreSQL database server, hosting zero or more Narugn cells. For each server S there is a polygon p(S). If a server hosts a cell (x,y), then (x,y) is contained inside p(S). Each server belongs to a cluster. Two servers S1, S2 are said to be adjacent if there are cells (x1,y1) in p(S1) and (x2,y2) in p(S2) such that (x1,y1) is adjacent to (x2,y2).

A Narugn cluster a collection C={S_1,...,S_k} of one or more Narugn servers, satisfying two conditions:

  1. (connected) for each i there is j such that S_i is adjacent to S_j;

  2. (disjoint) for each distinct i and j, S_i does not overlap with S_j.

Various operations can be performed on clusters, provided that the result is a valid Narugn cluster. For example:

  1. Cluster sum

    { S_1, ..., S_k } + { T_1, ..., T_h } = { S_1, ...., S_k, T_1, ..., T_h };

  2. Cluster difference (assuming a <= k <= b)

    { S_1, ..., S_k } - { S_a, ..., T_b } = { S_1, ...., S_(a-1) };

At present, cluster difference is not implemented, while cluster sum is implemented via the "connect" API call.


Each cell has integer global coordinates (x,y).

The polygon of a cell server has real coordinates, and lies in the (x,y) plane.

The incidence relation between points (cells) and polygons (servers) determines which server hosts a given cell. In particular, different server must have disjoint polygons.

There is a "cell location" graph whose vertices represent possible cells, and whose edges represent connections. The actual cluster is an induced subgraph.

The chosen cell location graph is a square tiling of the plane such that cell (x1,y1) is connected to cell (x2,y2) iff

{|x1-x2|,|y1-y2|} = {0,1}.

Extension / State / Logic

The contents of each cell database are divided in three groups: * Extension * State * Logic


The core Narugn code is Extension, and does not change frequently; every other object is either Logic or State.

Each change of the extension code requires a new extension version number, plus EXTENSION UPDATE scripts from all the previous versions which are supported. An EXTENSION UPDATE must preserve the state and the logic.

The purpose of the Extension code is to allow basic management of the Narugn cluster. This includes propagation of updates to the Logic code across the cluster, ensuring that the State is preserved under such updates. All the code that does not serve this purpose has been moved to Logic.

The Narugn Extension API is composed by five calls:

  • rescan
  • ping
  • version
  • logic
  • connect
  • state_table, state_sequence

The "rescan" call refreshes the notion of neighbours of each reachable cell, and does so for each discoverable cell.

The "ping" call is the simplest possible Narugn operation; each cell just returns 'OK'.

The "version" call returns version numbers for the OS, PostgreSQL and Narugn.

The "logic" call replaces the existing logic with the given one.

The "connect" call merges two clusters into a bigger cluster.

The "state_table" and "state_sequence" calls can be used to mark State objects.

Logic, State

The Logic code is not contained in the extension, nor generated automatically. A new version of the Logic code is propagated by Narugn like any other function execution, via the "logic" Extension API call. Updates are performed only when the new version of the Logic source code is different from the current one (Narugn stores the md5 of the currently installed Logic source code).

The author of Logic can use state_table() and state_sequence() to mark State objects as such. Contents of State objects are automatically preserved under Logic updates.

Note. Sequences are not really preserved under Logic updates; they are bumped by one, which is good enough for all purposes (since sequences are not guaranteed not to have gaps).

See also

doc/ for a guided tour.


Gianni Ciolli

Copyright and License

Copyright (c) 2012 Gianni Ciolli Distributed under the terms of the GNU General Public License v3: