The Netfarm Book

The Cooperative of pplied Language

July 24, 2020

Contents

 0.1 Introduction
  0.1.1 “Abstract”
  0.1.2 How Netfarm deviates from existing designs
  0.1.3 The structure of Netfarm
  0.1.4 Thanks
  0.1.5 What to do next
1 Conventions
 1.1 Block structure
 1.2 Set specifiers
 1.3 Strings
 1.4 Integers
2 decentralise2
 2.1 Systems
  2.1.1 Database protocol
  2.1.2 Synchronisation protocol
  2.1.3 Leader loop protocol
  2.1.4 Tuning the standard-system
 2.2 Acceptors
  2.2.1 Acceptor protocol
  2.2.2 Threaded acceptors
 2.3 Connections
  2.3.1 Connection types
  2.3.2 Threaded connections
  2.3.3 Netfarm wire format connection
  2.3.4 Netfarm binary connection
 2.4 Messages
  2.4.1 Built in message types
  2.4.2 Defining message types
  2.4.3 Translators
3 Netfarm
 3.1 External formats
  3.1.1 Vague objects
  3.1.2 Character format
  3.1.3 Binary format
 3.2 The client
4 Netfarm script machine
 4.1 Presentations
A A description of a voting-web system
B A history of Netfarm
C Index
 Listings
Bibliography

0.1 Introduction

0.1.1 “Abstract”

Netfarm is an attempt at creating a distributed, trustless object system. We develop Netfarm to fill a perceived void in the rapidly-expanding “decentralisation” bubble, to utilise the greater fault tolerance of a distributed hash table and simplify programming via a client language’s meta object protocol, and to devise less hierarchical moderation techniques that do not leave them at the whim of their servers’ operators and administrators.

The design of Netfarm is not ideal due to historical and planning issues; but it should serve well as an introduction to trustless object systems, which we believe can be easier to program and have better throughput than some of the models that are used frequently today, such as blockchains (demonstrated to be usable for programming in Ethereum) and various federated protocols (such as ActivityPub, notably used in Mastodon among other “fediverse” blogging servers).

0.1.2 How Netfarm deviates from existing designs

Some of these points are made redundant by the preceding paragraphs, but it may be worthwhile to explain why we made those claims, and why they are desirable.

0.1.3 The structure of Netfarm

We see the Netfarm system as a synthesis of various components:

However, a user should be able to modify and use any component separately, and should have extensive control over many aspects of the system, to implement any changes while still acting as a “client” of the system, that does not modify the system itself.

0.1.4 Thanks

We would like to thank Luke Nuttall1 for providing a drawing of the Netfarm mascot Demeter.

We would also like to thank Robert Strandh for providing advice on optimising the Netfarm script machine and how Netfarm should interact with client code, and Gilbert Baumann for also suggesting optimisations for the script machine and several stylistic concerns, among other many other insightful discussions.

0.1.5 What to do next

The boundaries that separate a Netfarm implementation and its host language are not yet clear. Several questions remain, such as how much a Netfarm node must know about the data it is verifying, and what it is expected to do for its clients.

We forsee that a new distributed object system will have to be created, to overcome flaws that were introduced to Netfarm through its age and attempts to persue multiple goals. One such problem was that we chose the means of interaction with the network to be sending and receiving data, which creates an awkward split in mechanisms, between the creation of an object and objects sending messages to each other.

As such, we would like to remind the reader that they should take care to form their own opinions on how such a system should be structured from any problems they have noticed, and that Netfarm is not the end-all of distributed object systems. We would hope for something like Pierre-Joseph Proudhon’s dream in this quotation:

Je rêve une société où je serai guillotiné comme conservateur.

(I dream of a world in which I would be executed as a reactionary.)

We hope the approach we have developed for Netfarm, of identifying and constructing alternatives to many forms of centralisation, will be commonplace and we will be the ones developing centralised systems.

Chapter 1
Conventions

1.1 Block structure

A “block” in decentralise2 is represented in two ways, depending on how it is used:

multiple-value-call can be used to convert from the second representation to the first, but there are currently no reasons why that should be useful.

1.2 Set specifiers

The interesting set and uninteresting set for a decentralise2 system are represented as predicates, which usually should not change.

When the interesting set must be changed, the system is notified using a function which takes two set specifiers. A set specifier is either:

The latter is very useful when sets are almost “infinite”, such as in a distributed hash table where the change (from “rehashing” some types of distributed hash tables, or the operator deciding they can commit to storing more objects) can well exceed 2100, and is impractical to represent as a pair of lists.

1.3 Strings

Strings are always encoded using UTF-8 in the Netfarm systems. No buts, no ifs there. The sequence of code points used to form a string must be preserved in encoding and decoding.1

1.4 Integers

Integers are encoded in binary data in big endian format, i.e. such that the most significant octet (or other unit) is written first, and the least significant is written last. This format is most common in networking applications, and is the most convenient for users of human languages that write left-to-right to read.

Octet vectors are written in hexadecimal, with the first octet to be written or read appearing at the leftmost position in a vector, and the last at the right.

For example, 10 01 is the vector consisting of the octets 16 and 1, and can be interpreted as the integer 4097.

Chapter 2
decentralise2

The first component that was developed for Netfarm was the decentralise1 library, which allows a programmer to implement some kind of distributed network by writing the components that they are most interested in, and using provided implementations of the components they are not interested in writing.

A decentralise user may implement one or more of:

2.1 Systems

A system handles the requests sent to a node in a distributed system, and sends requests for blocks it has not yet retrieved to synchronise itself. A block is a tuple consisting of a name, version, channel set, and some data; of which the metadata can be used by a system to determine what it must retrieve and update.

system [Protocol Class]

The protocol class for a system. A system is maintained by some maintenance threads. One of which is the leader thread, which runs a leader loop that schedules requests for synchronisation and stops itself when the system is stopped.

TODO: The standard-system should track maintenance threads like it tracks the leader thread, and eventually, this should all be integrated into the bailout thread supervision library.

standard-system [Class]

A system that uses the database and synchronisation protocols to implement the basic behaviour of a node.

echo-system [Class]

A silly system that responds to any messages other than invalid syntax with the message sent.

:id [Initarg]

system-id system [Generic Function]

The ID of a system, as an integer in the range [0,2256)

:acceptors [Initarg]

The acceptors of a system.

2.1.1 Database protocol

The database protocol is part of the system protocol, because a system may process the data sent over the wire into some other format that should be stored and serialised by some other protocol. For example, the Netfarm system implements get-block in terms of netfarm-system:get-vague-object, and provides the rendered vague object and all the object names that affected it via computed values.

It is possible to separate the synchronisation and database protocol implementations, and combine them into a complete system implementation using multiple inheritance when using the reference implementation:

Listing 2.1: Using multiple inheritance to create a system
(defclass foobar-sql-database () 
  ((database-host :initarg :host 
                  :reader foobar-database-host) 
   ...)) 
 
(defclass my-system 
  (decentralise-system:standard-system 
  foobar-sql-database) 
  ()) 
 
(defvar *system* 
 (make-instance my-system 
  ; an initarg for FOOBAR-SQL-DATABASE 
  :host "sql-server.local" 
  ; an initarg for STANDARD-SYSTEM 
  :concurrent-requests 20))

memory-database-mixin [Class]

The simplest database implementation, which stores block data in a concurrent hash table.

not-found [Condition]

A condition type that is raised when get-block or get-block-metadata are called with the name of a block that is not stored by the system.

The following generic functions must be implemented by a database:

get-block system name [Generic Function]

Return block structure for the block named name from the system, or signal a condition of type not-found.

put-block system name version channels data [Generic Function]

Store a block with the provided block structure in the system, or signal a condition of type error.

map-blocks function system [Generic Function]

Call function repeatedly with block structure for the metadata of every object in the system.

get-block-metadata system name [Generic Function]

Return block structure for the metadata of the block named name from the system, or signal a condition of type not-found.

This generic function will be called for each block’s metadata sent to a system, so adding a method which does not have to load a block’s data is highly recommended. Otherwise, for the implementors’ convenience, the following method will be used:

get-block-metadata (system system) name [Method]

The default method for get-block-metadata calls get-block, and returns the metadata from the data it retrieved, but implementations which are even slightly concerned with efficiency should implement a method for get-block-metadata that does not have to read the data for a block.

2.1.2 Synchronisation protocol

When metadata about a block is received, it is categorised into either the interesting set or the uninteresting set, or discarded.

