Fundamenta Informaticae - Volume 109, issue 4

Authors: Ésik, Zoltán | Sutner, Klaus

Article Type: Research Article

DOI: 10.3233/FI-2011-517

Citation: Fundamenta Informaticae, vol. 109, no. 4, pp. 369-381, 2011

Authors: Locher, Thomas | Schmid, Stefan | Wattenhofer, Roger

Article Type: Research Article

Abstract: This article reports on the results of our measurement study of the Kad network. Although several fully decentralized peer-to-peer systems have been proposed in the literature, most existing systems still employ a centralized architecture. The Kad network is a notable exception. Since the demise of the Overnet network, the Kad network has become the most popular peer-to-peer system based on a distributed hash table. It is likely that its user base will continue to grow in numbers over the next few years due to the system's scalability and reliability. The contribution of the article is twofold. First, we compare the …two networks accessed by eMule: the centralized paradigmof the eDonkey network and the structured, distributed approach pursued by the Kad network. We re-engineer the eDonkey server software and integrate two modified servers into the eDonkey network in order to monitor traffic. Additionally, we implement a Kad client exploiting a design weakness to spy on the traffic at arbitrary locations in the ID space. The collected data provides insights into the spacial and temporal distributions of the peers' activity. Moreover, it allows us to study the searched content. The article also discusses problems related to the collection of such data sets and investigates techniques to verify the representativeness of the measured data. Second, this article shows that today's Kad network can be attacked in several ways. Our simple attacks could be used either to hamper the correct functioning of the network itself, to censor content, or to harm other entities in the Internet not participating in the Kad network, such as ordinary web servers. While there are heuristics to improve the robustness of Kad, we believe that the attacks cannot be thwarted easily in a fully decentralized peer-to-peer system, i.e., without some kind of a centralized certification and verification authority. This result may be relevant in the context of the current debate on the design of a clean-slate network architecture for the Internet which is based on concepts known from the peer-to-peer paradigm. Show more

Keywords: Peer-to-Peer, Robustness, Measurements, Distributed Systems, eMule, Kademlia, Future Internet Architecture

DOI: 10.3233/FI-2011-518

Citation: Fundamenta Informaticae, vol. 109, no. 4, pp. 383-403, 2011

Authors: Piao, Xiaoxue | Salomaa, Kai

Article Type: Research Article

Abstract: We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT'05, LNCS 3623, pp. 68–79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata.

Keywords: tree automata, unranked trees, state complexity, nondeterminism

DOI: 10.3233/FI-2011-519

Citation: Fundamenta Informaticae, vol. 109, no. 4, pp. 405-424, 2011

Authors: Simson, Daniel

Article Type: Research Article

Abstract: We study integral solutions of diophantine equations q(x) = d, where x = (x1 , . . . , xn ), n ≥ 1, d ∈ \mathbb{Z} is an integer and q : \mathbb{Z}n → \mathbb{Z} is a non-negative homogeneous quadratic form. Contrary to the negative solution of the Hilbert's tenth problem, for any such a form q(x), we give efficient algorithms describing the set ℛq (d) of all integral solutions of the equation q(x) = d in a ΦA -mesh translation quiver form. We show in Section 5 that usually the set ℛq (d) has a shape of …a ΦA -mesh sand-glass tube or of a ΦA -mesh torus, see 5.8, 5.10, and 5.13. If, in addition, the subgroup Ker q = {v ∈ \mathbb{Z}n ; q(v) = 0} of \mathbb{Z}n is infinite cyclic, we study the solutions of the equations q(x) = 1 by applying a defect δA : \mathbb{Z}n → \mathbb{Z} and a reduced Coxeter number čA ∈ \mathbb{N} defined by means of a morsification bA : \mathbb{Z}n × \mathbb{Z}n → \mathbb{Z} of q, see Section 4. On this way we get a simple graphical algorithm that constructs all integral solutions in the shape of a mesh translation oriented graph consisting of Coxeter ΦA -orbits. It turns out that usually the graph has at most three infinite connected components and each of them has an infinite band shape, or an infinite horizontal tube shape, or has a sand-glass tube shape. The results have important applications in representation theory of groups, algebras, quivers and partially ordered sets, as well as in the study of derived categories (in the sense of Verdier) of module categories and categories of coherent sheaves over algebraic varieties. Show more

Keywords: principal quadratic form, quiver, poset, tubular mesh algorithm, Coxeter matrix, morsification, defect, reduced Coxeter number, sand-glass tube, mesh geometry

DOI: 10.3233/FI-2011-520

Citation: Fundamenta Informaticae, vol. 109, no. 4, pp. 425-462, 2011

Authors: Zhu, Ping

Article Type: Research Article

Abstract: In Pawlak's rough set theory, a set is approximated by a pair of lower and upper approximations. To measure numerically the roughness of an approximation, Pawlak introduced a quantitative measure of roughness by using the ratio of the cardinalities of the lower and upper approximations. Although the roughness measure is effective, it has the drawback of not being strictly monotonic with respect to the standard ordering on partitions. Recently, some improvements have been made by taking into account the granularity of partitions. In this paper, we approach the roughness measure in an axiomatic way. After axiomatically defining roughness measure and …partition measure, we provide a unified construction of roughness measure, called strong Pawlak roughness measure, and then explore the properties of this measure. We show that the improved roughness measures in the literature are special instances of our strong Pawlak roughness measure and introduce three more strong Pawlak roughness measures as well. The advantage of our axiomatic approach is that some properties of a roughness measure follow immediately as soon as the measure satisfies the relevant axiomatic definition. Show more

Keywords: Accuracy measure, approximation, partition measure, roughness measure, rough set

DOI: 10.3233/FI-2011-521

Citation: Fundamenta Informaticae, vol. 109, no. 4, pp. 463-480, 2011

Article Type: Correction

DOI: 10.3233/FI-2011-522

Citation: Fundamenta Informaticae, vol. 109, no. 4, pp. 481-481, 2011