Publications

Pre-prints

Subgraphs in Semi-Random Graphs

Authors: Natalie C. Behague, Trent G. Marbach, Pawel Pralat, Andrzej Rucinski

https://arxiv.org/abs/2105.07034

Abstract: The semi-random graph process is a single player game in which the player is initially presented with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing an arbitrary fixed graph G. Let ω=ω(n) be any function tending to infinity as n→∞. In (Omri Ben-Eliezer et al. "Semi-random graph process". In: Random Structures & Algorithms 56.3 (2020), pp. 648-675) it was proved that asymptotically almost surely one can construct G in less than n(d−1)/dω rounds where d≥2 is the degeneracy of d. It was also proved that the result is sharp for G=Kd+1, that is, asymptotically almost surely it takes at least n(d−1)/d/ω rounds to create Kd+1. Finally, the authors of that paper conjectured that their general upper bound is sharp for all graphs G. We prove this conjecture. *** We currently work on extending the results to hypergraphs. Stay tuned. ***

An evolving network model from clique extension - Long

Authors: Anthony Bonato, Ryan Cushman, Trent Marbach, Zhiyuan Zhang

Abstract:

We consider a new model for complex networks whose underlying mechanism is extending dense subgraphs. In the frustum model, we iteratively extend cliques over discrete-time steps. For many choices of the underlying parameters, graphs generated by the model densify over time. In the special case of the cone model, generated graphs provably satisfy properties observed in real-world complex networks such as the small world property and bad spectral expansion. We finish with a set of open problems and next steps for the frustum model. 

On Meyniel Extremal Families of Graphs

Authors: Anthony Bonato, Ryan Cushman, Trent Marbach

Abstract: 

We provide new constructions of Meyniel extremal graphs, which are families of graphs with the conjectured largest asymptotic cop number.  Using spanning subgraphs, we prove that there are an exponential number of new Meyniel extremal families with specified degrees. Using linear programming on hypergraphs, we explore the degrees in families that are not Meyniel extremal. We give the best-known upper bound on the cop number of vertex-transitive graphs with a prescribed degree. We find new Meyniel extremal families of regular graphs with large chromatic number, large diameter, and explore the connection between Meyniel extremal graphs and bipartite graphs. Conjectures relating Meyniel extremal families to maximum and average degrees in their graphs are presented.

Time-delayed Cops and Robber

Authors: Nancy Clarke, Danielle Cox, Melissa Huggan, Trent Marbach

Abstract: 

We consider a variation of the Cops and Robber game in which the cops do not have perfect information; the information they receive regarding the robber's position is delayed by one round. Our parameter of interest is the time-delayed cop number of a graph $G$, the minimum number of cops that suffice to guarantee a win on $G$. We present a variety of results on this parameter, including general bounds, and make comparisons to the cop numbers of known related variants of the original game. We have particular interest in graph products, Meyniel-type bounds, and cop density.


Graph Latinity

Authors:  Fatih Demirkale, Akira Kamibeppu, Trent G. Marbach, Oktay Olmez, Rebecca J. Stones

Abstract: 

A d-dimensional partial Latin hypercuboid (d-PLH) generalizes a Latin square to an arbitrary number of dimensions of different lengths, and also allows empty cells. A d-PLH gives a d-PLH graph with edges between entries when their cells agree at all but one coordinate, or when they contain the same symbol, generalizing Latin square graphs. We introduce the Latinity of a graph G: the minimum d for which some d-PLH graph is isomorphic to G.

We deduce the Latinity of all (a) graphs on up to 6 vertices, (b) graphs formed by deleting at most 3 edges from complete graphs, (c) complete bipartite graphs, (d) forests, (e) unit interval graphs, (f) graphs with maximum degree 2, (g) line graphs of 3-colorable graphs, and (h) 3-regular graphs with chromatic index 3. The smallest graphs with infinite Latinity have 6 vertices, precisely K6 \ K4 and K6 \ K3. We find all generalized Petersen graphs have Latinity 2, except for the Petersen graph which has Latinity 4.

Locally finite graphs and their localization numbers

Authors:  Anthony Bonato, Florian Lehner, Trent G. Marbach, JD Nir

https://arxiv.org/abs/2404.02409

