The Experts below are selected from a list of 24 Experts worldwide ranked by ideXlab platform
Luís Rodrigues - One of the best experts on this subject based on the ideXlab platform.
-
ICDCS - Order-Preserving Renaming in Synchronous Systems with Byzantine Faults
2013 IEEE 33rd International Conference on Distributed Computing Systems, 2013Co-Authors: Oksana Denysyuk, Luís RodriguesAbstract:Renaming is a fundamental problem in distributed computing. It consists in having a set of processes with unique ids from a large Namespace pick distinct names from a smaller Namespace. Order-preserving renaming is a stronger variant of the renaming problem where the new names are required to preserve the ordering of the initial ids. This paper addresses order-preserving renaming in synchronous message passing systems with Byzantine failures. Although in this model order-preserving renaming can be solved by using consensus, it is known that this problem is "weaker" than consensus. Therefore, we are interested in designing algorithms that are more efficient than consensus-based solutions. This paper makes three contributions in this direction. We present an order-preserving renaming algorithm with N > 3t resiliency, a Target Namespace of size N + t -- 1, and O(log N ) round complexity (N is the number of processes and t is an upper bound on the number of faults). We also show that with N > t2 +2t our algorithm can be modified to have constant round complexity while achieving tight Namespace of size N. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication rounds with N > 2t2 + t.
-
Order-preserving Renaming in Synchronous Message Passing Systems with Byzantine Faults
arXiv: Data Structures and Algorithms, 2012Co-Authors: Oksana Denysyuk, Luís RodriguesAbstract:Renaming is a fundamental problem in distributed computing, which consists of a set of processes picking distinct names from a given Namespace. The paper presents algorithms that solve order-preserving renaming in synchronous message passing systems with Byzantine processes. To the best of our knowledge, this work is the first to address order-preserving renaming in the given model. Although this problem can be solved by using consensus, it is known that renaming is "weaker" than consensus, therefore we are mainly concerned with the efficiency of performing renaming and make three contributions in this direction. We present an order-preserving renaming algorithm for $N > 3t$ with Target Namespace of size $N+t-1$ and logarithmic step complexity (where $N$ is the number of processes and $t$ is an upper bound on the number of faults). Similarly to the existing crash-tolerant solution, our algorithm employs the ideas from the approximate agreement problem. We show that our algorithm has constant step complexity if $N>t^2+2t$ and achieves tight Namespace of size $N$. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication steps, if $N > 2t^2 + t$.
-
PODC - Brief announcement: order-preserving renaming in synchronous message passing systems with byzantine faults
Proceedings of the 2012 ACM symposium on Principles of distributed computing - PODC '12, 2012Co-Authors: Oksana Denysyuk, Luís RodriguesAbstract:Renaming is a fundamental problem in distributed computing which consists in a set of processors picking distinct names from a given Namespace. We are interested in a stronger variant of the problem in which the processors have to pick new names according to the initial order of their original ids. We assume a fully connected synchronous message passing system consisting of N processors, s of which can exhibit Byzantine behavior. In a synchronous model, renaming can be solved using consensus. However, it is known that renaming is "easier" than consensus. Therefore, in this work we are mainly concerned with the efficiency of performing renaming and briefly describe two contributions in this direction. The first contribution consists in an order-preserving renaming algorithm for N > 3t2 with constant step complexity and Target Namespace of size N2+Nt. As a second contribution we present an order preserving renaming algorithm with O(log N) step complexity and Target Namespace of size 2N, for N > 3t. Full version of this paper is available in [2].
Oksana Denysyuk - One of the best experts on this subject based on the ideXlab platform.
-
Order-Preserving Renaming in Synchronous Systems with Byzantine Faults
2016Co-Authors: Oksana DenysyukAbstract:Abstract—Renaming is a fundamental problem in distributed computing, which consists of a set of processes picking distinct names from a given Namespace. The paper presents algorithms that solve order-preserving renaming in synchronous message passing systems with Byzantine processes. To the best of our knowledge, this work is the first to address order-preserving renaming in the given model. Although this problem can be solved by using consensus, it is known that renaming is “weaker ” than consensus, therefore we are mainly concerned with the efficiency of performing renaming and make three contributions in this direction. We present an order-preserving renaming algorithm for N> 3t with Target Namespace of size N+t−1 and logarithmic step complexity (where N is the number of processes and t is an upper bound on the number of faults). Similarly to the existing crash-tolerant solution, our algorithm employs the ideas from the approximate agreement problem. We show that our algorithm has constant step complexity if N> t2 + 2t and achieves tight Namespace of size N. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication steps, if N> 2t2 + t. I
-
ICDCS - Order-Preserving Renaming in Synchronous Systems with Byzantine Faults
2013 IEEE 33rd International Conference on Distributed Computing Systems, 2013Co-Authors: Oksana Denysyuk, Luís RodriguesAbstract:Renaming is a fundamental problem in distributed computing. It consists in having a set of processes with unique ids from a large Namespace pick distinct names from a smaller Namespace. Order-preserving renaming is a stronger variant of the renaming problem where the new names are required to preserve the ordering of the initial ids. This paper addresses order-preserving renaming in synchronous message passing systems with Byzantine failures. Although in this model order-preserving renaming can be solved by using consensus, it is known that this problem is "weaker" than consensus. Therefore, we are interested in designing algorithms that are more efficient than consensus-based solutions. This paper makes three contributions in this direction. We present an order-preserving renaming algorithm with N > 3t resiliency, a Target Namespace of size N + t -- 1, and O(log N ) round complexity (N is the number of processes and t is an upper bound on the number of faults). We also show that with N > t2 +2t our algorithm can be modified to have constant round complexity while achieving tight Namespace of size N. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication rounds with N > 2t2 + t.
-
Order-preserving Renaming in Synchronous Message Passing Systems with Byzantine Faults
arXiv: Data Structures and Algorithms, 2012Co-Authors: Oksana Denysyuk, Luís RodriguesAbstract:Renaming is a fundamental problem in distributed computing, which consists of a set of processes picking distinct names from a given Namespace. The paper presents algorithms that solve order-preserving renaming in synchronous message passing systems with Byzantine processes. To the best of our knowledge, this work is the first to address order-preserving renaming in the given model. Although this problem can be solved by using consensus, it is known that renaming is "weaker" than consensus, therefore we are mainly concerned with the efficiency of performing renaming and make three contributions in this direction. We present an order-preserving renaming algorithm for $N > 3t$ with Target Namespace of size $N+t-1$ and logarithmic step complexity (where $N$ is the number of processes and $t$ is an upper bound on the number of faults). Similarly to the existing crash-tolerant solution, our algorithm employs the ideas from the approximate agreement problem. We show that our algorithm has constant step complexity if $N>t^2+2t$ and achieves tight Namespace of size $N$. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication steps, if $N > 2t^2 + t$.
-
PODC - Brief announcement: order-preserving renaming in synchronous message passing systems with byzantine faults
Proceedings of the 2012 ACM symposium on Principles of distributed computing - PODC '12, 2012Co-Authors: Oksana Denysyuk, Luís RodriguesAbstract:Renaming is a fundamental problem in distributed computing which consists in a set of processors picking distinct names from a given Namespace. We are interested in a stronger variant of the problem in which the processors have to pick new names according to the initial order of their original ids. We assume a fully connected synchronous message passing system consisting of N processors, s of which can exhibit Byzantine behavior. In a synchronous model, renaming can be solved using consensus. However, it is known that renaming is "easier" than consensus. Therefore, in this work we are mainly concerned with the efficiency of performing renaming and briefly describe two contributions in this direction. The first contribution consists in an order-preserving renaming algorithm for N > 3t2 with constant step complexity and Target Namespace of size N2+Nt. As a second contribution we present an order preserving renaming algorithm with O(log N) step complexity and Target Namespace of size 2N, for N > 3t. Full version of this paper is available in [2].
Michael S. Okun - One of the best experts on this subject based on the ideXlab platform.
-
On the Power of Impersonation Attacks
arXiv: Distributed Parallel and Cluster Computing, 2010Co-Authors: Michael S. OkunAbstract:In this paper we consider a synchronous message passing system in which in every round an external adversary is able to send each processor up to k messages with falsified sender identities and arbitrary content. It is formally shown that this impersonation model is slightly stronger than the asynchronous message passing model with crash failures. In particular, we prove that (k+1)-set agreement can be solved in this model, while k-set agreement is impossible, for any k>=1. The different strength of the asynchronous and impersonation models is exhibited by the order preserving renaming problem, for which an algorithm with n+k Target Namespace exists in the impersonation model, while an exponentially larger Namespace is required in case of asynchrony.
Okun Michael - One of the best experts on this subject based on the ideXlab platform.
-
On the Power of Impersonation Attacks
2010Co-Authors: Okun MichaelAbstract:In this paper we consider a synchronous message passing system in which in every round an external adversary is able to send each processor up to k messages with falsified sender identities and arbitrary content. It is formally shown that this impersonation model is slightly stronger than the asynchronous message passing model with crash failures. In particular, we prove that (k+1)-set agreement can be solved in this model, while k-set agreement is impossible, for any k>=1. The different strength of the asynchronous and impersonation models is exhibited by the order preserving renaming problem, for which an algorithm with n+k Target Namespace exists in the impersonation model, while an exponentially larger Namespace is required in case of asynchrony.Comment: This is the full version of a brief announcement (under the same name), which appeared in Proc. 21st International Symposium on Distributed Computing (DISC 07
James Bean - One of the best experts on this subject based on the ideXlab platform.
-
Schema Assembly and Reuse
SOA and Web Services Interface Design, 2010Co-Authors: James BeanAbstract:XML schemas are not only powerful implementations of metadata rules and constraints, but they are also subject to reuse. The ability to reuse XML schemas as a form of reference and assembly is a powerful service interface capability. There are powerful schema reuse examples, where schemas without a Target Namespace can be inherited and applied in many different contexts. The patterns and techniques most often applied to schema reuse include no-Namespace schemas (referenced by the XML schema “include” and “redefine” declarations), Namespace-qualified schemas (referenced by the XML schema “import” declaration), and wildcard schemas (referenced by the XML schema “any” declaration). Each of these techniques has advantages and disadvantages. As a general recommendation, the service interface designer should avoid the XML schema “redefine” declaration. Critical to the application of any interface schema reuse is ensuring that the reusable schemas were designed and developed with intent to reuse. There are several important design considerations to resolve when designing a new, reusable schema. The designer must ensure that the schema is of appropriate granularity, is reasonably static (not subject to frequent change), is identified in a way that is discoverable, exploits the “global declarations” pattern, and is based on well-defined metadata standards. The XML schemas syntax is extensive, and there are often a number of different approaches to defining a schema-based interface. Validating and testing the interface schemas are also important. An effective XML schema-based Web service interface will have been tested and proven before it is deployed.
