You are here

Decentralized Evaluation of Regular Expressions for Capability Discovery in Peer-to-Peer Networks

TitleDecentralized Evaluation of Regular Expressions for Capability Discovery in Peer-to-Peer Networks
Publication TypeThesis
Year of Publication2012
AuthorsSzengel, M
Refereed DesignationNon-Refereed
AdvisorGrothoff, C, Holz, R, Polot, B, Niedermayer, H
Academic DepartmentDepartment of Computer Science
Number of Pages100
Date Published11/2012
UniversityTechnische Universitaet Muenchen
CityGarching bei Muenchen
Thesis TypeMasters
KeywordsDFA, distributed hash table, GNUnet, NFA, regular expressions, search

This thesis presents a novel approach for decentralized evaluation of regular expressions for capability discovery in DHT-based overlays. The system provides support for announcing capabilities expressed as regular expressions and discovering participants offering adequate capabilities.

The idea behind our approach is to convert regular expressions into finite automatons and store the corresponding states and transitions in a DHT. We show how locally constructed DFA are merged in the DHT into an NFA without the knowledge of any NFA already present in the DHT and without the need for any central authority. Furthermore we present options of optimizing the DFA.

There exist several possible applications for this general approach of decentralized regular expression evaluation. However, in this thesis we focus on the application of discovering users that are willing to provide network access using a specified protocol to a particular destination.

We have implemented the system for our proposed approach and conducted a simulation. Moreover we present the results of an emulation of the implemented system in a cluster.

szengel2012ms.pdf1.24 MB