MeshFS

From OLPC
Jump to navigation Jump to search

What is MeshFS?

MeshFS is a system for publishing, searching for, and retrieving objects.

Assumptions

Good things

  • Links are fast

Bad things

  • No information is known about the topology of the network
  • Nodes may be offline for multi-day periods
  • Nodes may be malicious
  • Users will want to index content whose format was not known at design-time
  • Security algorithms, both social and cryptographic, will not continue to be useful indefinitely
  • No single organization can be trusted to maintain the network

Metaspecification

This specification is arranged into sections and levels, which are orthogonal. A particular chunk of spec may only logically depend on levels less than or equal to its level. Thus, Transmission Level 0 may refer to Datastructure Level 0, and vice versa, but may not refer to Transmission Level 1.

An exception is made for normative ("Why?") explanations. Datastructure Level 0 may, e.g., explain why the author believes that it will adequately support higher levels. Such explanations are for the education of the user and may aid in algorithm optimization, but do not have any effect on the formal semantics of the system.

Datastructure

Level 0

The basic design of the datastructure is a table. However, no node can enumerate either the complete column- or the complete row-set.

Rows do not have identity; they are identified solely by their contents. Columns are identified by a bytestring, called the column name. Each cell is a bytestring.

Each node stores a sparse table locally. Any given cell may be missing from any given node's local table. Some cells may not be present in any node's local table. However, a cell can never be proven missing from the global table, because no set of nodes can ever be assumed to represent the complete global table.

Transmission

Level 0

Each transmission contains a sparse row, or, equivalently, a finite map from column names to cells. The transmission of a sparse row is an assertion that the cells provided are all in the same row in the global table (an assertion which, of course, cannot be definitively checked, even in theory).