A State-based CRDT without Infinite Growth

[synctext]

Goal: upload and download byte accounting, detect freeriders, and refuse service.

Requirement: privacy is a cradinal requirement, only count bytes with a certain accuracy and never leak what is being downloaded or relayed. Side channel attack danger.

• Sharing ratio tracking
• parity of contributions
• multichain deploy and crawl
• ask ratio
  • reject/accept
  • forgiveness, robustness, fairness

[synctext]

Thesis (2).pdf

Feedback: expand 2-page intro with indirect reciprocity, tragedy of commons, leftist-stuff is OK in foreword, rest needs to be boring & scientifically grounded.

Chapter 1, ThesisReady: tragedy, iterative PD, freeriding, single-point-of-failure, tribler attempts at finding mechanisms to build trust

[synctext]

Thesis (3).pdf
Feedback:

• "Not only are these systems useful to overcome virtual restrictions", too fast buildup of storyline.
• "human nature is not that depressing", use neutral scientific observation language.
• Expand: multichain in intro
• focus problem description .tex
• Afterwards: coding reward -- payout in anon chain

Storyline: tragedy, iterative PD, freeriding, single-point-of-failure, tribler attempts at finding mechanisms to build trust

[synctext]

Result of quick update session. Stop deleting bad text for one cycle. Create brainfart version of:

• picture(s) for "payout and relay incentives" sub-section
• add repeated interactions mechanism to discussion "payout and relay incentives".
• Pro- and Con- of whitelisting or blacklisting cheating agents in "payout and relay incentives"
• "experimental setup" Section
• (write down text for figures which are not there yet) "Implementation and experiments" section

[synctext]

new .pdf @Captain-Coder ?

[Captain-Coder]

Please see here for the most recent version.

[synctext]

Comments on recent thesis version. thesis (46).pdf

"There are several elephants in the room when translating this high-level concept to an actual implementation."

Brainstorm ToDo list:

• experiments, Gumby. MultichainExperimentClient

• Afterwards, screenshot content for blockchain browser (Design & implementation chapter)
  

[Captain-Coder]

The most interresting experiment we could do, is to verify that the multichain can actually be used to reject free riders. The experiment I want to should thus show that with multichain disabled free riding is possible, especially over multiple download sessions. When multichain is enabled the experiment should show that those that could still free-ride before will now be rejected.

For example: Start 100 nodes in 4 groups: 40 nodes will download and seed upto ratio 1.9, 20 free ride low (ratio 0.8), 20 free ride medium (ratio 0.5) and 20 free ride heavy (ratio 0.0). Each node has a 200KB/s maximum upload throughput and an unlimited donwload throughput. Sequentially perform 15 downloads of 20MB. 4 nodes will be picked randomly (uniform distribution) to serve as seeds for each download. This should mimic periodic content releases over time. Plot download speed over time for each node, colour by node grouping. If multichain works as advertized, we should see the download throughput of the 3 free rider groups converging towards their respective sharing ratios or lower. Importantly we should see some of the 15 downloads no longer completing. At the same time the other nodes should see a modest increase in throughput. If multichain is disabled (or does not work as advertized) we should see all downloads completing, and all nodes getting roughly equal throughput.

This would need tribler to meddle with the workings of libtorrent, which might require some engineering effort. Alternatively it should be possible to run this experiment through hidden tunnels, which are easy to control based on multichain scoring.

[synctext]

First, small scale validation experiment. Easy to understand and check manually.
Community-level emulation, 100 nodes. Good Ewout idea: string of 15 downloads.

Hard threshold policy for rejecting relay requests. Please focus on evaluating and testing a hard-coded 3 GByte freeriding limit.

Sadly it is likely that only positive reinforcement policies will scale and resilience against simple whitewashing attacks.

[synctext]

"The following deliberately simple experiment demonstrates our access control decisions. Requests by freeriders are rejected."

[synctext]

Key objective minimal-validation-experiment: 1 downloader from 1 seeder. Repeated downloads, then gets rejected by the tunnel community proxy. (e.g. 3 GByte freeriding limit, 250MB file downloads, blocked after 12 times)
Only tunnel stuff has the reject ability, minimal requirement is 2 proxies.

[synctext]

Requirement: crawl neighbors (with Quinten).
Key objective 2 full-validation-experiment: Community-level emulation, 100-ish nodes.
Key objective 3 minimal-validation-experiment: parity of contributions: seeder, proxies, downloader

Scientific question: placement of reject policy (during rendezvous proxy setup?)

Very future work (do not work on this in 2017 please!): priority-based queuing mechanism, thus give away bandwidth to highest ratio/upload peer and pre-empt low-level contributors.

[synctext]

Gumby experiments required re-work. Tribler tries to re-use tunnels after first-time usage. But that goes wrong. Second download sees no fresh tunnels are needed, but libtorrent or something can't really use them. Ongoing investigation.

Plus Gumby uses the mainline public DHT network for all tunnel activities. Ongoing tribler fix and Gumby PR.

How close to operational code? Few weeks..

