# qDHT patent planning ## Crucial concepts - DHT as spacetime plane - Space: Transition rrDHT arcs to have discrete boundaries and build a space tree of blocks - Time: Setting a $T_0$ for each app/DHT and building a time-tree of time blocks - Can compute a hash (via hashing or XOR as an optimization for unordered data and compression of "stable" tree branches) of all hashes of all data in any region of spacetime - ## Useful concepts These are currently unimplemented but may be useful in the future - Use of Fenwick trees or Segment trees to keep a fast in-memory cache of region data which can be incrementally updated as new data comes in ## Questionable concepts - Using a probability model to determine the ideal set of regions to use during gossip - Depends on the ability to actually find an accurate probability model; also on how hard it is for different agents to reconcile different choices of regions --- # Outline ## Ontology / definitions ### P2P Network ("Network") A P2P network, or "Network", is a collection of Agents who are able to connect to each other over the Internet for the purpose of exchanging data. ### Spacetime All entities in the Network are organized into a geometrical "Spacetime". Spacetime simply represents that all entities have locations and extents in space as well as in time, and can be organized in relation to each other through the standard notion of Euclidean distance. The "space" we talk about is simply a finite circle, but can be generalized to higher dimensions by an [$n$-torus](https://en.wikipedia.org/wiki/Torus#n-dimensional_torus). The "time" we talk about is simply a 1-dimensional [ray](https://mathworld.wolfram.com/Ray.html) with its endpoint fixed at the origin. Spacetime is formed by simply sweeping the circle (or $n$-torus) of space through time to form a cylinder (or more complex surface for higher dimensions). All entities exist somewhere on this cylindrical surface. For the purpose of simplicity and brevity, for rest of this document we will assume that space is 1-dimensional. Any subsequent geometric terms used can be extended to higher dimensions by the reader, e.g. a spacetime "rectangle" can be extended to "rectangular prism" for a system with 2 spatial dimensions instead of 1. ### Event (called "Op" in Kitsune) An Event is a packet of data which is transferred from one Agent to another. Each Event is deterministically assigned a Hash, and each Hash has a definite Location in space, therefore each Event has a Location in space. Each Event also contains a Timestamp which gives it a Time coordinate. Thus, each Event occupies a definite point (in the geometric sense) in spacetime. ### Agent An Agent is a distinct member of a P2P network. Agents communicate with each other to send data about each other, and about Events, to each other. Agents are the source of Events. Each Agent has a definite Location in space, but has no timestamp associated with it. ### Arc Each Agent has an Arc, which is a certain extent of space containing the Agent's location. Agents are responsible for storing and gossiping all Events which are located within their Arc. Agents grow and shrink their Arcs over time, depending on network conditions. Arcs may not be sized arbitrarily: they must follow some quantization rules which will be described later. ### Hash A Hash is a "digest" or "fingerprint" of some data which is meant to be universally unique. TODO, define. Hashes have a Location in space (but not in time). ### Region (of spacetime) A Region is simply a rectangular area of spacetime, with extent in both space and time. Regions are used to refer to groupings of Events which intersect that region. Regions may not be drawn arbitrarily: they must follow the rules of quantization described later. ### Gossip round ("Round") Agents communicate ("gossip") with another in discrete Rounds. During a Round, data is exchanged according a fixed protocol. Much of this document will be dedicated to the details of what happens during a Round. ### Quantization Certain spacetime coordinates are "quantized", meaning they cannot take on a continuous range of values, but must instead be selected from a discrete set of evenly spaced values. The coordinates which are quantized are: - The endpoints of an agent's Arc - The coordinates making up a Region Space and time are both quantized. The "grid" which defines the quantization is determined for each dimension separately. Each dimension has a "quantum", a smallest possible unit, and the spacing of quantized values is determined from that. Quantizations of increasing coarseness can be obtained by successively doubling the distance between quantized values, or equivalently, by removing every other quantized value from consideration. The number of doublings used to obtain a particular set of quantized values for a dimension is called the *quantization power* or simply the "Power" of that dimension. A power of 0 denotes a dimension with points spaced by the chosen quantum length. A power of 1 denotes a quantizaion with double the spacing of power 0, meaning that half as many points are used to represent the same space. Regions can only be drawn using adjacent points from each quantized dimension. In other words, a "side" of the rectangular region cannot contain more than 2 quantized points. Distinct regions defined by quantizations at the same power levels can never overlap. Two regions, one of which has lower power levels in both dimensions than the other, will never partially overlap: either they will be nonoverlapping, or one region will be fully contained by the other. The only way to have partially overlapping regions is to have two regions A and B where A's space power is higher than B's, and A's time power is lower than B's. ## Prior art: rrDHT ### What we build upon - We still use the same notion of an Arc (previously incorrectly called "radius") ### Differences/improvements to rrDHT - Arcs are now quantized ## Algorithm All Agents in a network agree on an *origin time*, $T_0$. Agents set their Arc determined by the *arc resizing algorithm* (Q: do we want to describe that in this patent?) When choosing another Agent to gossip with: - both agents compute their *common arc*, which is the intersection of their two arc - both agents choose a set of regions to cover the area of spacetime bounded by spatially by the common arc, and temporally by the current time, according to the *region selection algorithm*. - each agent exchanges the fingerprint of each region in their list, along with the coordinates of that region, wich the other. - the agents compare hashes of identical regions to see if the contents are different. - the agents send all Event data only for the regions which have changed.