Abstract: 

We study the Localization game on locally finite graphs trees, where each of the countably many vertices have finite degree. In contrast to the finite case, we construct a locally finite tree with localization number n for any choice of positive integer n. Our examples have uncountably many ends, and we show that this is necessary by proving that locally finite trees with finitely or countably many ends have localization number at most 2. Finally, as is the case for finite graphs, we prove that any locally finite graph contains a subdivision where one cop can capture the robber.

2024

[38] How to Cool a Graph

Authors: Anthony Bonato, Trent Marbach, Holden Milne, Theodore Mishura

Modelling and Mining Networks (2024)

https://doi.org/10.1007/978-3-031-59205-8 

Abstract: 

We introduce a new graph parameter called the cooling number, inspired by the spread of influence in networks and its predecessor, the burning number. The cooling number measures the speed of a slow moving contagion in a graph; the lower the cooling number, the faster the contagion spreads. We provide tight bounds on the cooling number via a graph’s order and diameter. Using isoperimetric results, we derive the cooling number of Cartesian grids. The cooling number is studied in graphs generated by the Iterated Local Transitivity model for social networks. We conclude with open problems.

[37] The Frustum Network Model Based on Clique Extension

Authors: Anthony Bonato, Ryan Cushman, Trent Marbach, Zhiyuan Zhang

Journal of Combinatorial Optimization

https://link.springer.com/article/10.1007/s10878-024-01178-y

Abstract: 

The frustum model simulates network evolution by extending cliques, which represent highly interacting groups in social networks. In each time-step, new vertices are added adjacent to existing cliques of prescribed order. The model exhibits several features of social networks, such as densification, short distances, bad spectral expansion, and high local clustering 

2023

[36] The One-visibility Localization Game

Authors: Anthony Bonato, Trent Marbach, Michael Molnar, JD Nir

Theoretical Computer Science

https://doi.org/10.1016/j.tcs.2023.114186

Abstract: 

We introduce a variant of the Localization game in which the cops only have visibility one, along with the corresponding optimization parameter, the one-visibility localization number $\zeta_1$. By developing lower bounds using isoperimetric inequalities, we give upper and lower bounds for $\zeta_1$ on $k$-ary trees with $k\ge 2$ that differ by a multiplicative constant, showing that the parameter is unbounded on $k$-ary trees. We provide a $O(\sqrt{n})$ bound for $K_h$-minor free graphs of order $n$, and we show Cartesian grids meet this bound by determining their one-visibility localization number up to four values. We present upper bounds on $\zeta_1$ using pathwidth and the domination number and give upper bounds on trees via their depth and order. We conclude with open problems. 

[35] Meta Pseudo Labels for Anomaly Detection via Partially Observed Anomalies - LONG

Authors: Sinong Zhao, Zhaoyang Yu, Xiaofei Wang, Trent Marbach, Gang Wang, Xiaoguang Liu

Engineering Applications of Artificial Intelligence

https://doi.org/10.1016/j.engappai.2023.106955

Abstract: 

General anomaly detection has been an important research due to its broad and significant applications. Those algorithms that are based on weakly supervised or partially observed anomalies have attracted particular interest currently. However, most such algorithms treat the unlabeled set as a substitute for normal samples and ignore the potential anomalies in it, which on the one hand causes the noise of the normal set, and on the other hand, fails make full use of the abnormal supervision information. To address this issue, we propose a meta-pseudo-label based framework for anomaly detection (MPAD). The framework strives to obtain effective pseudo anomalies from the unlabeled samples to supplement the observed anomaly set. Specifically, a teacher network is improved based on the feedback of a student network on a validation set, thereby generating more conducive pseudo anomalies to assist the student network while incurring less confirmation bias. In addition, we also design a model roll-back scheme to guarantee the performance of the student network. Extensive experiments show that the proposed MPAD algorithm outperforms current popular algorithms on five real datasets, and the framework can effectively improve the utilization of unlabeled samples while maintaining an advanced degree of robustness. In addition, the results of ablation experiments confirm the effectiveness of each module of our MPAD. Parameter experiments provide sufficient reference for parameter selecting.

[34] The Localization Game on Directed Graphs