These two sets are represented by predicates, and changes between the sets can be represented in several ways (see Set specifiers for a reference of these set specifiers). The interesting and uninteresting set predicates must usually remain referentially transparent and not change, to allow the system to cache block metadata and schedule requests; but the sets can be modified when the system is notified, using update-system-for-new-interesting-block-predicate.

interesting-block-p system name version channels [Generic Function]

Determine if a block should be requested, based on its metadata.

interesting-block-p (system standard-system) name version channels [Method]

Everything is interesting by default.

uninteresting-block-p system name version channels [Generic Function]

Determine if a block’s metadata should be kept, in case it may become interesting later, due to update-system-for-new-interesting-block-predicate.

uninteresting-block-p (system standard-system) name version channels [Method]

Everything that has a newer version than the system stores is uninteresting to the system.

update-system-for-new-interesting-block-predicate system interesting-set uninteresting-set [Generic Function]

Update the system’s cache of the interesting set, adding every member of the interesting-set to the interesting set and removing every member of the uninteresting-set from it.

2.1.3 Leader loop protocol

The leader loop of a system performs tasks that are not easy to delegate to a connection, such as watching for requests that timed out, and replacing them with new requests.

leader-loop system [Generic Function]

Run the leader loop for the system. This is expected to return only when the system is stopped.

leader-loop (system standard-system) [Method]

The leader loop of a standard-system implements the description we gave of a leader loop.

start-system system [Generic Function]

Start a system, by starting all its acceptors and a leader thread.

stop-system system [Generic Function]

Stop a system by closing all its acceptors and connections, and advising maintenance threads to stop.

system-stopping-p system [Generic Function]

Should the threads maintaining the system stop now?

2.1.4 Tuning the standard-system

:scheduler-timeout [Initarg]

The time (in seconds) that the scheduler should wait for a request to be responded to. This defaults to 10 seconds.

:scheduler-concurrent-requests [Initarg]

The number of requests that the scheduler can wait for at a time. This defaults to 80 requests.

TODO: It may be useful to add a(n optional) limit on how many requests can be sent to one connection at a time.

2.2 Acceptors

An acceptor creates connections by accepting them from something that faces the outside world, such as a server socket, and gives them to a system.

acceptor [Protocol Class]

The protocol class for an acceptor.

threaded-acceptor [Protocol Class]

The protocol class for an acceptor that uses a thread to give a system connections.

2.2.1 Acceptor protocol

give-system-connection system connection [Generic Function]

Give a connection to the system the acceptor accepts connections for.

An acceptor may have to define :after methods on:

start-acceptor acceptor system [Generic Function]

Start the acceptor, allowing it to create connections on behalf of the system.

start-acceptor (acceptor threaded-acceptor) system [Method]

Start a thread that repeatedly accepts connections by calling acceptor-loop.

stop-acceptor acceptor [Generic Function]

stop-acceptor (acceptor acceptor) [Method]

2.2.2 Threaded acceptors

An acceptor must define a method on:

accept-connection (acceptor) [Generic Function]

Return a new connection that should be added to the acceptor’s system.

An acceptor should usually only have to define a primary method on:

acceptor-loop acceptor [Generic Function]

acceptor-loop (acceptor acceptor) [Method]

Forever accept connections and add them to a system.

Socket acceptor

socket-acceptor [Class]

An acceptor that accepts connections from a socket, also wrapping the connections in SSL.

:connection-class [Initarg]

The class to make instances of. This must be a subclass of either character-connection or binary-connection.

:host [Initarg]

:port [Initarg]

The hostname and port to bind to. These default to "0.0.0.0" and 1892, respectively.

:certificate [Initarg]

:key [Initarg]

Pathnames for the certificate and key files.

start-acceptor (acceptor socket-acceptor) system [:Before Method]

This method starts listening on the given hostname and port.

stop-acceptor (acceptor socket-acceptor) system [:Before Method]

This method stops listening on the given hostname and port.

accept-connection (acceptor socket-acceptor) system [Method]

A socket method accepts a connection by accepting a connection from the socket, and instantiating an instance of the acceptor’s connection class.

Connections are instantiated with initargs :socket and :stream, with values for the raw socket and the SSL-wrapped stream, respectively.

2.3 Connections

A connection connects a client and a server together, allowing the two to exchange messages between each other. decentralise2 is able to handle many different types of connections, including in-memory passing connections and socketed connections that use the operating system’s networking capabilities, which only have to implement a simple protocol.

