Search

Distributed file systems have become an essential service for sharing data among users. An important aspect of a file system is its ability to keep its contents secure from unauthorized access. To investigate the interplay of security and consistency in distributed file systems, we formalize the three properties related to data security, namely confidentiality, integrity and accessibility. Based on these properties, we provide an impossibility result that indicates that these properties cannot be achieved together in a highly-available partition-tolerant setting. We further discuss a CRDT-based model, implementing the traditional POSIX access control policy, that guarantees confidentiality and integrity while precluding accessibility only in rare situations. Our conclusion is that the POSIX policies are not suitable in a distributed system setting, but that a more fine-grained model is required to obtain the security semantics that reflect the users' intention.

The tree is an essential data structure in many applications. In a distributed application, such as a distributed file system, the tree is replicated.To improve performance and availability, different clients should be able to update their replicas concurrently and without coordination. Such concurrent updates converge if the effects commute, but nonetheless, concurrent moves can lead to incorrect states and even data loss. Such a severe issue cannot be ignored; ultimately, only one of the conflicting moves may be allowed to take effect. However, as it is rare, a solution should be lightweight. Previous approaches would require preventative cross-replica coordination, or totally order move operations after-the-fact, requiring roll-back and compensation operations. In this paper, we present a novel replicated tree that supports coordination-free concurrent atomic moves, and provably maintains the tree invariant. Our analysis identifies cases where concurrent moves are inherently safe, and we devise a lightweight, coordination-free, rollback-free algorithm for the remaining cases, such that a maximal safe subset of moves takes effect. We present a detailed analysis of the concurrency issues with trees, justifying our replicated tree data structure. We provide mechanized proof that the data structure is convergent and maintains the tree invariant. Finally, we compare the response time and availability of our design against the literature.; L’arbre est une structure de données essentielle. Quand l’application est distribuée, par exemple dans un système de fichiers distribué, l’arbre est répliqué. Pour améliorer les performances et la disponibilité, les différents clients doivent pouvoir mettre à jour leurs répliques simultanément et sans coordination. Celles-ci convergent si les mises à jour commutent entre elles ; néanmoins, même dans ce cas, des opérations “move” concurrentes peuvent conduire à des états incorrects, et même à la perte de données. Au bout du compte, entre deux opérations “move” en conflit, seule l’une des deux peut être autorisée à prendre effet. Cependant, comme ce cas est rare, la solution doit être légère. Les approches précédentes nécessitaient une coordination préventive des répliques, ou des retours en arrière a posteriori. Dans cet article, nous présentons un nouvel arbre répliqué, qui met en œuvre une opération “move” atomique sans coordination, et dont nous prouvons qu’il maintient l’invariant d’arbre.Notre analyse identifie les cas où les “move” concurrents sont intrinsèquement sûrs, et proposons un algorithme léger, sans coordination et sans retour-arrière, pour les autres cas, de sorte qu’un sous-ensemble maximal et sûr de “move” prenne effet. Nous présentons une analyse détaillée des problèmes de cohérence dans les arbres. Nous fournissons une preuve mécanisée que la structure des données est convergente et maintientl’invariant d’arbre. Enfin, nous comparons le temps de réponse et la disponibilité de notre concept à la littérature.

The tree is an essential data structure in many applications. In a distributed application, such as a distributed file system, the tree is replicated.To improve performance and availability, different clients should be able to update their replicas concurrently and without coordination. Such concurrent updates converge if the effects commute, but nonetheless, concurrent moves can lead to incorrect states and even data loss. Such a severe issue cannot be ignored; ultimately, only one of the conflicting moves may be allowed to take effect. However, as it is rare, a solution should be lightweight. Previous approaches would require preventative cross-replica coordination, or totally order move operations after-the-fact, requiring roll-back and compensation operations. In this paper, we present a novel replicated tree that supports coordination-free concurrent atomic moves, and provably maintains the tree invariant. Our analysis identifies cases where concurrent moves are inherently safe, and we devise a lightweight, coordination-free, rollback-free algorithm for the remaining cases, such that a maximal safe subset of moves takes effect. We present a detailed analysis of the concurrency issues with trees, justifying our replicated tree data structure. We provide mechanized proof that the data structure is convergent and maintains the tree invariant. Finally, we compare the response time and availability of our design against the literature.; L’arbre est une structure de données essentielle. Quand l’application est distribuée, par exemple dans un système de fichiers distribué, l’arbre est répliqué. Pour améliorer les performances et la disponibilité, les différents clients doivent pouvoir mettre à jour leurs répliques simultanément et sans coordination. Celles-ci convergent si les mises à jour commutent entre elles ; néanmoins, même dans ce cas, des opérations “move” concurrentes peuvent conduire à des états incorrects, et même à la perte de données. Au bout du compte, entre deux opérations “move” en conflit, seule l’une des deux peut être autorisée à prendre effet. Cependant, comme ce cas est rare, la solution doit être légère. Les approches précédentes nécessitaient une coordination préventive des répliques, ou des retours en arrière a posteriori. Dans cet article, nous présentons un nouvel arbre répliqué, qui met en œuvre une opération “move” atomique sans coordination, et dont nous prouvons qu’il maintient l’invariant d’arbre.Notre analyse identifie les cas où les “move” concurrents sont intrinsèquement sûrs, et proposons un algorithme léger, sans coordination et sans retour-arrière, pour les autres cas, de sorte qu’un sous-ensemble maximal et sûr de “move” prenne effet. Nous présentons une analyse détaillée des problèmes de cohérence dans les arbres. Nous fournissons une preuve mécanisée que la structure des données est convergente et maintientl’invariant d’arbre. Enfin, nous comparons le temps de réponse et la disponibilité de notre concept à la littérature.