The current true halves tries to somewhat do a light check on previous hash. When getting a signature request Tribler now always requests a few blocks and fires up a deferred in 5 seconds. Only if the integrity of Trustchain is correct we put our signature down. Also we moved beyond the sign-anything policy, byte accounting is checked (rounded to 16KB blocks or so+fuzzy factor).

[devos50]

@Captain-Coder where is this fuzzy factor exactly? I haven't encountered it so far in the code base or did I miss something?

[Captain-Coder]

@devos50 Yeah seems you're right. I'm quite sure PimV and me agreed to put it in. But apperently we never did.

It definately should be in there though, i'm already seeing tons of "not enough outstanding credit" errors in my experiment, even though there is no malicious node and everything works via localhost. I suspect the counters in (hidden_)tunnel_community.py are nog counting the same thing going out as comming in. I'll probably need to fix this for my experiments.

[synctext]

ToDo: 3 pages of master experiment thesis material.

• 2 graphs of full-validation-experiments, with reject ability. (X-axis time, Y percent completion). Other graph blockchain dissemination in time (how many known blocks in time).
• describe experiment in detail with pictures included, 3 pages. Detailed thesis writing style.

[synctext]

Update: DHT isolation PR needs rebase.

Excellent bug hunting, anonymous DHT in Tribler results in identity spamming. Our small exit node community gets abuse blocked by most DHT implementations. We mix introduction IP:ports with exit node IP:ports (exits get DHT blocked, introduction points run their own DHT instance).

[synctext]

Update: Tribler patch was needed for current Arch Linux support of Tribler, Libtorrent 1.1.1 series and Socks API.

We moved to Tx block inside transaction of Trustchain. This binary blob is put straight into the Tribler SQL table Triblerchain_blocks. Aggregation queries are now impossible from SQL (e.g. requires character extraction). Somewhat working code of reject policy based on MBytes.
We have true halves, plus implemented policy to ignore all MByte on Trustchain if it is not counter-signed.
Ongoing work:scoring function in MBytes. Semi working Gumby with 2 seeders, relays, and 4-ish downloaders. First reject policy results in 1-2 weeks. 4 hours of runtime.

Real experimental results: full devel hidden seeding code with DHT isolation (== remove bootstrap nodes). Experiment duration is determined by file size above trustchain counting limit and below 10min tunnel lifetime x amount of swarm downloads.
O yeah, working Raspberry pi box, 50 KBytes/sec anon downloads.

[synctext]

Thesis material also include global re-factoring and end-to-end deployment testing+fixes.

There are both outgoing and incoming tunnel_extend requests. Both trigger the calculation of scoring function. Major refactoring task of the Tx block and SQL usage. Python type inheritance of Trustchain to both Triblerchain and Tradechain. Our approach is merely code sharing not data sharing or data duplication. Tx block is parsed and optionally split into fields. Dictionary of Tradechain can't be split into fixed fields, thus remains a blob. Not fancy, no realistic alternatives, but required.

Raspberry pi, build script of Libtorrent and Tribler core (no GUI).
ToDo: cut-off experiment, 1-ish week.

[synctext]

Ongoing DHT isolation PR since June 8.
Now writing thesis text, experiment chapter.

Warning: at End of December the phd students of Tribler team will work full-time on fixing the credit mining+payout through tunnels. Key feature for Tribler project, earn credits by donating disk and bandwidth...

[synctext]

Add to thesis our Tribler publication "Paying the Guard: an Entry-Guard-based Payment System for Tor". Quote from draft thesis:

A naïve scheme could be to compensate relays for their bandwidth usage, both up and down where the
downloader at the end of the proxy chain has to provide this compensation. Such a scheme is doomed to fail for the following reasons.
[...]
Everyone has to wait for the payment request to eventually
reach the downloader and for the payment to propagate back along the circuit. 

Your attacker model assumes people deviate from the protocol. Human behavioral studies (including ours) has showed this to be incorrect, the overall majority is honest or follows the default.
Let's call this the opportunistic token economy...

[devos50]

The first step towards proxy/exit node payouts is done: a very basic experiment to perform hidden seeding and downloading (one hop, one circuit, one downloader and one seeder). See https://jenkins.tribler.org/job/pers/job/hidden_seeding_devos50/.

(annotations in the graphs above are bugged for some reason)

Next step: integration of TriblerChain + implementation of payouts.

UPDATE: TriblerChain is running correctly, next to the hidden tunnel community. Left: implementation of payouts.

[synctext]

solid milestone. Perhaps we want to expand this Jenkins job to annotate the various .PNG file with start,stop, etc time markers. Like unit tests and Allchannels.
Work towards a few article+thesis inclusion graphs.

[devos50]

@synctext the graphs above have annotations (the green/blue/red vertical lines) but the text is not visible for some reason. I suspect this has something to do with the way the graphs get rendered on our bbq server. I noticed that annotation texts are quite unreliable in R and they display if I render them on my own machine. While not top priority, we should look into this at some point.

[devos50]

Additional meeting notes 06-04-2021:

• Explain why you focus on collections of unordered data elements in the system model.
• To search an element in the Ewout data structure, you first search the R-tree with log complexity, and then we do a linear scan in the associate BloomCRDT.
• You assume a system parameter: the initial size of the Bloomfilter. Please elaborate in the text.
• Experiment idea: show how long it takes before the storage requirements of a CFRT become better than that of an OR-set.
• Please structure your system model using a list. “We make following assumptions:” …
  • Messages may arrive out of order: we assume unordered communication channels.
  • You assume global resolvability, e.g., using IPv8 communities or a DHT.
  • For every assumption, explain why it is reasonable.
• Make separate subsections: “Advantages of BloomCRDT / Advantages of CFRT”.
• Defend the need for the CFRT. We now have BloomCRDTs in the network, peers are joining/merging them and sharing them with others. What is the next step now?

[Captain-Coder]

report.pdf

In addition to the text, I have made progress on integrating my stuff into a gumby experiment.

[devos50]

Meeting notes 12-04-2021:

• Please write a small abstract to accompany the progress email to the committee.

For next week, please finish your first experiments. Post the graphs here.

Tentative planning:

• May 24: finished experiments.
• June 1: finished conclusions.
• June 15: finished introduction.
• July 1: polish finished, hand in thesis.
• July X: hand in thesis.

[Captain-Coder]

entry_count.pdf
entry_size.pdf

Nothing much to look at but I'm happy the gumby+ipv8+pycharm+postprocessing+custom experiment scenario is now setup.

[devos50]

Meeting notes 19-04-2021:

• Experiment pipeline up and running! Includes Gumby + R post-processing scripts + IPv8 messaging. CFRT implementation missing.
• You can work on Section 5.1: implementation details (explain IPv8, communities, messages, …). “We have chosen IPv8 as networking middleware because it ticks all the boxes and is the de-facto networking library adopted by our lab”.
• Describe the experiment setup (section 5.2). Network topology, peer behavior etc.
• First experiment with 5 nodes.
• First (primitive) graphs are there and show that the size of your BloomCRDT is bounded.
• Suggestion: micro-benchmark the merge operation under load.
• First experiment: compare with the naive OR-set, show that the size of the BloomCRDT is adaptive. Different workloads: 1) append-only, 2) add+delete, 3) concurrent adds (e.g., in bursts).
• Second experiment: scalability. How much adds/deletes can we tolerate? Show relation between number of nodes and the data structure size.
• For the sprint after this one, please focus on implementing the CFRT. Afterwards, we can focus on more sophisticated experiments.
• Experiment with realistic data: take the biggest channel in Tribler, replay torrent insertion/deletion. Show the overhead in network communication/local storage requirements/processing power.

[Captain-Coder]

I found that the experiment with different work loads was becomming to complex. There is too much going on for a first experiment to explain properly. I am already questioning this simple setup.

report.pdf

Proposed structure for chapter 5 including experiments

[devos50]

Meeting notes 26-04-2021:

• Suggestion: rename chapter 5.1: Implementation, chapter 5.2: Experiment Setup (describe your experiment settings/environment/workload etc.)
• Rename 5.2 to "BloomCRDT Experiments"
• At the start of 5.2, please introduce some "experiment research questions" that you are going to answer (can be done later).
• Recommend to use theme_bw() for the plots, move the legend within the plot.
• When you have many experiment parameters, list them in a separate table.
• Describe the cooldown time.
• Seeing interesting spike in figure 5.1b, either explain this result or start your data logger later.
• Term 'replica' confusing, use "total active nodes". Use 'n' to indicate the total number of nodes in your experiment.
• Start with your positive results, then show that the number of elements remain roughly the same for the OR-set and the BloomCRDT.
• Different workloads are interesting to see! Show that your data structure shines when the workload contains the removal of elements.
• Next experiment planned: show trade-offs in P2P environment. Show that vector clocks don't perform well in open P2P networks. Consider adding realistic latencies to this experiment.
• Please finish the storage experiments first. Maybe end each paragraph with something like a "main finding".
• Resistance of BloomCRDT against Sybil attack/spam (for other compared systems it would be a DDoS attack). Vector clock overload.

For next week, finish the storage and P2P experiments.

[Captain-Coder]

Here is this weeks progress.

report.pdf

I'm going to ask for a day off work on the 11th (and possebly the 12th) to get some extra work done.

[devos50]

Meeting notes 03-05-2021:

• Move the URLs to a cite in 5.1.
• ‘not worth the trouble’ informal language.
• What are the difficulties when implementing your code? Lines of code? Unit testing?
• Suggestion: make a table where you state the lines of code for each component of your work. Overlay logic, BloomCRDT, CFRT.
• Implementation section is not very convincing yet; please add a bit more context and describe engineering challenges that your encountered.
• Please remove the last sentence of the leader of Section 5.2. You can repeat the novelty of your solution in the first sentences of 5.2.
• Beginning of 5.2.1: our hypothesis is that …
• We conduct an experiment … (use active voice for the experiments).
• Align graphs at the top of the page.
• “We emphasise that the size as shown in the vertical axes of Figures 5.1a and 5.1b is the required network overhead to disseminate the data structure to another peer and directly correlates with network usage.”
• Remove experiments 5.1c and 5.1d, I don’t think they add much.
• Explain why the lines in Figure 5.1a grow with different rates.
• Include the OptOR-Set in the first experiment?

