ascd: a network-aware daemon for P2P sharing of ASC data

← Back to ASC page

Abstract

At present, the ASC system can learn from the execution of currently and locally running programs only. However, it is likely that, for a given program running on a given computer, the same program has been run before, on a different computer, and potentially with similar inputs. It would be ideal if a computer could obtain the learning data produced by one or more invocations of ASC on another computer instead of reproducing the same work locally. In addition, we would like to allow any improvements to the learning data to be sent back to the source. To enable this, I propose that ASC be made “network-aware” by the introduction of another program, ascd, the ASC daemon, and a small number of modifications to ASC itself.

In short, our ASC daemon will minimally need to meet the following needs posed by the task of network-awareness:

  1. It must be possible for an installation of ASC to obtain learning data from any other sources before running a program under ASC.
  2. It must be possible for an installation of ASC to “update” others with any new learning data it acquires as the result of running a program under never-before-seen conditions.
  3. Since ASC itself may be installed anywhere on a given system (e.g., for any user on a UNIX timesharing system), local ASC installations must be able to share data with each other, on the same system, if configured to do so. This minimizes the reproduction of learning work done on a given system.
  4. Since there may be one or more ASC-enabled systems connected via a network (e.g., the Internet), it must be possible for an ASC installation on one system to exchange learning data with an installation on another system, so as to minimize the reproduction of learning work across networked systems.
  5. Since ASC itself is only running while its target program is running, and a given ASC installation’s learning data may be of use to other ASC installations at any time, the learning data produced by a given ASC installation should be available to others, even while a program is not running.

I propose that ascd meets these needs by providing the following features for each need:

  1. The ascd daemon will respond to requests from local ASC installations for any learning data it has stored. This means that, if ascd has any learning data for a given program, it can satisfy such a request by sending a running ASC with .excite, .net, and .train files.
  2. The ascd daemon will store learning data produced by local ASC installations (.excite, .net and .train files). That way, ascd can respond to any future requests with these files.
  3. The simple case of two, non-concurrent invocations of ASC on a given program is already handled by (1) and (2) above: the first invocation starts and finishes, and ascd updates its store. By the time the second invocation begins, it obtains exactly the data produced by the first invocation.

    However, the more complex case of concurrent invocations must be handled separately. This is the case of two invocations that begin with the same initial learning data, but which (presumably) produce different post-run data. In this case, I propose that ascd use any one of several network combination techniques: the daemon could simply choose the network that results in the lowest bit error rate (BER), choose the smallest or largest network, or merge the networks to produce a single network that is twice as large.1

    These network combination techniques could be composed in any way, for any number of concurrent invocations, dependent only on the timing (e.g., starting and ending times) of each invocation. Potential worst-cases for timings will be ignored here (i.e., at this stage we are only concerned with combining networks; combining them optimally can be the concern of future work).

  4. If we consider that, by (3), a given ASC-enabled system is simply a store of learning data held by one ascd daemon, then communication over a network between systems is simply the communication of two or more ascd programs speaking a common protocol. However, the rules by which two ascd daemons should communicate are different than the ones used between an ASC installation and its daemon (i.e., it is peer-to-peer).

    In addition, since we can assume that network latency times are several orders of magnitude higher than latencies between programs on a given system, we must not require a local ASC installation to interact with a network before or after it executes a target program. Instead, we leave the network communication to the ascd daemon.

    Therefore, I propose that two ASC-enabled hosts on a network will communicate with each other in a manner independent from any local ASC installations, except under the following circumstances:

    • A local ASC installation on a host A is running a program P for the first time (i.e., the ascd daemon on A stores no learning data for P). In this case, it may be worthwhile for A to consult a host B for learning data for P. If B has learning data, then A can make a request for it, and P can be run with B’s data.

    • A program P completes, causing a host A to update its store for learning data for P. As the result of prior network communication, A knows that another host B would like learning data for P. As a result, A will offer its data to B.

    One more note: as in (3), ascd daemons will need to choose the appropriate network combination technique if a daemon is requesting data for a program for which the daemon already has data.

  5. Apart from the circumstances enumerated in (4), ASC-enabled hosts can share learning data in any manner they wish, dependent on the configuration of their ascd daemons. For example, the hosts may decide to broadcast their local stores to the network at predefined network intervals. They may also decide to dump their stores to new hosts joining the network for the first time. These events can happen independent of any local activities (but may actually be be delayed by local activity, if an ascd daemon decides to wait for a local ASC invocation to complete).

    Hosts will also need to determine if or when to actually consult the network, in the case that the host already has data for a given program. For all (or some) other hosts, a host will need to keep track of the quality and recency of training data elsewhere in the network. This will allow the host to make responsible decisions as to when to obtain new data from other hosts.