Authors: Anthony Bonato, Ryan Cushman, Trent Marbach, Brittany Pittman

Discrete Applied Mathematics

https://www.sciencedirect.com/science/article/abs/pii/S0166218X23002251

Abstract: 

In the Localization game played on graphs, a set of cops uses distance probes to identify the location of an invisible robber. We present an extension of the game and its main parameter, the localization number, to oriented graphs. We present several bounds on the localization number of an oriented graph, including a tight bound via strong components, a bound using a linear programming problem on hypergraphs, and bounds in terms of DAG-width. A family of oriented graphs of order 𝑛 is given with localization number (1−𝑜(1))𝑛/2. We investigate the localization number of random and quasi-random tournaments, including Paley tournaments. 

[33] The Iterated Local Transitivity Model for Hypergraphs

Authors: Natalie Behague, Anthony Bonato, Melissa Huggan, Rehan Malik, Trent Marbach

https://doi.org/10.1016/j.dam.2023.04.006

Abstract: 

Complex networks are pervasive in the real world, capturing dyadic interactions between pairs of vertices, and a large corpus has emerged on their mining and modeling. However, many phenomena are comprised of polyadic interactions between more than two vertices. Such complex hypergraphs range from emails among groups of individuals, scholarly collaboration, or joint interactions of proteins in living cells. Complex hypergraphs and their models form an emergent topic, requiring new models and techniques.


A key generative principle within social and other complex networks is transitivity, where friends of friends are more likely friends. The previously proposed Iterated Local Transitivity (ILT) model incorporated transitivity as an evolutionary mechanism. The ILT model provably satisfies many observed properties of social networks, such as densification, low average distances, and high clustering coefficients.


We propose a new, generative model for complex hypergraphs based on transitivity, called the Iterated Local Transitivity Hypergraph (or ILTH) model. In ILTH, we iteratively apply the principle of transitivity to form new hypergraphs. The resulting model generates hypergraphs simulating properties observed in real-world complex hypergraphs, such as densification and low average distances. We consider properties unique to hypergraphs not captured by their 2-section. We show that certain motifs, which are specified subhypergraphs of small order, have faster growth rates in ILTH hypergraphs than in random hypergraphs with the same order and expected average degree. We show that the graphs admitting a homomorphism into the 2-section of the initial hypergraph appear as induced subgraphs in the 2-section of ILTH hypergraphs. We consider new and existing hypergraph clustering coefficients, and show that these coefficients have larger values in ILTH hypergraphs than in comparable random hypergraphs.

[32] MDGAD: Meta domain generalization for distribution drift in anomaly detection

Authors: Sinong Zha, Zhaoyang Yu, Trent G. Marbach, Gang Wang, Airu Yin, Yatao Zhou, and Xiaoguang Liu

Neurocomputing

https://doi.org/10.1016/j.neucom.2023.126483

Abstract: 

Anomalies often experience distribution drift over time in anomaly detection. Traditional anomaly detection methods detect anomalies with the same distribution effectively, but it is difficult to detect anomalies with changing distributions. In this paper, we propose a meta domain generalization based anomaly detection (MDGAD) framework to detect anomalies when distribution drifts. The framework first divides the data into a series of subsets. We measure the domain shift between sets with a class-sensitive distance metric, and merge similar sets, thereby generating different source domains to enhance domain diversity. We utilize the distribution shifts that existed on these source domains to simulate the distribution shifts that would be encountered when the model was applied. Meta learning is employed during training. First, the network is updated once on the meta-training set, and then another update is performed on the meta-verification set. These two gradients together determine the update direction of the network. At the same time, our framework will complete the domain alignment task on multiple source domains to extract domain invariant features and enhance the generalization of feature learning. We use Devnet as the base model and test our framework on 5 simulated data sets. The results confirm that our MDGAD outperforms current popular algorithms in detecting unknown anomalies and has better robustness. In addition, we also test our framework on real financial datasets to demonstrate the effectiveness.

[31] The Localization Game on Locally Finite Trees (short)

Authors: Anthony Bonato, Florien Thomas, Trent Marbach, JD Nir

Eurocomb'23

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-021

Abstract: 

