Designing PubSub

Nobody has claimed this yet.

> Note: This issue summarizes the work done on PubSub by the IPFS community (https://github.com/libp2p/pubsub/issues/1 (8 Aug), Q3 team week, Q3 workshop https://github.com/ipfs/2016-Q3-Workshop/issues/17) and a brain dump from some of my personal notes that may not be representative of everyone's view and understanding of the problem space.
##
# Background
- Developers want to be able to have dynamic content on their applications
- Peers should be able to subscribe to particular content and when other peers publish the matching query, the subscribers should receive an update
- [`ipfs/notes#pubsub`](https://github.com/ipfs/notes/issues?q=is%3Aissue+is%3Aopen+label%3Apubsub) Extensive list of pubsub conversations
# Literature review
- [ ] find a way to collaboratively extract value from lit-reviews
- Academic
- [x]([XL pubsub paper]%28http://dl.acm.org/citation.cfm?id=2543583%29) - get background on distributed pub/sub
- [x] https://github.com/libp2p/pubsub/issues/4 - collect a list of relevant papers and find a place and time to discuss them
- Industrial (understand what went wrong/great and why)
- [ ] collect a list of cases (e.g. https://github.com/libp2p/pubsub/issues/3)
# Designing PubSub v1

The aim is to collect use cases and requirements for a **minimum viable** pubsub v1.
## Use cases
- [ ]([USECASES.md]%28https://github.com/libp2p/pubsub/blob/master/USECASES.md%29) Build a list of use cases from community and implementors
- [ ] Find a way to collaboratively extract values from use-cases
- [ ] Give deadline to this
## Requirements
- Small networks (thousand of nodes)
- Survive massive amount of churn in browsers
- Minimize flood
- Do not prevent future improvement (hard!)
- [ ] define what are the other properties of this system:
- Reliable? (every peer receives all the messages and in order)
- Authenticated? (should peers sign messages)
# PubSub layers

> Note: The following is my personal view of the problem space (from our conversations and use cases), please chip in/argue by commenting, I will update accordingly
## Terminology
- Publishers: they are the authors of the new content that need to be published
- Brokers: they can be subscribers, they receive messages from publishers and send them to subscribers
- Subscribers: simply subscribe to messages
- [ ] https://github.com/libp2p/pubsub/issues/5 - Add new terms to [`ipfs/glossary`](https://github.com/ipfs/glossary)
## Problem space
- [ ] What type of content can users subscribe to?
- Permissioned vs Permissionless pubsub
- **tl;dr** Users must subscribe to the content where the pubkeys of the publishers are known. If not, they are basically blindly subscribing to spam.
- Permissioned:
- _(in theory)_ subscribers subscribe to a known set of publishers (each publisher is known by a public key)
- _(in practice)_ subscribers subscribe either to an IPRS or an IPNS (known set of pubkeys), the publishers of the content publishes to the network that route event to the subscribers.
- _(verdict)_ a lot of work has been done in this direction!
- **note:** this does not mean that the numbers of subscribers must be fixed, new users can join/leave a permissioned network
- Permissionless:
- _(in theory)_ subscribers subscribe to an identifier (which can also be a query), however, in order to avoid complete spam (since we don't know the pubkeys everyone can publish at that identifiers) we need to add some way to reduce spam, e.g. proof-of-work type of approach
- _(in practice)_ subscribers could subscribe to a genesis block of a blockchain (say bitcoin) and receive updates from the majority
- _(verdict)_ this is mostly an exciting gray area, anti-spam is hard and this would just turn pubsub into consensus/atomic broadcast problem
## Layers of abstraction
### (layer 3) Developers API `.pub`, `.sub` and events `message`, `error`

This layer is the final interface that should be used by application developers (a-la orbit)
- [ ] Strawman application interface (create an issue on this)
- [ ] Define the properties of this final layer (retrying subscription, ensure order, keeping a state of messages received & so on)
- [ ] Define subscribe signature
- `.sub(id, [set of keys in the network])`
- find if the ID itself could be a pointer to an IPLD that has a list of Pubkeys and a query
- find if the ID, pubkeys and query can be separate params
- [ ] Define publish signature
- `.pub(id, content)`
- find if the content must be encrypted externally, could/must be signed externally
- find a way to point to previous updates (authenticated streams) via the content itself or another param
- [ ] Define a `.on('message', (content) =>)`
- should the check for authentication of content be done behind the scenes?
- [ ] Define the set of errors that could happen in this
- [ ] Define the need for `snapshot` - say that one peer has missed an entire year of updates, they can either download each individual update or get a final snapshot (maybe too complex but could be done with IPLD transforms)
### (layer 2) Data model

This is layer is the data model that describes a sequence of events
- We can describe a sequence of events in IPLD, who publishes an event, basically publishes an IPLD
- [ ] Proposal Authenticated Streams (create a grouping issue on this) - discussed mainly in https://github.com/ipfs/notes/issues/154 (and https://github.com/ipfs/notes/issues/148)
- Identifiers are the "genesis" of future events.
- Events point back in a DAG style
- Subscribers will receive new nodes added to the DAG and get from the DHT the nodes they are missing
### (layer 1 and 0) Pubsub Routing (better name needed)

This consists of peer discovery and event propagation (same as content-distribution).

This is the layer that routes an event from publisher (that has only a partial view of the subscribers - otherwise this would just this broadcast!) to the subscribers. There are different strategies for distributing events. If this layer change, there should be no change in the **Data Model** or **Developers API**.
#### Structured vs Unstructured networks

There are different strategies to do this:
- **structured networks**: in this case the peers of the network will self-organize in a very specific structure (this is great for reliable networks where nodes are not continuously disconnecting so that the structure is not constantly altered), the great thing about this is that we can reuse the DHT (see Pastry, PastryStrings)
- **unstructured networks**: in this case peers will distribute messages without following a specific structure (these are mostly gossip algorithms). Messages are often received multiple time.

Questions to answer:
- [ ] Define the network requirements
- Is there a "one-fits all" routing strategy?
- What are the type of networks we plan to have pubsub?
- [ ] Should the pub/sub strategy be adaptive? So multiple peers talk multiple pubsub (we once referred to this as multipubsub)?
#### The role of the peers

The author of the content is a publisher, however they have a partial view of the subscribers, so some of those subscribers must be distributing the content themselves (becoming brokers themselves - since the content is authenticated, they could be considered publisher themselves too, they are just publishing someelse content).
- [ ] Agree on terminology of who's who (publisher, broker, subscriber)
- [ ] Are all the subcribers brokers? (meaning every peer participate to the distribution? please keep in mind cheap devices)
#### Pubsub router interface

This should define a low level interface where subscribers and publishers talk individually to other peers, for example exchanging peers, exchanging interests, basically a generic pubsub protocol. This can be helpful in case we are implementing different pubsub routers.
- [ ] Find if this abstraction is needed
- [ ] Nail down an interface
# Testing the network
- [ ] https://github.com/libp2p/pubsub/issues/10 - find a way to spin up a simulation with thousand of nodes that subscribe and publish content considering any type of fault (byzantine, network partition, fail-stop, network delay)
- [ ] benchmarks: build tools to measure the efficiency of a pubsub network (if we are going to try different strategies)

---
#### Note
1. I haven't covered many things that we left pending or that I don't remember right now, please chip in - nothing of the above is cast in stone :)
2. We have to create and link the issues related to most of the TODO items, so that we can have separate conversations outside of this issue
##

cc @jbenet, @diasdavid, @haadcode, @dignifiedquire

Start with the use cases in USECASES.md and the linked discussions, then review the proposed developer API, data model, and routing layers in this issue. The work is not ready until the requirements, terminology, interfaces, and testing approach are agreed and documented.

Written by the indexing model from the issue text.