connection [Protocol Class]

Note that a connection is implicitly started when it is instantiated.

stop-connection connection [Generic Function]

Stop the connection, which should free any resources that creating the connection acquired, such as threads and sockets.

handle-message connection message [Generic Function]

Handle a message that was sent to the connection.

handle-message (connection connection) message [Method]

The default method calls the message handler of the connection with the message.

:message-handler [Initarg]

connection-message-handler connection [Accessor]

A function that should be called with each received message. The default handler will wait for a new handler to be set, in order to (hopefully) prevent some race conditions, where a message could be received before the client has set a message handler.

write-message connection message [Generic Function]

Write a message to a connection. The implementation of this must be thread safe, such that two threads can call write-message simultaneously, and will correctly write both messages.

2.3.1 Connection types

The types of data that a connection can send are represented by a connection’s class, not unlike the stream classes such as fundamental-character-stream and fundamental-binary-stream in the de-facto Gray streams standard.

Note that, unlike Gray streams, all connections are bidirectional.

character-connection [Protocol Class]

A connection that can send blocks with vectors of characters (strings) as data.

binary-connection [Protocol Class]

A connection that can send blocks with vectors of octets as data.

2.3.2 Threaded connections

threaded-connection [Protocol Class]

A connection that uses a thread to read messages.

read-message connection [Generic Function]

Read a message from the connection, blocking until one is present, then returning it and T, or return something and NIL if a message cannot be read ever again (e.g the other node closed the connection).

listener-loop connection [Generic Function]

The thread of the connection will call this function, and stop when it returns.

listener-loop (connection threaded-connection) [Method]

Repeatedly calls read-message, handling its return values appropriately.

passing-connection [Class]

A connection that passes its messages to another connection.

:target [Initarg]

The connection that the passing connection should pass its messages to.

2.3.3 Netfarm wire format connection

netfarm-format-connection [Class]

A character connection that exchanges messages using a simple textual format, based on the wire protocol Nettle used.

As the name suggests, this was intended to be the default connection class for Netfarm; but the creation of Netfarm’s much more efficient binary format suggests that we should use a binary connection class as default.

Nonetheless, it is quite easy to read, and superficially looks like the HTTP/1.0 wire protocol. Messages begin with unique “verbs”, and are separated by new lines.


boolean::=yes no
integer::=(0 9)*
length-prefixed-string::=integer : character*



block-name::=length-prefixed-string
channel-name::=length-prefixed-string
id::=length-prefixed-string
line-count::=integer
reason::=length-prefixed-string
uri::=length-prefixed-string
version::=integer



announce::=announce boolean
block-header::=block block-name version line-count channel-name*
error::=error block-name reason
get::=get block-name*
ok::=ok block-name
node::=node uri id
subscribe::=subscribe channel-name*
subscription::=subscription block-name version channel-name*

Length prefixed strings are preceded by the length of the string (written in base 10), and a colon.
Figure 2.1: An Extended Backus-Naur form-like syntax description of the Netfarm wire format


The base decentralise2 messages are represented as follows:

2.3.4 Netfarm binary connection


boolean::=00 01
byte::=00 ff
long-integer::=short-integer × 8
short-integer::=byte
long-bytes::=long-integer byte*
short-bytes::=short-integer byte*
long-string::=long-bytes
short-string::=short-bytes
name-list::=long-integer short-string*



block-name::=short-string
block-list::=name-list
channel-list::=name-list
version::=long-integer
metadata::=block-name long-integer channel-list
uri::=short-string
id::=short-string



get::=01 block-list
character-block::=02 metadata long-string
binary-block::=03 metadata long-bytes
ok::=04 block-name
error::=05 block-name long-string
subscribe::=06 block-list
subscription::=07 metadata
allow-announcement::=08 boolean
announce::=09 short-string short-string

Byte vectors are preceded by the length of the vector. Strings are byte vectors, that are decoded and encoded as character vectors. Name lists are lists of names, that are preceded by the length of the list.
Figure 2.2: An Extended Backus-Naur form-like syntax description of the Netfarm binary wire format


2.4 Messages

A message is an abstract object that is sent over a connection, and can be considered the lowest-level communication protocol decentralise2 is concerned with.

message-case message &body case* [Macro]

case::=( pattern form* )
pattern::=( keyword variable* )
dont-care::= - _ NIL
variable::=dont-care symbol