International audience; This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message , no process delivers first a set of messages including and later a set of message including m.After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the “power” side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data types), and distributed tasks. On the “computability limits” side it shows that SCD-broadcast and read/write registers are computationally equivalent.

Wenn man an die heutige Speichermenge, die benötigte Dateipersistenz, die hohe Verfügbarkeit und die größeren Dateigrößen denkt, war ein Speichersystem immer der zentrale Fehler, aber auch ein notwendiger Faktor für die meisten aktuellen End- und/oder Power-User. In Anbetracht des ungenutzten Speicherplatzes auf den Clients/Arbeitsplätzen der Endanwender, vor allem in großen Unternehmen, gibt es einigen oder im besten Fall sehr viel freien Speicherplatz, der für einen anderen Zweck wie eine kombinierte Dateiablage genutzt werden könnte. Ein Ort, an dem Daten sicher, ausfallsicher, redundant und immer zugänglich gespeichert werden können. Unter diesem Gesichtspunkt ist IPFS (InterPlanetary File System), ein Peer-to-Peer-Hypermedia-Protokoll, das eine sichere inhaltsbasierte Adressierung und Funktionalität zur Speicherung und Verteilung von Daten in einem dezentralen verteilten Datensystem bietet, sehr gut geeignet, um oben genannte Speicherplätze zu kombinieren. Außerdem spart IPFS durch seine Deduplizierung von Dateien Bandbreite und wird in dieser Arbeit als grundlegendes Dateisystem für eine dezentrale Speichersystemlösung für Mehrbenutzerzwecke verwendet. Darüber hinaus bietet IPFS auch eine Versionskontrolle für Dateien. Doch die genannten Vorteile der Deduplizierung gehen leider mit einigen Nachteilen einher, wenn man IPFS in einem Mehrbenutzersystem einsetzt. Diese Arbeit konzentriert sich speziell auf die Probleme, die in einem deduplizierten Dateisystem auftreten, das für den Mehrbenutzerbetrieb und die Dateispeicherung verwendet wird. IPFS behält die Anzahl der Dateien nicht im Auge und speichert Dateien nur einmal, wenn sie den Deduplizierungsregeln entsprechen. Dies ist ein Problem, wenn dieselbe Datei von zwei einzelnen Benutzern auf demselben System gespeichert wird. Daher wird in diesem Beitrag eine Lösung für das genannte Problem vorgestellt, indem eine zusätzliche Logikschicht eingeführt wird, die die gespeicherten Dateien, ihre Anzahl und die Benutzerrechte für die gespeicherten Dateien in einem privaten dezentralen Dateispeichersystem verfolgt. Diese Schicht wird durch eine Kombination von zusätzlichen Suiten und Protokollen realisiert. Dazu gehören IPFS als Dateisystem, IPFS-Cluster für die Verteilung und Propagierung von Inhalten im System und MongoDB als Datenbank, um Dateiberechtigungen und Dateizahlen auf gespeicherte Dateien abzubilden. Es bildet IPFS-Hashes von gespeicherten Dateien in der Datenbank ab, mit zusätzlichen Berechtigungen und Dateizahlen dieser. Die Ergebnisse dieses Papiers liefern zusätzliches Diskussionsmaterial über Verbesserungen des genannten Systems, indem die eingeführte Schicht zu einer vollständig dezentralen Lösung geändert wird, indem Berechtigungsinformationen von Dateien in einer Blockchain gespeichert werden. Thinking about today’s file sizes storage amount, needed file persistence, high availability and bigger file sizes, a storage system was always the central failure but also a needed factor for most of current end and/or power users. Considering the unused storage space on end user clients/workstations especially in big companies, there is some or in the best-case plenty free space that could be allocated and used for some other purpose like a combined file storage. A place where data can be stored securely, fail safe, redundant and always accessible. This taken into account IPFS (InterPlanetary File System), a peer-to-peer hypermedia protocol that offers secure content based addressing and functionality for saving and distributing data in a decentralized distributed data-system is very well suited for combining above mentioned storage spaces. Furthermore IPFS saves bandwidth through it's deduplication of files and is used in this paper as fundamental filesystem for a decentralized storage system solution for multi-user purposes. In addition IPFS also provides version control for files. But mentioned advantages of deduplication unfortunately come with some disadvantages when using IPFS in a multi-user system. This work focuses especially on the problem that arise in a deduplicated filesystem that is used for multi-user operation and file storage. IPFS does not keep track of file counts and stores files just once if they fit the deduplication rules. This is a problem when the same file is stored by two individual users on sad system. Therefore this paper presents a solution for mentioned problem by introducing an additional logic layer that keeps track of saved file, their count and user permissions on those saved in a private decentralized file storage system. This layer is realized through a combination of additional suites and protocols. That include IPFS as filesystem, IPFS cluster for the distribution and propagation of content across the system and mongoDB as database to map file permissions and file counts to saved files. It maps IPFS hashes of saved files into the database with additional permission and file counts of those. Findings of this paper provide additional discussion material about improvements of mentioned system by changing the introduced layer to a completely decentralized solution by saving permission informations of files to a blockchain.

This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ' , no process delivers first a set of messages including m ' and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent., Comment: arXiv admin note: substantial text overlap with arXiv:1702.08176