We study the Localization game on locally finite graphs and trees, where each vertex has finite degree. As in finite graphs, we prove that any locally finite graph contains a subdivision where one cop can capture the robber. In contrast to the finite case, for n a positive integer, we construct a locally finite tree with localization number n for any choice of n. Such trees contain uncountably many ends, and we show this is necessary by proving that graphs with countably many ends have localization number at most 2. We finish with questions on characterizing the localization number of locally finite trees.

[30] The Localization Number and Metric Dimension of Graphs of Diameter 2

Authors: Anthony Bonato, Melissa Huggan, Trent Marbach

https://doi.org/10.11575/cdm.v18i1

Abstract:

We consider the localization number and metric dimension of certain graphs of diameter 2, focusing on families of Kneser graphs and graphs without 4-cycles. For the Kneser graphs with diameter 2, we find upper and lower bounds for the localization number and metric dimension, and in many cases these parameters differ only by an additive constant. Our results on the metric dimension of Kneser graphs improve on earlier ones, yielding exact values in infinitely many cases. We determine bounds on the localization number and metric dimension of Moore graphs of diameter 2 and polarity graphs. 

[29] Meta Pseudo Labels for Anomaly Detection via Partially Observed Anomalies

Authors: Sinong Zhao, Zhaoyang Yu, Xiaofei Wang, Trent Marbach, Gang Wang, Xiaoguang Liu

https://doi.org/10.1007/978-3-031-30678-5_8

Abstract:

General anomaly detection based on weakly supervised or partially observed anomalies has been an important research. However, most such algorithms treat the unlabeled set as a substitute for normal samples and ignore the potential anomalies in it, which fails make full use of the abnormal supervision information. To address this issue, we propose a Meta-Pseudo-label based framework for Anomaly Detection (MPAD). The framework strives to obtain effective pseudo anomalies from the unlabeled samples to supplement the observed anomaly set. Specifically, a teacher network is improved based on the feedback of a student network on a validation set, thereby generating more conducive pseudo anomalies to assist the student network while incurring less confirmation bias. Extensive experiments show that the proposed MPAD algorithm outperforms current popular algorithms on five real datasets.

[28] Pursuit-Evasion Games on Latin Square Graphs

Authors: Shreya Ahirwar, Anthony Bonato, Leanna Gittins, Alice Huang, Trent Marbach, Tomer Zaidman

 https://dx.doi.org/10.4310/JOC.2023.v14.n4.a4

Abstract:

We investigate various pursuit-evasion parameters on Latin square graphs, including the cop number, metric dimension, and localization number. Bounds for the cop number are given for Latin square graphs and for similarly defined graphs corresponding to k mutually orthogonal Latin squares of order n. If n > (k+1)^2, then the cop number is shown to be k+2. Lower and upper bounds are provided for the metric dimension and localization number of Latin square graphs. An analysis of the metric dimension of back-circulant Latin squares shows that the lower bound is close to tight.


[27] MSDN - A Multi-Subspace Deviation Net for Anomaly Detection

Authors: Sinong Zhao, Zhaoyang Yu, Trent Marbach, Gang Wang, Xiaoguang Liu

https://doi.org/10.1109/ICDM54844.2022.00178

Abstract:

General anomaly detection techniques have always received a lot of attention. Current detection methods usually focus solely on representation learning or anomaly judgment. This paper proposes a Multi-Subspace Deviation Network (MSDN) framework to build a model combining feature learning with anomaly score learning under the condition that a small number of labeled anomalies can be observed. Concretely, our framework combines a feature learner with two specific projectors: a self-supervised projector and an anomaly score learner. We utilize random affine transformations to map the raw data to multiple subspaces and train a classifier to predict the transformation label in the self-supervised module. Anomaly scores are then obtained directly from a deviation network, where the contrastive loss is used to amplify the gap in the anomaly scores between normal objects and anomalies. Extensive experiments on eight datasets show that our proposed method achieves higher detection accuracy than previous schemes with fewer observed anomalies. 

2022

[26] An evolving network model from clique extension - Short

Authors: Anthony Bonato, Ryan Cushman, Trent Marbach, Zhiyuan Zhang

https://doi.org/10.1007/978-3-031-22105-7_38

Abstract:

We consider a new model for complex networks whose underlying mechanism is extending dense subgraphs. In the frustum model, we iteratively extend cliques over discrete-time steps. For many choices of the underlying parameters, graphs generated by the model densify over time. In the special case of the cone model, generated graphs provably satisfy properties observed in real-world complex networks such as the small world property and bad spectral expansion. We finish with a set of open problems and next steps for the frustum model. 

[25] Tic-Tac-Toe on an Affine Plane of order 4

Authors: P. Danziger, M. Huggan, R. Malk, T. Marbach

Australasia Journal of Combinatorics (accepted)

https://ajc.maths.uq.edu.au/pdf/82/ajc_v82_p021.pdf

Abstract:

The game of tic-tac-toe is well known. In particular, in its classic version it is famous for being unwinnable by either player. While classically it is played on a grid, it is natural to consider the effect of playing the game on richer structures, such as finite planes. Playing the game of tic-tac-toe on finite affine and projective planes has been studied previously. While the second player can usually force a draw, for small orders it is possible for the first player to win. In this regard, a computer proof that tic-tac-toe played on the affine plane of order 4 is a first player win has been claimed. In this note we use techniques from the theory of latin squares and transversal designs to give a human verifiable, explicit proof of this fact.

[24] The Localization Capture Time of a Graph

Authors: Natalie C. Behague, Anthony Bonato, Melissa A. Huggan, Trent G. Marbach, Brittany Pittman

https://arxiv.org/abs/2105.09806

Abstract: The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and capture time using treewidth.

[23] Tight Bounds on the Probabilistic Zero Forcing on Hypercubes and Grids

Authors: Natalie C. Behague, Trent Marbach, Pawel Pralat

https://www.combinatorics.org/ojs/index.php/eljc/article/view/v29i1p3 

Abstract: Zero forcing is a deterministic iterative graph colouring process in which vertices are coloured either blue or white, and in every round, any blue vertices that have a single white neighbour force these white vertices to become blue. Here we study probabilistic zero forcing, where blue vertices have a non-zero probability of forcing each white neighbour to become blue. We explore the propagation time for probabilistic zero forcing on hypercubes and grids. 



2021

[22] The Localization Number of Designs 

Authors: Anthony Bonato, Melissa A. Huggan, Trent Marbach

Journal of Combinatorial Designs 

https://onlinelibrary.wiley.com/doi/abs/10.1002/jcd.21762

See also: https://arxiv.org/pdf/2005.12780.pdf

Abstract: We study the localization number of incidence graphs of designs. In the localization game played on a graph, the cops attempt to determine the location of an invisible robber via distance probes. The localization number of a graph G, written ζ(G), is the minimum number of cops needed to ensure the robber's capture. We present bounds on the localization number of incidence graphs of balanced incomplete block designs. Exact values of the localization number are given for the incidence graphs of projective and affine planes. Bounds are given for Steiner systems and for transversal designs.


[21] Improving Load Balancing for Modern Data Centers through Resource Equivalence Classes

Authors:  K. Duan, Y. Li, T. Marbach, G. Wang, X. Liu.

ICSOC 2021 (accepted)

Abstact: Load balancing is one of the most significant concerns for data center (DC) management, and the basic method is reassigning tasks from overloaded servers to underloaded servers. However, to ensure the service availability, during the reassignment of a task, some resources (i.e., transient resources) are consumed simultaneously on its initial server and its target server, which imposes a challenge for load balancing. The latest research has proposed a concept called resource equivalence class (REC: a set of resource configurations such that an latency-critical (LC) application running with any one of them can meet the QoS target). In this paper, we use the REC to improve the load balancing for a data center, where multiple LC applications have already co-located on servers with the service availability and QoS guarantees. We formulate the load balancing problem as multi-objective constrained programming (MOCP) model. To solve the proposed problem, we first propose a machine learning-based prediction model to construct the RECs for applications. Then, we develop a local search (LS) algorithm to approximate the optimal solution iteratively. We evaluate the proposed algorithm via simulated experiments, and the results show that LS outperforms the state-of-the-art baseline significantly. To the best of our knowledge, it is the first time to use REC for improving load balancing in DCs. 

[20] The Game of Cops and Eternal Robbers

Authors: A. Bonato, M. Huggan, T. Marbach, F. Mc Inerney

