Model checking is an automatic verification technique, which provides an answer to the question whether a pro-gram, given as a state-transition system, satisfies its specification, given in terms of a temporal-logic f...
详细信息
ISBN:
(纸本)9781467393171
Model checking is an automatic verification technique, which provides an answer to the question whether a pro-gram, given as a state-transition system, satisfies its specification, given in terms of a temporal-logic formula. Model checking is very well studied as far as boolean finite-state programs are concerned [CGP99].
Designing privacy-preserving distributed algorithms for stochastic aggregative games is urgent due to the privacy issues caused by information exchange between players. This paper proposes two differentially private d...
详细信息
Designing privacy-preserving distributed algorithms for stochastic aggregative games is urgent due to the privacy issues caused by information exchange between players. This paper proposes two differentially private distributed algorithms seeking the Nash equilibrium in stochastic aggregative games. By adding time-varying random noises, the input and output-perturbation methods are given to protect each player's sensitive information. For the case of output-perturbation, utilizing mini-batch methods, the algorithm's mean square error is inversely proportional to the privacy level E and the number of samples. For the case of input-perturbation, a differentially private distributed stochastic approximation-type algorithm is developed to achieve almost sure convergence and (epsilon, delta)-differential privacy. Under suitable consensus time conditions, the algorithm's convergence rate is rigorously presented for the first time, where the optimal convergence rate O(1/k) in a mean square sense is obtained. Then, utilizing mini-batch methods, the influence of added privacy noise on the algorithm's performance is reduced, and the convergence rate of the algorithm is improved. Specifically, when the batch sizes and the number of consensus times at each iteration grow at a suitable rate, an exponential rate of convergence can be achieved with the same privacy level. Finally, a simulation example demonstrates the algorithms' effectiveness. (C) 2022 Elsevier Ltd. All rights reserved.
Motivated by both distributed computation and decentralized control applications, we studied the distributed linear iterative algorithms with memory. Specifically, we showed that the system of linear equations Gx = b ...
详细信息
Motivated by both distributed computation and decentralized control applications, we studied the distributed linear iterative algorithms with memory. Specifically, we showed that the system of linear equations Gx = b b can be solved through a distributed linear iteration for arbitrary invertible G using only a single memory element at each processor. Further, we demonstrated that the memoried distributed algorithm can be designed to achieve much faster convergence than a memoryless distributed algorithm. Two small simulation examples were included to illustrate the results. Copyright (c) 2011 John Wiley & Sons, Ltd.
If each node in a wireless network has information about only its 1-hop neighborhood, then what are the limits to performance? This problem is considered for wireless networks where each communication link has a minim...
详细信息
If each node in a wireless network has information about only its 1-hop neighborhood, then what are the limits to performance? This problem is considered for wireless networks where each communication link has a minimum bandwidth quality-of-service (QoS) requirement. Links in the same vicinity contend for the shared wireless medium. The conflict graph captures which pairs of links interfere with each other and depends on the MAC protocol. In IEEE 802.11 MAC protocol-based networks, when communication between nodes i and j takes place, the neighbors of both i and j remain silent. This model of interference is called the 2-hop interference model because the distance in the network graph between any two links that can be simultaneously active is at least 2. In the admission control problem studied in the present paper, the objective is to determine, using only localized information, whether a given set of flow rates is feasible. While distance -d distributed algorithms have been analyzed for the 1-hop interference model, an open problem in the literature is to extend these results to the K-hop interference model, and the present work initiates the generalization to the K-hop interference model. We show that the centralized version of the problem is NP-hard and then investigate distributed, low-complexity solutions for this problem. We propose a distributed algorithm for this problem where each node has information about only its 1-hop neighborhood. The worst-case performance of the distributed algorithm, i.e. the largest factor by which the performance of this distributed algorithm is away from that of an optimal, centralized algorithm, is analyzed. Lower and upper bounds on the suboptimality of the distributed algorithm are obtained, and both bounds are shown to be tight. The exact worst-case performance is obtained for some ring topologies. The performance of the distance-1 distributed algorithm is compared with that of the row constraints, and these two distributed
This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number...
详细信息
This paper studies the "usefulness" of initial conditions for distributed algorithms on anonymous networks. In the literature, several initial conditions such as making one vertex a leader, giving the number of vertex to each vertices, and so on, have been considered. In this paper, we study a relation between the initial condition by considering transformation algorithm from one initial condition to another. For such transformation algorithms, we consider in this paper, both deterministic and randomized distributed algorithms. For each deterministic and randomized transformation type, we show that the relation induces an infinite lattice structure among equivalence classes of initial conditions.
Designing, tuning, and analyzing the performance of distributed algorithms and protocols are complex tasks. A major factor that contributes to this complexity is the fact that there is no single environment to support...
详细信息
Designing, tuning, and analyzing the performance of distributed algorithms and protocols are complex tasks. A major factor that contributes to this complexity is the fact that there is no single environment to support all phases of the development of a distributed algorithm. This paper presents Neko, an easy-to-use Java platform that provides a uniform and extensible environment for various phases of algorithm design and performance evaluation: prototyping, tuning, simulation, deployment, etc.
Over the last two decades, considerable research has been done in distributed operating systems, which can be attributed to faster processors and better communication technologies. A distributed operating system requi...
详细信息
Over the last two decades, considerable research has been done in distributed operating systems, which can be attributed to faster processors and better communication technologies. A distributed operating system requires distributed algorithms to provide basic operating system functionality like mutual exclusion, deadlock detection, etc. A number of such algorithms have been proposed in the literature. Traditionally, these distributed algorithms have been presented,in a theoretical way, with limited attempts to simulate actual working models. This paper discusses our experience in simulating distributed algorithms with the aid of some existing tools, including OPNET and Xplot. We discuss our efforts to define a basic model-based framework for rapid simulation and visualization and illustrate how we used this framework to evaluate some classic algorithms. We have also shown how the performance of different algorithms can be compared based on some collected statistics. To keep the focus of this paper on the approach itself, and our experience with tool integration, we only discuss some relatively simple models. Yet, the approach can be applied to more complex algorithm specifications. Copyright (C) 2001 John Wiley & Sons, Ltd.
distributed computation has attracted considerable attention and large-scale distributed systems have been designed and developed. A distributed system inherently has possibility of fault tolerance because of its redu...
详细信息
distributed computation has attracted considerable attention and large-scale distributed systems have been designed and developed. A distributed system inherently has possibility of fault tolerance because of its redundancy. Thus, a great deal of investigation has been made to design fault-tolerant distributed algorithms. This paper introduces two promising paradigms, self-stabilization and wait-freedom, for designing fault-tolerant distributed algorithms and discusses some subjects important from the point of view of algorithm engineering.
We call a network an anonymous network, if each vertex of the network is given no ID's. For distributed algorithms fur anonymous networks, solvable problems depend strongly on the given initial conditions. In the ...
详细信息
We call a network an anonymous network, if each vertex of the network is given no ID's. For distributed algorithms fur anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions A and B (denoted by A greater than or equal to B) as the relation that some distributed algorithm can compute B on any network satisfying A. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions k-LEADER and k-COLOR. k-LEADER denotes the initial condition that gives special condition only to k vertices. k-COLOR denotes the initial condition that divides the vertices into k groups. Then we, investigate the property of the relation among these initial conditions.
distributed algorithms have become a rapidly growing field of research due to the advances of the network technologies. However, they are very difficult to implement correctly because they must meet many requirements....
详细信息
distributed algorithms have become a rapidly growing field of research due to the advances of the network technologies. However, they are very difficult to implement correctly because they must meet many requirements. In this paper, we follow the guidelines of systematic literature reviews to provide a survey of the existing works ensuring the formal verification of distributed algorithms in static and dynamic networks. Then, we develop a taxonomy of these solutions based on some criteria. Also, a discussion on each criterion is shown with a focus on constraints, requirements and challenges. Finally, we identify some recommendations and open research areas which can motivate the development of more efficient solutions. So, throughout this present paper, we provide information for researchers and developers to understand the contributions and challenges of the existing solutions to pave the way for enhancing their reliability.
暂无评论