Match the value of message against some patterns, which look like the arguments to the function message, and evaluate the forms of the first matching case, with all variables that don’t match the rule dont-care bound to the arguments.

message keyword &rest values* [Function]

Create a message from the type designated by the keyword with the given values. The number of values must be the same as the number of accessors of the type.

2.4.1 Built in message types

get-blocks (:get names) [Message Type]

put-block (:block name version channels data) [Message Type]

ok-response (:ok name) [Message Type]

error-response (:error name reason) [Message Type]

new-subscriptions (:subscription name version channels) [Message Type]

subscription (:subscribe channels) [Message Type]

announcement-control (:allow-announcement allow?) [Message Type]

node-announcement (:announce uri id) [Message Type]

2.4.2 Defining message types

define-message-type keyword type-specifier constructor-name &rest accessors [Macro]

Define a message type named by the given keyword, which corresponds to the given Common Lisp type specifier, can be constructed by calling the function named by the constructor-name, and can be destructured using all the functions named in accessors.

2.4.3 Translators

object->data object target source [Generic Function]

“Serialize” or “render” an object (which came from, or represents an instance of the source), into a value that can be sent as data on the target.

data->object data source target [Generic Function]

“Deserialize” or “parse” the data (which represents an instance of, or something the target can consume), into an object, which was received from the source.

Chapter 3
Netfarm

The second component that was developed was the Netfarm object system. The Netfarm object system introduces a text format for representing an object, as well as code to serialize and deserialize objects.

The part of the Netfarm system that implements an object system is also named Netfarm. It may be helpful to describe this component as the “Netfarm object system”, and the entire system as the “Netfarm software stack” or words to those meanings.

As an example of how Netfarm enables its users to exchange objects with little friction, we will imagine that there are two car enthusiasts, Adrian and Bob, who want to discuss their cars. Here is a class definition for a car that they could have used in a client program:

Listing 3.1: A class definition for a car
(defclass car () 
  ((colour :initarg :colour :reader car-colour) 
   (year   :initarg :year   :reader car-year) 
   (make   :initarg :make   :reader car-make) 
   (model  :initarg :model  :reader car-model)) 
  (:metaclass netfarm:netfarm-class))

This class functions identically to any other class defined using the Common Lisp Object System:

Listing 3.2: Instantiating and describing an instance of a Netfarm class
Adrian> (make-instance car :year 1952 :make "Studebaker" 
                            :model "Starlight" :colour "blue") 
#<CAR> 
Adrian> (defvar *my-car* *) 
*MY-CAR* 
Adrian> (car-model *my-car*) 
"Starlight"

We will discuss how Adrian can send that description of a car to Bob later.

3.1 External formats

Objects are usually serialized in order to transmit them to another client that does not share memory with the origin of the object, and that client must then deserialize the serialized form to produce a usable object.

In Netfarm, serialization is done by converting an object to a vague object, which has as much context of the object removed as possible, which can then be serialized into a character or octet vector. These vectors can then be deserialized by deserializing the vector into a vague object, and then re-introducing the context that the origin of the object supplied.

The octet-vector representation is also used for generating and verifying signatures.

3.1.1 Vague objects

vague-object [Class]

The class of a vague object.

apply-class vague-object class [Function]

Recontextualize a vague object by “applying” a class to it, producing an object.

3.1.2 Character format

render value &optional stream [Function]

Render a value. If a stream is given, then write the value to that stream, else return the rendered value as a string.

render-object object &optional stream [Function]

Render an object. If a stream is given, then write the object to that stream, else return the rendered object as a string.

parse stream-or-string [Function]

Parse a value from a stream or a string.

parse-block string &key source name [Function]

Parse an object from a string. The returned vague object has the supplied source and name.

3.1.3 Binary format

binary-render value &optional function [Function]

Render a value. If a function is given, then write the value by calling it with octet vectors that it should write, else return the rendered value as an octet vector.

binary-render-object object &optional function [Function]

Render an object. If a function is given, then write the value by calling it with octet vectors that it should write, else return the rendered value as an octet vector.

binary-parse function-or-vector [Function]

Parse a value from a function (called with no arguments, which returns octets) or a vector.

binary-parse-block function-or-vector &key source name [Function]

Parse an object from a function (as previously described for binary-parse) or a vector.

3.2 The client