Suggestions for experiment flow:

• Always use the algorithm as group variable (OR-Set, OptOR-Set, BloomCRDT (this work))
• Graph 1: horizontal axis: time into experiment, vertical axis: average message size). Fix n=100
• Graph 2: horizontal axis: identities encountered, vertical axis: average message size).
• Use different workloads: create-and-delete workload and append-only.

[Captain-Coder]

report.pdf

Much to discuss. Engineering (and experiment integration) on CFRT is done. Done text up to 5.2.1, Experiments done up to 5.3.2

[devos50]

Meeting notes 10-05-2021:

• Polish the legend of your graphs, make it shared (e.g., on top of the figure).
• Figure 5.1: please make the lines more thick and use separate styles for the graphs.
• Axis text is too small for readers.
• Explain the sub-linear
• Split Figure 5.1 (horizontally) in three separate figures. For each Figure, make sure you have one paragraph explaining the results.
• Make a Figure 5.4 with the join()+deserialization time.
• For each graph, explain what’s on the horizontal and vertical axis.
• Explain your observations in Figure 5.2.
• Please use subsections to explain the modules of your implementation, or use \textbf{…} before each paragraph.
• Add a system architecture, showing how each component communicates with the other. Show how your system and components interact with the network layer and the application.
• What is the unit of the ‘average merge time’?
• Add a key graph showing the savings of the CFRT! Compare it with your BloomCRDT.
• If you are not going to compare with the MST, please explain why.
• To DAS5 or not to DAS5?

[Captain-Coder]

report.pdf

[devos50]

Meeting notes 17-05-2021:

• DAS5 experiments are setup!
• When adding more nodes, there are more operations in the network (higher workload).
• Gumby has built-in CPU profiling, you can import the ProfileModule to enable this functionality.
• You are running multiple experiments within a single DAS5 job. This might lead to (unintentional) skewed results.
• Figure 5.1: please mark what belongs to your experiment and what belongs to your CFRT/CRDT implementation (e.g., with a dashed border box).
• Give a small snippet of a scenario file, just to give some ideas on how you are running the experiments.
• “Gumby allows developers to quickly setup and run experiments in distributed environments”
• Size of figures require some polish. Also consider using different linestyle (for black/white printing). Linewidth can also be increased.
• Figures that should be compared should use the same y-axis and same limits.
• Touch -> rename to: “fetch”
• Key result: given a CFRT, the number of check operations is logarithmic in the total number nodes in the tree.
• Make sure that the axis have proper labels and units (if applicable).
• Figure 5.7e and 5.7f, make sure they are using the same y-axis limits, makes comparison easier.
• I would like to see 5.7e and 5.7f with an add+delete workload. Please make this specific in your caption.
• Final experiment: fault tolerance of CFRT. Add packet drop to the IPv8 endpoint. Show information convergence in the network.

[Captain-Coder]

report.pdf

Turns out 90% packet loss is not an unsolvable problem
CFRT plots wouldnt come out right. so they are unfortunately missing, but can be previewed in the latest jenkins runs https://jenkins-ci.tribler.org/job/pers/job/ewout/job/cfrt_experiment/22/

[devos50]

Meeting notes 25-05-2021:

• Experiments are mostly finished!
• Figures in 5.3.1 and Figure 5.8 are broken. Please fix these plots for the next meeting.
• Please elaborate in Figure 5.9 what the difference is with Figure 5.8.
• “Even though we acknowledge that such a large packet drop rate is non-existent for practically deployed networks, it reveals the robustness of the CFRT data structure.”
• I will provide feedback on the experiments later (either tomorrow or the day after tomorrow).
• Next spring: introduction!
• Start your storyline with elaborating Big Tech. “Big Tech has a unprecedented amount of power in our current society” -> “As countermovement to big tech, there is local-first software”. Then introduce decentralisation. Then: “one approach to realise local-fist software in a decentralized network is by using CRDTs.”. This thesis focuses on …
• Try to add the research question at the end of Section 3.
• In the introduction, please add something like: “This thesis focusses on X and Y.”
• Zoom in on one or two of the ideals of local-first software? Especially in the context of distributed systems.
• Please add a figure with an architecture showing a traditional client-server architecture and a decentralized architecture.
• Shortly mention CRDTs in the introduction.
• You can move 2.2.1 to the introduction.
• Mention Tribler as leading example of decentralized local-first software. Include a screenshot of Tribler (please filter out any copyrighted material!!). Add a screenshot of the FMA channel.

Suggestion to organise your introduction:

• Start with Big Tech
• 1.1: “Local-first software”
• 1.2: “Towards decentralized local-first software”
• 1.3: “Our contributions”

[Captain-Coder]

report.pdf

Ready for feedback on chapter 5

[devos50]

Feedback on Chapter 5:

Major feedback:

• Several typos, please run a spelling checker to identify and address them.

Implementation:

• Start your chapter with: “This chapter first provides implementation details on the BloomCRDT and the CFRT data structures. We then present an experimental evaluation of our solutions. Our experiments focus on X, Y and Z.
• Minor stylistic issue: I usually add a ~ between the references to improve readability (e.g., bla bla~\cite{X}).
• Before your list of existing implementations, add: “Below we list existing solutions and their technical characteristics”
• “python2” and “python3” change to “Python 2” and “Python 3”
• usefull -> useful
• Add: “We believe that the evaluated libraries do not provide the functionality that we need, and we consider extending these solutions as sub-optimal time management. Therefore, we decided to implement the BloomCRDT and CFRT from scratch in the Python programming language”.
• in process use -> in-process use
• You can add somewhere: “Our implementation contains a few optimisations but we believe further optimisations such as X and Y are possible to further increase performance and scalability”
• “a more efficient method of computing hashes was implemented” can you give some more details on this?
• “and the CRDT set primitives at 328 LoC” this sentence looks incorrect.
• nessecary -> necessary
• refference -> reference
• can you list the message types that you use with a small explanation, e.g., in a table?
• elemens -> elements
• Mention that the Gumby CFRT module contains code related to experiment management?
• DAS5 reference is broken

BloomCRDT experiments:

• Use enumerate instead of itemise
• Add just before the two advantages: “As a reminder, we repeat these advantages below:”
• You can make the second advantage a bit more dramatic: “[…] then it could grow to disproportional sizes in open P2P environments”
• “The OR-set was chosen” -> “The OR-set was chosen as baseline” (same for the OptOR-set)
• you use “On the other hand” but there is no “on the one hand”.
• 5.2.1 is quite a bit of text. You can mark paragraphs with \textbf{…}, e.g., \textbf{Experiment Setup.} and \textbf{Results.} (don’t overuse this though)
• “The sets are allowed to reach eventual consistency” this is not clear to me, why do they need “permission” to reach eventual consistency?
• “each replica starts two processes” is this a system process? Consider using “routine” if it’s not a system process.
• (5.2.1) with which peers does a peer exchange its CRDT state? all of them? Or a subset?
• Suggestion to use \texttt to indicate Python libraries such as pickle.
• “On the otherhand” there is no “on the one hand” + typo
• “efficient enough to keep up” to keep up with what? How?
• Reference to Figure 5.2 should be 5.3.
• “1 order of magnitude” -> “one order of magnitude”
• “Each graph shows experiment time” -> “Each product shows the time into the experiment”
• “Figure 5.4 shows the sum of figures 5.4” -> should be: Figure 5.5 shows the sum…”
• “Other solutions like […] would show results similar to the OptOR-Set” why so?
• “fixed at” -> “fixed to”

CFRT experiments:

• “a singleton BloomCRDT should show linear growth” growth in what dimension?
• “is represented by a single CFRT node with infinite bounds” these bounds are not clear to me.
• “5.7a shows count of” -> “5.7a shows the count of”
• y axis -> y-axis (but you should rather talk about the horizontal/vertical axis).
• systen -> system
• fault tollerance -> fault tolerance
• I think the term ‘convergence’ should be specified better. Lines that are similar (in Figure 5.8) is not a very scientific explanation.

Section 5.4:

• You can end this section with a few ‘suggestions for further experiments’ but this should follow a clear structure like other paragraphs. 5.4 currently reads more like a small TODO list. Maybe re-write it to a ‘discussion’ sections where you summarise the most important results of your experiments. Also defend here that a large-scale application-specific experiment (e.g., replaying Tribler channels) is a next step but intentionally left out of scope due to time constraints.

[Captain-Coder]

report.pdf
Lots of TODOs still, but I belive the story line is there now. It makes sense to me atleast.

[devos50]

Meeting notes 31-05-2021:

• Through ubiquitious means, e.g., with a website, mobile application, or enterprise desktop software.
• Introduce the term Big Tech, actual spelling: “Big Tech”
• Add some numbers, show the impact of Big Tech!
• Local-first software is about data autonomy and independence of a centralized party. Related to vendor lock-in?
• Structure of the first paragraphs:
  • 1. introduce Big Tech, add some numbers, show their influence
  • 2. elaborate on the concept of data autonomy (e.g., “Big Tech deploys centralized servers that manage all data and interactions by and between users”).
• First sentence 1.1: “A counterforce to the lack of data autonomy is LFS”.
• Define local-first software in your introduction.
• You can use Bintray as an example to show how dependency on centralized companies can lead to issues when they decide to discontinue their services.
• “Responsiveness and Availability” search for references regarding continued downtime (e.g., Reddit). The impact of service disruption can be significant, even if it’s only an hour of downtime. LFS also has the potential to decrease user latency since it sidesteps the need for communication with a centralized server.
• Seamless collaboration should be the last point you discuss since it closely relates to your work.
• Big Tech collaboration software forces you to use their services, infrastructure, and workload. Maybe App Store vetting as example?
• Before 1.1, in the first paragraph: Big Tech provides convenient access to information (one-stop shop).
• A local-first software implementation without centralized system requires coordination amongst users themselves, which is non-trivial to achieve.
• Add a figure, showing a centralized vs decentralized systems.
• Be consistent when enumerating: firstly, secondly, thirdly.
• Nice sentence: “Tribler brings Big Tech features without Big Tech”
• Describe Tribler according to the three discussed principles of LFS.
• Section 1.3: “Local-First Software in practice: Tribler”. Show that Tribler has some issues that can be addressed by a CRDT, incomplete because …
• Section 1.4: Thesis outline and Contributions: “In this thesis, we address this research gap. We …”. We take an experimental and practical approach to address this issue, in stark contrast to existing related work that is mostly theoretical.

