Matching Items (14)
Description
Peer-to-peer systems are known to be vulnerable to the Sybil attack. The lack of a central authority allows a malicious user to create many fake identities (called Sybil nodes) pretending to be independent honest nodes. The goal of the malicious user is to influence the system on his/her behalf. In order to detect the Sybil nodes and prevent the attack, a reputation system is used for the nodes, built through observing its interactions with its peers. The construction makes every node a part of a distributed authority that keeps records on the reputation and behavior of the nodes. Records of interactions between nodes are broadcast by the interacting nodes and honest reporting proves to be a Nash Equilibrium for correct (non-Sybil) nodes. In this research is argued that in realistic communication schedule scenarios, simple graph-theoretic queries such as the computation of Strongly Connected Components and Densest Subgraphs, help in exposing those nodes most likely to be Sybil, which are then proved to be Sybil or not through a direct test executed by some peers.
ContributorsCárdenas-Haro, José Antonio (Author) / Konjevod, Goran (Thesis advisor) / Richa, Andréa W. (Thesis advisor) / Sen, Arunabha (Committee member) / Xue, Guoliang (Committee member) / Arizona State University (Publisher)
Created2010
Description
In a multi-robot system, locating a team robot is an important issue. If robots
can refer to the location of team robots based on information through passive action
recognition without explicit communication, various advantages (e.g. improving security
for military purposes) can be obtained. Specifically, when team robots follow
the same motion rule based on information about adjacent robots, associations can
be found between robot actions. If the association can be analyzed, this can be a clue
to the remote robot. Using these clues, it is possible to infer remote robots which are
outside of the sensor range.
In this paper, a multi-robot system is constructed using a combination of Thymio
II robotic platforms and Raspberry pi controllers. Robots moving in chain-formation
take action using motion rules based on information obtained through passive action
recognition. To find associations between robots, a regression model is created using
Deep Neural Network (DNN) and Long Short-Term Memory (LSTM), one of state-of-art technologies.
The input data of the regression model is divided into historical data, which
are consecutive positions of the robot, and observed data, which is information about the
observed robot. Historical data is sequence data that is analyzed through the LSTM
layer. The accuracy of the regression model designed using DNN can vary depending
on the quantity and quality of the input. In this thesis, three different input situations
are assumed for comparison. First, the amount of observed data is different, second, the
type of observed data is different, and third, the history length is different. Comparative
models are constructed for each case, and prediction accuracy is compared to analyze
the effect of input data on the regression model. This exploration validates that these
methods from deep learning can reduce the communication demands in coordinated
motion of multi-robot systems
can refer to the location of team robots based on information through passive action
recognition without explicit communication, various advantages (e.g. improving security
for military purposes) can be obtained. Specifically, when team robots follow
the same motion rule based on information about adjacent robots, associations can
be found between robot actions. If the association can be analyzed, this can be a clue
to the remote robot. Using these clues, it is possible to infer remote robots which are
outside of the sensor range.
In this paper, a multi-robot system is constructed using a combination of Thymio
II robotic platforms and Raspberry pi controllers. Robots moving in chain-formation
take action using motion rules based on information obtained through passive action
recognition. To find associations between robots, a regression model is created using
Deep Neural Network (DNN) and Long Short-Term Memory (LSTM), one of state-of-art technologies.
The input data of the regression model is divided into historical data, which
are consecutive positions of the robot, and observed data, which is information about the
observed robot. Historical data is sequence data that is analyzed through the LSTM
layer. The accuracy of the regression model designed using DNN can vary depending
on the quantity and quality of the input. In this thesis, three different input situations
are assumed for comparison. First, the amount of observed data is different, second, the
type of observed data is different, and third, the history length is different. Comparative
models are constructed for each case, and prediction accuracy is compared to analyze
the effect of input data on the regression model. This exploration validates that these
methods from deep learning can reduce the communication demands in coordinated
motion of multi-robot systems
ContributorsKang, Sehyeok (Author) / Pavlic, Theodore P (Thesis advisor) / Richa, Andréa W. (Committee member) / Yang, Yezhou (Committee member) / Arizona State University (Publisher)
Created2020
Description
This thesis addresses the following fundamental maximum throughput routing problem: Given an arbitrary edge-capacitated n-node directed network and a set of k commodities, with source-destination pairs (s_i,t_i) and demands d_i> 0, admit and route the largest possible number of commodities -- i.e., the maximum throughput -- to satisfy their demands.
The main contributions of this thesis are three-fold: First, a bi-criteria approximation algorithm is presented for this all-or-nothing multicommodity flow (ANF) problem. This algorithm is the first to achieve a constant approximation of the maximum throughput with an edge capacity violation ratio that is at most logarithmic in n, with high probability. The approach used is based on a version of randomized rounding that keeps splittable flows, rather than approximating those via a non-splittable path for each commodity: This allows it to work for arbitrary directed edge-capacitated graphs, unlike most of the prior work on the ANF problem. The algorithm also works if a weighted throughput is considered, where the benefit gained by fully satisfying the demand for commodity i is determined by a given weight w_i>0. Second, a derandomization of the algorithm is presented that maintains the same approximation bounds, using novel pessimistic estimators for Bernstein's inequality. In addition, it is shown how the framework can be adapted to achieve a polylogarithmic fraction of the maximum throughput while maintaining a constant edge capacity violation, if the network capacity is large enough. Lastly, one important aspect of the randomized and derandomized algorithms is their simplicity, which lends to efficient implementations in practice. The implementations of both randomized rounding and derandomized algorithms for the ANF problem are presented and show their efficiency in practice.
The main contributions of this thesis are three-fold: First, a bi-criteria approximation algorithm is presented for this all-or-nothing multicommodity flow (ANF) problem. This algorithm is the first to achieve a constant approximation of the maximum throughput with an edge capacity violation ratio that is at most logarithmic in n, with high probability. The approach used is based on a version of randomized rounding that keeps splittable flows, rather than approximating those via a non-splittable path for each commodity: This allows it to work for arbitrary directed edge-capacitated graphs, unlike most of the prior work on the ANF problem. The algorithm also works if a weighted throughput is considered, where the benefit gained by fully satisfying the demand for commodity i is determined by a given weight w_i>0. Second, a derandomization of the algorithm is presented that maintains the same approximation bounds, using novel pessimistic estimators for Bernstein's inequality. In addition, it is shown how the framework can be adapted to achieve a polylogarithmic fraction of the maximum throughput while maintaining a constant edge capacity violation, if the network capacity is large enough. Lastly, one important aspect of the randomized and derandomized algorithms is their simplicity, which lends to efficient implementations in practice. The implementations of both randomized rounding and derandomized algorithms for the ANF problem are presented and show their efficiency in practice.
ContributorsChaturvedi, Anya (Author) / Richa, Andréa W. (Thesis advisor) / Sen, Arunabha (Committee member) / Schmid, Stefan (Committee member) / Arizona State University (Publisher)
Created2020
Description
We describe mechanical metamaterials created by folding flat sheets in the tradition of origami, the art of paper folding, and study them in terms of their basic geometric and stiffness properties, as well as load bearing capability. A periodic Miura-ori pattern and a non-periodic Ron Resch pattern were studied. Unexceptional coexistence of positive and negative Poisson's ratio was reported for Miura-ori pattern, which are consistent with the interesting shear behavior and infinity bulk modulus of the same pattern. Unusually strong load bearing capability of the Ron Resch pattern was found and attributed to the unique way of folding. This work paves the way to the study of intriguing properties of origami structures as mechanical metamaterials.
ContributorsLv, Cheng (Author) / Krishnaraju, Deepak Shyam (Author) / Konjevod, Goran (Author) / Yu, Hongyu (Author) / Jiang, Hanqing (Author) / Ira A. Fulton Schools of Engineering (Contributor)
Created2014-08-07