Filament : a cohort construction service for decentralized collaborative editing platforms

Resmi C. Ariyattu, François Taı̈aniHAL 2016

TL;DR

This paper introduces Filament, a novel decentralized service that helps users collaboratively editing documents find each other without relying on traditional Distributed Hash Tables (DHTs). By leveraging self-organizing overlays based on semantic similarity, Filament efficiently constructs "cohorts" of users working on the same document, improving scalability and reducing latency in decentralized collaborative editing platforms.

What Problem Does This Paper Address?

Collaborative editing tools are becoming increasingly popular, but many existing solutions struggle with scalability, especially in decentralized environments. While peer-to-peer (P2P) approaches offer a way to overcome the limitations of centralized servers, they often assume that all users are working on the same set of documents. In reality, especially with a large user base, users editing the same document need an efficient way to discover each other. Traditional P2P search mechanisms like DHTs, while effective for general content addressing, introduce an unnecessary layer of indirection and are not ideally suited for scenarios where the number of documents (resources) is significantly smaller than the number of users. This paper addresses the challenge of efficiently connecting users who are interested in the same document in a decentralized setting, aiming for deterministic guarantees and avoiding the overhead of DHTs.

Methods

The core of Filament is a novel "cohort-construction" approach that utilizes self-organizing overlay networks. Instead of relying on a DHT to map documents to users, Filament builds overlays where nodes (users) organize themselves based on the similarity of the documents they are editing.

Here's a breakdown of the key techniques:

  • Self-Organizing Overlays: Filament composes multiple self-organizing overlay networks. These overlays connect nodes based on a similarity function, ensuring that each node is connected to its "closest" neighbors in terms of document interests.
  • Helper Overlay (n.H): Each node maintains a helper overlay initially populated with random peers. Over time, this overlay is filled with nodes that have similar, but not identical, document interests. This helps in discovering potential collaborators.
  • Document Views (n.view(dp)): Each node maintains a specific view for each document it's editing. The goal is to fill these views with collaborators as quickly as possible to facilitate rapid edit propagation.
  • Fingers (n.F): Similar to DHTs like Chord, Filament uses a finger list for long-distance routing. These links are crucial for efficiently locating collaborators for newly added documents or finding users working on similar documents.
  • Similarity Metric: A novel similarity metric is used, based on document IDs. It's designed to remove identical nodes and considers nodes with closer document IDs as more similar.

The algorithm operates in rounds, where nodes exchange their views with their helper overlay neighbors and a random system node. They then update their document views and helper overlays based on this information, aiming to fill their document views with a target number of collaborators.

Datasets

Not discussed in the paper. The evaluation uses a simulation environment (Peersim) with synthetic data.

Key Insights and Ideas

  • Semantic Similarity for Overlay Construction: The most significant insight is the use of semantic similarity (based on document IDs) to organize overlay networks. This allows for more direct and efficient discovery of collaborators compared to generic DHTs.
  • Avoiding DHT Indirection: By directly linking users based on document interests, Filament bypasses the extra hop and complexity often associated with DHTs, leading to potentially lower latency.
  • Deterministic Guarantees without DHTs: Filament aims to provide deterministic guarantees for finding collaborators, a feature often lacking in unstructured P2P approaches, while avoiding the structural complexity of DHTs.
  • Scalability through Decentralization: The self-organizing nature of the overlays and the decentralized approach inherently support scalability for large numbers of users.
  • Load Balancing: The approach naturally provides load-balancing properties by distributing the task of finding collaborators across the network.

Key Results

The paper presents preliminary evaluation results based on simulations using Peersim.

  • Convergence Time: The system takes approximately 11 rounds to converge, meaning document views are sufficiently filled.
  • New Document Discovery: When a new document is added to a node after system convergence, the node can find the required number of collaborators (l=10) for that document in about 4.1 rounds.
  • Filament vs. DHT Latency: Figure 8 shows that Filament generally exhibits lower document latency compared to a DHT-based approach, especially as the network size increases. For a network size of 2^12, Filament's latency is around 3-4 rounds, while a DHT's latency is around 6-7 rounds.

Limitations and Future Work

  • Preliminary Evaluation: The authors acknowledge that the evaluation is preliminary and based on simulations. Real-world deployment and testing are needed.
  • Similarity Metric Nuances: While the document ID similarity is novel, its effectiveness in diverse collaborative editing scenarios might require further exploration.
  • Churn Handling: The paper mentions that nodes may join or leave at any time, but the detailed mechanisms for handling significant churn and maintaining overlay stability are not deeply explored in this initial work.
  • Future Work: The authors suggest further research into more sophisticated similarity metrics, exploring the impact of different overlay configurations, and investigating the system's behavior under higher churn rates. They also aim to explore how this cohort-construction service can be integrated into actual collaborative editing platforms.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{ariyattu2016filament,
  author = {Resmi C. Ariyattu and François Taı̈ani},
  title = {{Filament : a cohort construction service for decentralized collaborative editing platforms}},
  booktitle = {HAL},
  year = {2016},
}
Figure