For next week, please finish the introduction and start working on the conclusion.

[Captain-Coder]

Also as discussed, chapter 5 will not be sent for a separate review but combined with Introduction and Conclusion as a complete draft.

[Captain-Coder]

report.pdf

Intro should be Ok (not spell checked yet),
Added "4.3.4. CFRT compared to DHT" cause I know ppl are going to ask about it.
Outlined conclusion, i have too many research ideas.

[devos50]

Meeting notes 07-06-2021:

• Figure 1.1 should be improved; show client vs. Server on the left side and only clients on the right side.
• Split Figure 1.1 in 1.1a and 1.1b.
• Remove ‘distributed systems’ from 1.2, defer the discussion of distributed systems to Section 2 (background and state-of-the-art).
• 1.3 is a bit on the shorter side. Show how Tribler meets all the requirements for LFS.
• “We envision a data structure that can benefit applications like Tribler”
• Consider making a list of your contributions.
• Thesis is content-complete; requires more polish
• Please end 6.1 with an overarching conclusions: “we believe our data structure can improve existing P2P networks…”
• Merge Section 6.1 and 6.2
• Section 6.1: Conclusions, Section 6.2: Further research
• Overall spelling check highly advised, consider using Texidote (https://github.com/sylvainhalle/textidote)
• Leader conclusions”: “We end this thesis with stating the conclusions and do suggestions for further research”.
• Mention latency aspects when describing MMO gaming.
• Jump from 1.1 to 1.2: End 1.1 with Big Tech, then discuss that Big Tech usually uses centralised components to realise their software. Given advantages + disadvantages, then introduce decentralized systems, discuss their advantages/disadvantages. Use Figure 1.1 to support your discussion.
• Thesis title: remove the word ‘index’. “A Scalable, P2P-compatible CRDT”.

For this week, focus on polishing the problem description. Make sure it matches with your experiments, and conclusions.

[Captain-Coder]

report.pdf

Perhaps I'll have time to spellcheck/textidote tomorrow morning before the meeting.

[devos50]

Meeting notes 14-06-2021:

Abstract:

• In the abstract, add a sentence explaining what a CRDT is.
• Infeasible in terms of … ?
• We adress the aforementioned problems and propose a new …
• R g-set not very clear. Suggestion: replacing grow-only sets with a probablistic data structure, a Bloomfilter.
• … More suitable for open P2P networks.
• BloomCRDT does not scale … in which dimension?
• To address this -> to overcome this problem
• What is an inconsistent data structure? Maybe you could reword this?
• … Thus remaining efficiency. How?
• Experiment conducted on our nation-wide supercomputer.
• Add: “We implement both BloomCRDT and CFRT. We the conduct experiments …”
• Abstract has an an abrupt ending!
• Can you insert the word ‘fault tolerance’ somewhere?
• “in extreme adverse conditions”
• “Still remains functional”

Introduction:

• Big tech acts as ... (avoid the word ‘assume’)
• Briefly explain what a CRDT exactly does in the introduction.

Related work:

• Cite and discuss FabricCRDT
• Please do a last check to see if you can also include very recent work.
• Some recent from Kleppmann.

Problem description:

• Use \textbf{} in the enumeration of 3.1.1.
• Link back to the text where you introduce Tribler (e.g., see Section X).
• Please number the criteria in 3.2.
• Your last criteria is closely related to criteria 2. Say in the text something like: “This criteria is closely related to criteria 2 since…”

Section 4:

• The first innovation is BloomCRDT, an …
• In 4.1, please motivate why you are making particular assumption.

Conclusions:

• The first sentence of the conclusion is negative. Start with something positive.
• Some section references are broken.
• End 6.1 with: “we envision a broad usage of our CRDT across many application domains, including …”
• Typo in title of Section 6.2.

Overall:

• End the bold small introductionary texts with a period.
• For more polish, you can add a tilde between the word and the citation (e.g.,: bla~\cite{X}).

[devos50]

While we’re waiting for the formal thesis defence procedure to start, I’ve gone through your thesis again, up to Section 4. I think the following feedback should keep you busy 👍

Overall:

• Content-wise thesis is in a good state 👏
• Make sure "Figure", "Section", "Chapter", "Table" etc. are always capitalized when referring to a particular element (so not: "in figure 1 we show X" but: "in Figure 1 we show X".
• Tribler is currently mentioned both in the introduction and problem description. Both sections refer to the management of channel elements. For the next thesis step, I strongly suggest to perform an experiment with Tribler channels and show how your system addresses the raised issues. This would definitely give the thesis more substance.
• Is the Sybil attack mentioned anywhere? This is key to address when talking about open P2P systems. At the very least, mention that this is out-of-scope of the research.

Abstract:

• Please number the disadvantages in the first paragraph of the abstract for more structure: "We identify three problem. First, ..."
• “A new state-based” (the dash is missing here).
• "To address this, multiple BloomCRDTs can be combined to form a Conflict Free R-Tree (CFRT)
  " -> you can make this statement stronger: "We further improve the scalability of our data structure and combine multiple BloomCRDTs into ..." (Now it is written a bit passively).
• "thus maintaining efficiency" -> efficiency in what sense?
• "works in P2P environments" -> this can be stronger, maybe "excels in P2P environments"?

Introduction:

• Can you give an example of a LFS system that has sunset and disrupted the work of end users?
• "this is a sharp contract" -> "this is in sharp contrast to..." ?
• "Figure 1.1 shows an example structure" -> "Figure 1.1 shows an example network organisation" (be more specific)
• Divide Figure 1.1 in 1.1a and 1.1b. Reference them separately in the text.
• "Firstly from a technical point of view" -> "Firstly, from a technical point of view, ..." (Add commas)
• In the first paragraph of 1.2, you mention that sometimes central components are unavoidable but then in the next paragraph, you say that they have three aspects so they are fundamentally undesirable in a distributed system. These statements look to be in conflict.
• Mention fault tolerance in your first argument in the 2nd paragraph of 1.2.
• Mention infrastructure and operational expenditure in your third argument in the 2nd paragraph of 1.2 (be more specific)
• Reference to Figure 1.1b in the last paragraph of section 1.2.
• Add a few citations to our prior work in the first paragraph in Section 1.3.
• "real world end users" -> "Internet-recruited volunteers".
• "..., not just academic benchmarks" -> "..., going beyond the standard evaluation methods of the academic community".
• "Provides this functionality without global infrastructure" -> "Provides this functionality without central point of control".
• "The current channels implementation can not accomodate the scale needed by some of the larger channels." Please explain why this is. Is it due to the protocol design?

Section 2:

• I really like this chapter! Mostly some minor grammar/consistency feedback here.
• "well known theory" -> "well-known theory" (there are a few more instances throughout the thesis that require a dash between two words).
• Maybe mention in 2.2.1 that states could be hard to merge since they could contain arbitrary application logic, potentially requiring an application to resolve conflicts on multiple aspects of the state.
• "In table 2.1 there are 4 common ..." -> "In Table 2.1 we show four common ..." (Capitalization + spelling out of numbers).
• The grammar of the first two sentences of Figure 2.3 are a bit off. You can also consider making 2.3a and 2.3b bigger and to align them vertically (you have a full page there).
• Section 2.5 feels a bit detached from the main storyline. Please signify the relevance of 2.5 already in the first sentence and show why the reader needs this knowledge to advance to the next section(s).
• "... include ZFS, bitcoin, git and Risk" -> missing references, also: "to name a few" is informal, consider something like: "... with X, Y and Z being the most significant applications using this primitive".
• "over a key space, a Merge Tree is not ..." -> this sentence requires more structure, e.g.: "therefore, a Merge Tree is not a ...".
• "The Merkle Search Tree (MST, [4])" -> split the abbreviation and the reference: "The Merkle Search tree (MST) [4] ..."

Section 3:

• "The sections on applications show" -> please be explicit here: "Section X and Y conclude that..."
• The first sentence of 3.1 uses the word explained twice, should be revised I think.
• "Next, section 3.2 describes how these problems impact a real world application." -> talk about the requirements of CRDTs in open P2P systems here.
• In 3.1.1, what do you specifically mean by "state size"? Can you define this in a more rigorous manner?
• "Since most existing applications of CRDTs are in collaborative software, it is reasonable to assume that the collaboration will cease eventually" do you have a citation to backup this argument?
• In what sense does a large state become "impractical"? Please expand on that.
• "The problem with a vector clock is that it:" suggestion to replace this by: "We identify three problems with using vector clocks".
• "The first step would be to discover, world wide, all replicas of the Linux kernel repository." Add some numbers here - are there estimates on the number of replicas?
• "Recurs to section 3.1.1 to read about the problems of grow-only data structures." -> I like the joke, but it breaks the storyline. Consider removing it.
• "This means that CRDTs have not found their way into P2P distributed systems" -> well, they did, but not in open P2P systems (add this nuance).
• "CRDTs consist of two types of data: application state is used by the application built on top of the CRDT, and metadata is needed to make the CRDT function but has no direct value to the using application." This is quite an important distinction and should be mentioned earlier. Maybe at the beginning of 3.1.1 already.
• "the delay after which eventual consistency is reached could be at infinity" -> "... could be infinite" (or more scientific: there is no upper bound on the convergence time).
• "ConTrib expressly avoids globally distributing block chains." -> suggestion: "ConTrib avoids expensive full replication of the global state across all peers".
• "Most importantly, a replica might not need the complete data structure in order to function." -> can you give an example here?
• At the beginning of 3.2, put a reference back to the Section where you explain Tribler (to remind the reader).
• "Lets assume this is some 2KB per torrent." -> "We assume that each torrent requires 2KB of state storage".
• "If it does then it should meet these criteria:" bit informal, suggestion: "We argue that any CRDT structure that can work in an open P2P system should exhibit the following four requirements:".
• There are a few typos in 3.2.
• "... encoded into the data structure, this is a ..." -> "encoded into the data structure as this is a ...".
• "No unbounded growth In both application state and metadata there should not be unbounded growth since this is not compatible with the persistent nature of Tribler’s channels." You are talking about the generic requirements but now rely on a single application.
• "Not push based" so pull-based?

[devos50]

Additional feedback on Chapter 4 (design):

• "... that vastly reduces the unbounded growth and op- erates in an open P2P environment" nice, but how? Please add one or two sentences explaining the key idea behind your approach(es).

Section 4.1:

• Your assumptions could use a bit more argumentation. Why exactly did you make these assumptions? For example, add some cites that show that message delivery is usually imperfect in P2P systems. And that peers/links may fail (what about Byzantine behaviour?). Also, use the word "churn".
• "Each peer can message a (small) subset ...", suggestion: "Each peer knows the network address of some other peers in joined groups".
• Add: "We make standard cryptographic assumptions, i.e., cryptographic primitives such as hashes and digital signatures are considered secure."
• Do you assume an unpermissioned network?

Section 4.2:

• Overall ok section.
• Put the first occurrence of "overtaking delete" in an \emph{} tag.
• "These concepts are not suited to an open P2P environment." Why not?
• "If only there where a space efficient" slightly informal, suggestion: "We envision a space-efficient ..."
• Remove the word "luckily" at the start of the 2nd paragraph in 4.2.2.
• Put the "Bloom Filter alternatives" as last point (I think it's the least important, parameter selection/false positive rates are more important).
• State the key idea somewhere in 4.2.2: "We replace the static list of identifiers with a probabilistic data structure and significantly reduce storage requirements of the OR-set".
• The fact that there are multiple Bloomfilters in a single BloomCRDT element is not properly explained. Please elaborate on that.
• (if time allows) After reading 4.2.3 again, I think some pseudo-code for the join of two Bloom filters would be helpful.
• "A simple strategy could be to double the capacity compared to the last Bloom Filter." Could you maybe hint at a more complicated policy?

Section 4.3:

• "With linear complexity on" complexity in the number of contained elements?
• "the most difficult part is correctly maintaining the links between the BloomCRDTs" why do we need a link in the first place? Can't we just merge them all? This requires a bit more explanation.
• "fan out factor" -> "fan-out factor" (there are more instances like this in the thesis).
• (caption Figure 4.4) "The diagram shows an example ..." Suggestion: "A R-tree where each edge ..."
• (caption Figure 4.4) you are using the word "edge", is this the proper terminology when talking about a tree?
• "If the root node has only 1 child" -> "If the root node has only one child"
• Do peers in the network now exchange CFRTs? Or does every node have their own CFRT and share BloomCRDTs? Requires a bit more explanation how this would work in a P2P environment.
• "After adding a few thousand elements the BloomCRDT becomes very inefficient." I would like to have this sentence earlier, e.g., somewhere at the start of 4.3. Also, inefficient in what dimension? Storage?
• "In addition to mapping the R-Tree node ..." Missing ending period.
• Section 4.3.4 feels unfinished. Does it require a separate subsection?

General:

• Make sure all figure captions end with a period.

[Captain-Coder]

I focused on getting the last experiment to work. It now does and surprise surprise cfrt works way better than stuffing a channel into a torrent. From a user's perspective. I think the tie-in text could be sharper, it was a bit late when I wrote that. I had to go log() on the graph y axis or the cfrt would just be a single line on the 0. I feel this could be formatted better, but I'm unsure what numbers to choose. Also the x axis is clipping on the right, dunno yet how to fix that.

The result of focus on the experiment is that some feedback points are still open. Those will be adressed today.

report.pdf

[devos50]

Meeting notes 16-08-2021:

• Almost ready for defence!
• Move the experiment to a separate section.
• Move the rant in 5.3.3 to 3.2 and refer back to 3.2 in 5.3.3.
• Please add the specifications of your workstation (for reproducibility).
• Figure 5.10 polish is still required.
  • Disable scientific notation on the vertical axis.
  • Figure 5.10 is actually a (E)CDF.
  • Add number separator to the break labels on the horizontal axis.
  • Explain the spike at the right side of the figure.
• Please add the source code as footnote in your thesis. Also, please move your code to a Github repository so we can transfer it to the Tribler organisation.

[synctext]

Final thesis on official TUDelft repo 🎊 Scientific highlights from thesis:

• Pull paradigm, never push. "A peer should be in charge itself about what information to fetch and at what time.", page number 18.
• Forgetting is essential. "Any solution that permanently stores (meta)data about other peers will show unbounded growth since P2P networks are subject to a constant influx of new peer identities.", page 18.