npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

new_protocol

v1.1.0

Published

This is a data replication protocol oriented towards applications where a group of semitrusted peers collaborate on a shared data structure. For example, a chat room, a wiki article, a multiplayer game. Prehaps a market even.

Downloads

1

Readme

new_protocol (working title)

This is a data replication protocol oriented towards applications where a group of semitrusted peers collaborate on a shared data structure. For example, a chat room, a wiki article, a multiplayer game. Prehaps a market even.

The simplest is a chat room. In a chat room each message is displayed on it's own. There is no complicated way to interpret updates and decide which has precidence such as in a wiki. But the core distributed systems problem is the same - ensuring that every peer receives every message.

A multi party chat room is a good model, because even if you think you want 1:1 chat, these days people are likely to have more than one device, so that becomes many parties.

core api

msg

{ //timestamp representing author's message creation time. ts: timestamp, //ids of messages directly preceding this one. prev: [ids...], //height is 1 more than the height of prev messages height: integer > 0, //arbitrary data content: ... }

branching messages

usually a new message has a single previous message.

 msg1 <--- msg2

but, it is possible for two peers to create a new message at approximately the same time, aka, "concurrently". This means, after one peer created the message, but before it was sent to them.

msg1 <--- msg2_1
  ^
   `----- msg2_2

if a message is created after a pair of messages like this, it has two prev items.

msg1 <--- msg2_1 <---,
  ^                   msg3
   `----- msg2_2 <---'

exception: the very first message has no previous message.

init ()

create a new state object

update(state, msg) => true | false | new_state

add msg to state. returns true if msg is already contained in state. returns false if msg cannot be added because of missing messages. (see missing) returns new_state if msg could be successfully added.

create(state, content, ts) => msg

creates a new valid message, given state and ts.

state is needed because the message will contain pointers to the leaves from the current state, and the height.

request (state, prev) => {have: [ids...], need: [ids...]}

construct a request object, from state and a received msg's prev field. it is possible that the received prev has multiple elements, but you may not be missing all of them. request will sort that out.

missing (state, request.have, request.need)

when you receive a message, it should be added to the current state, but sometimes a message cannot be added because the message as arrived in the wrong order. Probably there was another message before it, that you did not receive yet because you were offline, or the packet was dropped, or maybe it just crossed the other packet in the air.

in that case, a request => {have, need} should be sent to your peers requesting the missing message(s).

They will use missing(state, have, need) => messages to calculate the messages to be sent to you.

posets

posets (partially ordered sets) provide concepts to conviently talk about messages in distributed systems. This section establishes some notation about Posets that will be used to describe the protocol further on.

lowercase variables denote an item (a message). Uppercase variables denote a set.

The following operators evaluate to boolean when applied to individual messages, and can also be used to filter and combine sets of messages.

equality: a == a any message is equal to itself a = a causation: a < b when message b was created a was known (or another message that causally after a) concurrency: c >< d when message c was created, they had no knowledge of d, and vice versa

A <= b means messages from poset A that causally preceded b, and message b itself. A >= b means messages causally after b, and b.

A >< b means messages concurrent with b from set A.

finally, we have some operators and, or, subtract, that are applied to two sets.

A & B means intersection of A and B A | B means union of A and B A - B means subtract set B from A.

concurrent set is the same as messages not causally before, A >< b == ((A - (A < b | A > b))

message transmission

Normally, messages are broadcast one at a time. but after being offline, a peer will require messages that have happened since the last one they received.

If they were up to message b in set A, they need messages following from b, or messages that were concurrent with b.

that is: A - (A <= b), aka A >< b | A > b

in ./naive.js is a simple way to calculate these:

take the set _A = A, then iterate over the ancestors of b, and delete them from _A. _A now contains the updates needed. This requires duplicating the entire set, then deleting (probably most) messages from it.

in practice, a request for missing messages with be request(have, missing) where have is a list of known messages, missing is a list of messages that we know we do not have. (probably because we received another message that mentioned them)

So, we assume that the peer has everything before have. so whats missing is (x <= missing) - have

by using message height,


as messages are added, keep track of the heads. if since_heads is equal to our current heads, result is empty set. else check using hashtable or bloom filter if since_heads is in our message set. if not, return an error. if yes, heads are in set, then for each head, if prev is not a since_head, then it is in result. repeat, recursively.

I have an idea for an efficient way to calculate this, in one pass, using the height field.

since I'm intending this to be a udp protocol, which may have dropped packets,
it's possible to recive a message, without some prev messages.
in that case, a peer requests the missing messages `caused_after (have, missing)`
which requests M < missing - M <= have. that is, enough messages to correctly interpret M.

for every x in A > b, height(x) > height(b)
but there *may* exist items in A >< b that have height(x) > height(b)

if we know the height of the missing fields, we can incrementally expand two sets.
first we check the messages prev to missing. if any are not in Have, we expand Have
by adding every Have->prev until at the same min height as Missing.
then we repeat with Missing->prev