The netfarm-client system provides functions to read and write Netfarm objects from a decentralise client, as well as a client class which can search through a network for an object.

Continuing our car example, Adrian can create a client and use it to save his car:

Listing 3.3: Creating a client and saving an object using it
Adrian> (defvar *client* 
                (make-instance netfarm-client:client 
                               :bootstrap-uris ’("netfarm:a-server"))) 
*CLIENT* 
Adrian> (netfarm-client:save-object *client* *my-car*) 
"Lb6TI6j/GdkLsyCqt20xZhz7PohttpXejZTCKQEjT58="

save-object returns the hash of the object, which can be used by Bob to retrieve the object. Having to pass around a hash is not very convienent, and we can attach our car to some other object Bob may already know about, but we will begin by using this hash to retrieve the car.

Listing 3.4: Retrieving an object using its hash
Bob> (netfarm-client:find-object *client* 
      "Lb6TI6j/GdkLsyCqt20xZhz7PohttpXejZTCKQEjT58=") 
#<CAR> 
Bob> (describe *) 
#<CAR> 
  [standard-object] 
 
Slots with :INSTANCE allocation: 
  ... 
  COLOUR                         = "blue" 
  YEAR                           = 1952 
  MAKE                           = "Studebaker" 
  MODEL                          = "Starlight"

Chapter 4
Netfarm script machine

While it is a component that is packaged with the Netfarm object system, the Netfarm script machine is a sufficiently large and complex component that it deserves its own chapter. Scripts are portable programs that a Netfarm node can run to handle the behaviour of objects.

The script machine is based off the abstract SECD machine, which may be familiar to functional language compiler writers. The machine has several registers:

A simple assembler is provided with the reference Netfarm implementation, which can compile programs such as:

Listing 4.1: A recursive program that computes a Fibonacci number
(netfarm-scripts:define-script *fib* (1 2) 
  (:procedure 1) 
  (get-env 0 0) (get-value 1) < 
  (jump-cond 0 0 0 4) 
  (get-env 0 0) return 
  (get-env 0 0) (get-value 0) - (get-proc* 0) (call 1) 
  (get-env 0 0) (get-value 1) - (get-proc* 0) (call 1) 
  + return)

While this (symbolic) assembly code looks much different to a program written in a high-level language (and also unlike assembly code for real processors), it is similar to the bytecode generated by CLISP for Common Lisp programs, and CPython for Python programs.

This example program doesn’t really have a purpose in a Netfarm system. Scripts in Netfarm have three purposes (currently):

4.1 Presentations

Presentations are the other use of scripts in Netfarm. A presentation is a graphical representation of an object that retains its identity. A presentation model allows Netfarm to exchange machine-readable objects between clients, while also being able to present human-readable descriptions of objects. This model was introduced by [Cic84], and has been used in the Common Lisp Interface Manager to great effect.

There are at least four presentation types in Netfarm: toplevel presentations, block presentations, inline presentations, and instance forms. A programmer may create more presentation types for their own uses, but a graphical client is always expected to be able to render those types.



Figure 4.1: A toplevel presentation

PIC


Presentations are generated by presentation scripts that are referenced by an object’s schema in its presentation-script slot. If that slot is unbound, Netfarm will render a presentation using the fallback presentation script, which emits the following presentations for these types:

Appendix A
A description of a voting-web system

We have not implemented this voting-web system, but we should describe it, because it is a very important and (to our knowledge) new technique for moderating an online system. This system may be seen as an extension of many Usenet clients’ kill lists, which contain a set of patterns that match posts the user does not want to see; but it can also be used as a whitelist, or just to rank some objects in some order.

It is very important that a distributed system has a means of distributed “moderation”. We wonder why distributed systems are built without distributed moderation of some form, and we believe that using centralised moderation on such a system would be an equivalent of the “people’s stick” described in [Bak73]. Unlike some kinds of moderation in the real world, we are not required to give computers some kind of “objective” truth, and we do not attempt that with Netfarm. Freeing ourselves from that obligation allows us to approximate the desires of each user with greater precision.

This system allows a user to maintain a map of “facts” that they assert to be true or false. A presentation script may query the voting-web system while rendering an object, to decide what related objects it should render, or a client program may just refuse to render some presentation forms of an object that has certain facts about it asserted.

