Fundamenta Informaticae - Volume 173, issue 1

Authors: Kashiwabara, Kenji | Horie, Ikumi | Yamaguchi, Kazunori

Article Type: Research Article

Abstract: We introduce a new higher-order rank function with the capability to completely discriminate non-equivalent nodes. We review the partition lattice and rank functions and situate the existing rank functions and higher-order rank functions within the formalization. We propose a new refining operator and a new rank function that are better than the existing ones in some applications. We also show that the entire topology (graph) can be reconstructed from only our higher-order ranks making it possible to compare nodes in different graphs and to update the equivalence of nodes when an edge is added. Finally, we briefly describe the use …of our higher-order rank function in analyzing web pages as a possible application in different domains. Show more

DOI: 10.3233/FI-2020-1913

Citation: Fundamenta Informaticae, vol. 173, no. 1, pp. 1-31, 2020

Authors: Lin, Cheng-Kuan | Ma, Liang | Fan, Jianxi | Hsu, Lih-Hsing | Teng, Yuan-Hsiang

Article Type: Research Article

Abstract: We propose two new measures of conditional connectivity to be the extension of Rg -connectivity and Rg -edge-connectivity. Let G be a connected graph. A set of vertices (edges) F is said to be a conditional (g , d , k )(-edge)-cut of G if (1) G – F is disconnected; (2) every vertex in G – F has at least g neighbors; (3) degG–F (p ) + degG–F (q ) ≥ 2g + k for every two distinct vertices p and q in …G – F with d (p , q ) ≤ d . The (g , d , k )-conditional(-edge)-connectivity, denoted by κg,d,k (λg,d,k ), is the minimum cardinality of a conditional (g , d , k )(-edge)-cut. Based on these requirements, we obtain κ 1,1,k , κ 1,d ,2 , λ 1,1,1 and λ 1,d ,2 for the hypercubes. Show more

Keywords: conditional connectivity, hypercube

DOI: 10.3233/FI-2020-1914

Citation: Fundamenta Informaticae, vol. 173, no. 1, pp. 33-45, 2020

Authors: Macyna, Wojciech | Kukowski, Michal

Article Type: Research Article

Abstract: Solid state disks become the very popular storage devices. Nonetheless, their architecture based on flash memory has some limitations. They suffer from poor random write performance, as the flash memory blocks must be erased before write. Nowadays, among many database models, the column-oriented databases have attracted the attention. In this model, the data from the particular columns of the database table are stored separately in the memory blocks. As a consequence, only such columns are derived from the memory which are necessary for query execution. In this way, I/O number is reduced, what drastically increases the database performance. This paper …proposes a new storage method for the column oriented databases on solid state disks. In this method, the data from each column is stored as a separated structure, called Column-Flash tree (CF-tree). The table is always sorted by a particular column (or a set of columns). Due to utilizing fractional cascading and tree-like structure, the efficiency of update and search is obtained. The storage may be adjusted to the altering query pattern and disk characteristics by changing the height of the CF-tree and the capacity of its levels. In contrast to the other models, the approach may be applied to both read and write optimized databases. Show more

Keywords: Solid state disk, data storage, column oriented database

DOI: 10.3233/FI-2020-1915

Citation: Fundamenta Informaticae, vol. 173, no. 1, pp. 47-72, 2020

Authors: Tioura, Abdelhamid | Moumen, Hamouma | Kalla, Hamoudi | Ait Saidi, Ahmed

Article Type: Research Article

Abstract: The consensus is a central problem of fault-tolerant distributed computing. Unfortunately, solving such a problem is impossible in asynchronous distributed systems prone to process failures. To circumvent this impossibility (known as FLP impossibility result) in a deterministic way, on top of asynchronous distributed systems enriched with additional assumptions, several protocols have been proposed. Actually, to solve the Byzantine Consensus problem, with a deterministic manner, in systems where at most t processes may exhibit a Byzantine behavior, two approaches have been investigated. The first relies on the addition of synchrony, called Timer-Based, while the second, called Time-Free, is based on …the pattern of message exchange. This paper shows that both types of assumptions are not antagonist and can be combined to solve authenticated Byzantine consensus. The combined assumption considers a correct process pi , called ⋄〈t + 1〉-BW, and a set X of t +1 correct processes (including pi itself) such that, eventually, for each query broadcasted by a correct process pj of X , pj receives a response from pi ∈ X among the (n – t ) first responses to that query or both links connecting pi and pj are timely. Based on this combination, a simple hybrid authenticated Byzantine consensus protocol benefiting from the best of both worlds is proposed. As a matter of fact, although numerous hybrid protocols have been designed for the consensus problem in the crash model, this is, to our knowledge, the first hybrid deterministic solution to the Byzantine consensus problem. Show more

Keywords: Asynchronous distributed systems, Byzantine process, Consensus, Distributed algorithms, Hybrid protocol, Time-free assumption, Timer-based assumption, Fault tolerance

DOI: 10.3233/FI-2020-1916

Citation: Fundamenta Informaticae, vol. 173, no. 1, pp. 73-89, 2020