Theoretical Computer Science, Volume 874

https://www.sciencedirect.com/science/article/abs/pii/S0304397521002681

[2003.03791] The Game of Cops and Eternal Robbers (arxiv.org) 

Abstract:

We introduce the game of Cops and Eternal Robbers played on graphs, where there are infinitely many robbers that appear sequentially over distinct plays of the game. A positive integer t is fixed, and the cops are required to capture the robber in at most t time-steps in each play. The associated optimization parameter is the eternal cop number, denoted by , which equals the eternal domination number in the case , and the cop number for sufficiently large t. We study the complexity of Cops and Eternal Robbers, and show that the game is NP-hard when t is a fixed constant and EXPTIME-complete for large values of t. We determine precise values of  for paths and cycles. The eternal cop number is studied for retracts, and this approach is applied to give bounds for trees, as well as for strong and Cartesian grids.

2020

[19] Hybrid Dynamic Pruning for Efficient and Effective Query Processing

Authors: Wenxiu Fang, Trent G. Marbach, Gang Wang, Xiaoguang Liu

CIKM '20: Proceedings of the 29th ACM International Conference on Information & Knowledge ManagementOctober 2020 Pages 2013–2016

https://dl.acm.org/doi/10.1145/3340531.3412113

Abstact: The performance of query processing has always been a concern in the field of information retrieval. Dynamic pruning algorithms have been proposed to improve query processing performance in terms of efficiency and effectiveness. However, a single pruning algorithm generally does not have both advantages. In this work, we investigate the performance of the main dynamic pruning algorithms in terms of average and tail latency as well as the accuracy of query results, and find that they are complementary. Inspired by these findings, we propose two types of hybrid dynamic pruning algorithms that choose different combinations of strategies according to the characteristics of each query. Experimental results demonstrate that our proposed methods yield a good balance between both efficiency and effectiveness.

[18] Balanced Equi-n-squares

Authors: Saieed Akbari, Trent G. Marbach, Rebecca J. Stones, Zhuanhao Wu

Electronic Journal of Combinatorics P4.8

https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i4p8

Abstract: We define a d-balanced equi-n-square L= (l_ij), for some divisor d of n, as an n×n matrix containing symbols from Z_n in which any symbol that occurs in a row or column, occurs exactly d times in that row or column.  We show how to construct a d-balanced equi-n-square from a partition of a Latin square of order n into d×(n/d) subrectangles.  In design theory, L is equivalent to a decomposition of K_{n,n} into d-regular spanning subgraphs of K_{n/d,n/d}.  We also study when L is diagonally cyclic, defined as when l_{(i+1)(j+1)}=l_{ij}+ 1 for all i,j∈Z_n,  which corresponds to cyclic such decompositions of K_{n,n} (and thus α-labellings). 

We  identify  necessary  conditions  for  the  existence  of  (a) d-balanced  equi-n-squares,  (b) diagonally cyclic d-balanced equi-n-squares,  and (c) Latin squares of order n which partition into d×(n/d) subrectangles.  We prove the necessary conditions are sufficient for arbitrary fixed d>1 when n is sufficiently large, and were solve the existence problem completely when d∈{1,2,3}. 

Along the way, we identify a bijection between α-labellings of d-regular bipartite graphs and what we call d-starters:  matrices with exactly one filled cell in each top-left-to-bottom-right unbroken diagonal, and either d or 0 filled cells in each row and column.  We used-starters to construct diagonally cyclic d-balanced equi-n-squares, but this also gives new constructions of α-labellings.

[17] Computing Autotopism Groups of Partial Latin Rectangles

R. Stones, R. Falcon, D. Kotlar, T. Marbach

Journal of Experimental Algorithmics (2020)


[16] Audinet: A Decentralized Auditing System for Cloud Storage

Authors: Meng Yan, Jiajia Xu, Trent G. Marbach, Haitao Li, Gang Wang, Xiaoguang Liu

2020 International Symposium on Reliable Distributed Systems (SRDS)

https://ieeexplore.ieee.org/document/9252021