How ascd works

We will assume that the ascd daemon will run at system startup, and that the system will allow it to open network sockets and local UNIX sockets. When ascd does start, it opens a UNIX control socket in a well-known location, reads its learning data store from disk, and listens on the control socket.

ascd responds to the following local messages (i.e., messages from invocations of ASC), which constitute a simple local ASC protocol:

When the daemon receives LOOKUP or LOOKUP_LOCAL, it will initialize bookkeeping information for the connection to the ASC invocation, which includes a timestamp for when the lookup occurred. This allows the daemon to determine whether another invocation updated the store while the current invocation was running, and to use a network combination technique as opposed to replacement.

How ascd manages its store

The ascd daemon will use SQLite as an underlying storage system, which allows the daemon to efficiently perform modifications of the store. Efficiency is a central concern, since a given target program running on top of ASC could complete very quickly, giving the daemon little time to perform merging or updates before another invocation does a lookup.

Asynchronous, offline training

I will introduce the possibility of batch offline training, but this may be the subject of future work.

The ascd daemon could perform asynchronous, offline training of networks in its store during periods of system inactivity or as a method to optimize less-frequently used program data. This, in addition to network communication, can significantly increase the overall quality of training data while a given program is not even being run.

A simple implementation would detect when offline training could be started (e.g., based on the system load averages), and for which programs it is best to train (e.g., less frequently used programs, or programs for which a host knows other hosts are prioritizing).

Network combination techniques

As enumerated in the abstract, I can think of four simplistic network combination techniques, which I will enumerate and explain here:

Peer-to-peer protocol

Distributed hash table (DHT) protocols were considered for their durability and efficiency. A simple implementation in C of the Kademlia protocol was chosen, written by Juliusz Chroboczek. The Kademlia protocol is used by BitTorrent clients, for trackerless torrents.

Like most DHTs, any node can be the “owner” of a set of keys. If an ascd daemon is an “owner” of a set of keys K, it must store K in a special database table. Upon leaving the DHT, the daemon can drop the table containing K, since it is then up to the network to recover those values.

However, let the set S contain the keys for programs for which a daemon has training data that is obtained by the daemon while the host is not joined to the DHT. When that host joins, the host should attempt a DHT STORE operation so the owner node gets this data.

In my implementation I will enforce that owner nodes always use the best error rate metric to decide which training data to retain in K. This avoids the potential issue of network size blow-up, which is a subject for future work.

Import and export policies

I will introduce the possibility of import and export policies, but this may be the subject of future work.

For security or privacy reasons, an entity may not want to share information about what programs are being run under ASC, but still may desire the speedup ASC can provide. The simplest choice is that a system not use the ascd daemon at all. However, if multiple users are using a given program (for example), and training data should be shared among them, or if hosts want to share certain training data sets with specific other peers, it may be useful to implement import/export policies.

If a daemon has an import whitelist set up, then the daemon will only trust particular hosts for new training data. If a daemon has an import blacklist set up, then the daemon will always reject training data for particular hosts.

A daemon’s export policy defines which other hosts get copies of their local training data.

This feature would require that a DHT not be used. Another, more classic peer-to-peer structure would be required.

  1. For reasons I will discuss later, using merging as a local combination technique may not be ideal. 

  2. This may be the effect of an --asap flag in ASC, for example. It could be used when an invocation of ASC cares more about starting quickly than obtaining higher-quality learning data. 

  3. Perhaps networks with the same number of excited bits, or a network pair for which one network has a subset of the bits trained by the other.