In the absence of a fact asserted by the user, we believe it is possible to determine the probability that the user would assert the fact, as a function of some delegates’ assertions. Suppose Pr(Fis true toU) is the probability that a user U takes the fact F to be true, and that delegates(U) denotes the set of delegates of the user U. We can define the probability to be:

Pr(F is true to U) = 1 (if U asserts F to be true)
Pr(F is true to U) = 0 (if U asserts F to be false)
Pr(F is true to U) =     ∑      P r(F is true to D)correlation(U,D)
D ∈delegates(U)
------------∑----------------------------
                   |correlation(U,D )|
        D∈delegates(U )

We also introduced a function correlation(U,D) which estimates the correlation coefficient between two users, which we have appropriated from the memory-based collaborative filtering techniques used in recommender systems. This could be defined as:

correlation(U,D) =        ∑   support(U,f )support(D, f)
     F ∈facts
∘--∑---------------∘---∑-----------------
       support(U,F )2       support(D, F)2
 F ∈facts              F ∈facts
where support(U,F) = (|1    (if U asserts F to be true)
{
|(− 1  (if U asserts F to be false)
 0    (if U does not assert F )
and facts = the rules U asserts the rules D asserts

In the absence of a large number of common facts, setting the correlation coefficient to be a small constant may yield results that are not very good, but are better than not attempting to calculate a probability.

Appendix B
A history of Netfarm

(Note that this is a very long appendix, and it almost reads like a rant. It almost is a rant. It might, however, give a sense of why one would want to create a system like Netfarm.)

A forum on Reddit which some of the developers read brought up the idea of creating a website to host the forum, after Reddit had removed its warrant canary1 and was considered compromised. One of the moderators had used blog writing software with several modifications to create a sufficient forum website, and then the website had slowly grown to take its place. There was still some disapproval, possibly due to distrust of the administrators of the new forum and some users wanting a decentralised solution. Most of the effort of the administrators was focused on creating a less kludgy solution to hosting the forum, so ideas created by those users weren’t acted upon.

In 2017, Hayley had started writing some experimental code which implemented several kinds of “federated” servers with different goals. Some of those attempted various forms of secrecy, and others implemented different means of aggregating content. One project named “Nettle” (named after a minor character in a television show that frequently played on weekday mornings who wore a hat with a nettle leaf, which was able to sting unexpecting adults) had broken down the latter into two types:

This approach of decomposing a distributed system into the most basic of types and processes was interesting, so she proceeded to study it further. The “data object” and “aggregator” types were then merged, creating a distinct tree structure. When mutability was eventually desired, the concept of a “script” was introduced, allowing a programmer to specify what combination of users were allowed to update an object after its creation; however, the object was completely replaced, based on false judgement that a network could easily reach concensus on if an object can be updated, even if multiple older versions could exist simultaneously throughout a network. Fortunately, this mistake lead to the creation of a “watchbunny” (in place of a “watchdog”) timer which would interrupt an interpreter that took too long to evaluate its code.2 This watchbunny was then drawn and a scan of the drawing was used as an image for Nettle (but not as a logo of any sort; the logo was a cons cell drawn on top of a section of the Mandelbrot set), and later used as the logo for Netfarm.

The presence of a traditional moderation scheme was asssumed (and enforced as objects had to be verified by scripts their parents held), until the host admitted that they had been manipulating its users through several alternate accounts, which was suspected by some as they wouldn’t clean up any harrasing comments they made. The host was promptly banned from the website, causing many users to wonder about who had control over the website, and who would have it later, should it still exist. At that point, more people were interested in the development of Nettle than usual, and more breaking changes were made.

A “kill list” was proposed (borrowing from Usenet lexicon), which is arguably a first-order approximation of the current web-of-maps design, and it was decided that any kind of moderation had to be opt-in, lest it be used to repress users, or in the case that caused the controversy, to allow anyone else to contribute to keeping the peace.

In the last few months of Nettle, it was decided around this time that emulating a forum or some other form of social media would be a waste of this distributed system’s potential. It is not uncommon for there to be problems with trying to form a system with greater powers around the capabilities of one with lesser powers, and it was likely that the Nettle system was being designed poorly because any questions about its design were being asked in terms of how it could implement a forum. It was shortly realised that Nettle was not suitable for creating and distributing structured data. After that realisation and the reintroduction of the problematic administrator in the forum Nettle had arisen from by popular vote, it was unclear what the purpose of Nettle was, and it was put to rest.

During August of 2018, we had studied ...

Appendix C
Index

Index

:acceptors Initarg, 1
:certificate Initarg, 2
:connection-class Initarg, 3
:host Initarg, 4
:id Initarg, 5
:key Initarg, 6
:message-handler Initarg, 7
:port Initarg, 8
:scheduler-concurrent-requests Initarg, 9
:scheduler-timeout Initarg, 10
:target Initarg, 11
accept-connection Generic Function, 12
accept-connection Method, 13
acceptor-loop Generic Function, 14
acceptor-loop Method, 15
acceptor Protocol Class, 16
announcement-control Message Type, 17
apply-class Function, 18
binary-connection Protocol Class, 19
binary-parse-block Function, 20
binary-parse Function, 21
binary-render-object Function, 22
binary-render Function, 23
character-connection Protocol Class, 24
connection-message-handler Accessor, 25
connection Protocol Class, 26
data->object Generic Function, 27
define-message-type Macro, 28
echo-system Class, 29
error-response Message Type, 30
get-block-metadata Generic Function, 31
get-block-metadata Method, 32
get-blocks Message Type, 33
get-block Generic Function, 34
give-system-connection Generic Function, 35
handle-message Generic Function, 36
handle-message Method, 37
interesting-block-p Generic Function, 38
interesting-block-p Method, 39
leader-loop Generic Function, 40
leader-loop Method, 41
listener-loop Generic Function, 42
listener-loop Method, 43
map-blocks Generic Function, 44
memory-database-mixin Class, 45
message-case Macro, 46
message Function, 47
netfarm-format-connection Class, 48
new-subscriptions Message Type, 49
node-announcement Message Type, 50
not-found Condition, 51
object->data Generic Function, 52
ok-response Message Type, 53
parse-block Function, 54
parse Function, 55
passing-connection Class, 56
put-block Generic Function, 57
put-block Message Type, 58
read-message Generic Function, 59
render-object Function, 60
render Function, 61
socket-acceptor Class, 62
standard-system Class, 63
start-acceptor :Before Method, 64
start-acceptor Generic Function, 65
start-acceptor Method, 66
start-system Generic Function, 67
stop-acceptor :Before Method, 68
stop-acceptor Generic Function, 69
stop-acceptor Method, 70
stop-connection Generic Function, 71
stop-system Generic Function, 72
subscription Message Type, 73
system-id Generic Function, 74
system-stopping-p Generic Function, 75
system Protocol Class, 76
threaded-acceptor Protocol Class, 77
threaded-connection Protocol Class, 78
uninteresting-block-p Generic Function, 79
uninteresting-block-p Method, 80
update-system-for-new-interesting-block-predicate Generic Function, 81
vague-object Class, 82
write-message Generic Function, 83

acceptor, 84

block, 85

connection, 86

deserialize, 87

interesting set, 88

leader loop, 89
leader thread, 90

maintenance threads, 91
message, 92
metadata, 93

Netfarm object system, 94

presentation, 95, 96
presentation scripts, 97
presentation types, 98

script machine, 99
Scripts, 100
SECD machine, 101
serialized, 102
set specifiers, 103
system, 104

uninteresting set, 105

vague object, 106

Listings

Bibliography

[Bak73]   Mikhail Bakunin. Statism and anarchy, 1873.

[Cic84]    Eugene C. Ciccarelli. Presentation based user interface. https://dspace.mit.edu/handle/1721.1/6946, 1984.

[Eth19]   Ethereum developers. Sharding faq. https://github.com/ethereum/wiki/wiki/Sharding-FAQ, 2019.

[Rou17]   Indhi Rousseau. Mastodon instances. https://instances.social/list/advanced, 2017.

1currently reachable on Instagram at https://www.instagram.com/luke_is_frog/

1I believe the Common Lisp babel library preserves code points, as the encoding and decoding functions are quite simple, but some guarantees on how code points are treated would be nice.

1We do need a more unique and less vague name for this...

1A warrant canary is a method by which a communications provider can inform its users that the provider has been served a subpoena which they cannot legally disclose. When the canary ceases to be updated, it is very likely the provider has been served such a subpoena and they may have had to provide private information to the issuer.

2The language used, Nettle Lisp, was designed to avoid infinite loops and constructs such as functions were avoided that could create infinite loops, which also was a mistake. Don’t worry, I find making this many mistakes boring, too.