Abstract: In cloud storage, remote data auditing is designed to verify the integrity of cloud data on behalf of cloud users. The audit is performed by a third-party auditor (TPA) according to auditing protocols such as proof of retrievability and provable data possession. However, the TPA-based auditing framework leads to single-point failures, opaque audit processes and undetected mistakes. In this paper, we propose a decentralized auditing system in which the audit is performed by multiple auditors and the audit result is reached in a collaborative and transparent way. Auditors are selected for each audit randomly from the set of cloud users via modified cryptographic sortition; auditing procedures are implemented using a smart contract, and auditing records are published on a blockchain; an incentive mechanism is provided to regulate the behavior of system participants. We implement a prototype system and demonstrate that the proposed system is reliable and technically feasible.

[15] Improving Load Balance via Resource Exchange in Large-Scale Search Engines

K. Duan, Y. Li, T. Marbach, G. Wang, X. Liu

ICPP20 (2020)


[14] The Iterated Local Transitivity Model for Social Networks

A. Bonato, D. Cranston, M. Huggan, T. Marbach, R. Mutharasan

WAW2020 (2020)

[13] Refining Invariants for Computing Autotopism Groups of Partial Latin Rectangles

E. Danan, R. Falcon, D. Kotlar, T. Marbach

Discrete Mathematics Vol. 343, Is. 5 (2020)

www.sciencedirect.com/science/article/abs/pii/S0012365X20300030

[12] Computing Autotopism Groups of Partial Latin Rectangles: A Pilot Study 

R. Stones, R. Falcon, D. Kotlar, T. Marbach

Computational and Mathematical Methods (2020)

[11] Predicting Hard Drive Failures for Cloud Storage Systems  - (Book chapter) 

D. Liu, B. Wang, P. Li, R. Stones, T. Marbach, G. Wang, X. Liu, and Z. Li 

Algorithms and Architectures for Parallel Processing (2020)

www.springer.com/gp/book/9783030389901

2019

[10] Towards a Latin-Square Search Engine

W. Fang, R. Stones, T. Marbach, G. Wang, X. Liu. 

Proc. IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA2019) (2019)

[9] Themis: Efficient and Adaptive Resource Partitioning for Reducing Response Delay in Cloud Gaming

Y. Li, H. Liu, X. Wang, L. Pu, T. Marbach, S. Tang, G. Wang, X. Liu

Proceedings of the 27th ACM International Conference on Multimedia (MM’19)   (2019)

https://dl.acm.org/citation.cfm?id=3350941&dl=ACM&coll=DL 

[8] Gecko: A Resilient Dispersal Scheme for Multi-Cloud Storage

 M. Yan, J. Feng, Y. Kong, R. Stones, T.  Marbach, G. Wang, X. Liu, M. Su.

IEEE Access - Vol. 7, Is. 1   (2019) 

ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8728041

[7] The Enumeration of Cyclic Mutually Orthogonal Latin Squares

F. Demirkale, D. Donovan, J. Kokkala, T. Marbach

Journal of Combinatorial Designs 1--12 (2019)

https://doi.org/10.1002/jcd.21647 

2018

[6] Performance Analysis of 3D XPoint SSDs in Virtualized and non-Virtualized Environments

J. Zhang, P. Li, B. Liu, T. Marbach, X. Liu and G. Wang

IEEE ICPADS 2018 (2018)

https://ieeexplore.ieee.org/document/8644859 

[5] Two-line Graphs of Partial Latin Rectangles

E. Danan, R. Falcon, D. Kotlar, T. Marbach, R. Stones

Electronic Notes in Discrete Mathematics, 68   (2018)

https://www.sciencedirect.com/science/article/abs/pii/S157106531830101X 

[4] Load Prediction for Data Centers Based on Database Service

R. Cao, Z. Yu, T. Marbach, J. Li, G. Wang, X. Liu

COMPSAC2018 (2018)

https://ieeexplore.ieee.org/document/8377734 

[3] Covers and Partial Transversals of Latin Squares

D. Best, T. Marbach, R. Stones, I. Wanless 

Designs, Codes and Cryptography   (2018) 

https://doi.org/10.1007/s10623-018-0499-9

2016

[2] On the Intersection of Three or Four Transversals of the Back Circulant Latin Squares

2015

[1] The Spectrum for 3-way k-Homogeneous Latin Trades