共查询到10条相似文献,搜索用时 134 毫秒
1.
A population protocol is one of distributed computing models for passively-mobile systems, where a number of agents change
their states by pairwise interactions between two agents. In this paper, we investigate the solvability of the self-stabilizing
leader election in population protocols without any kind of oracles. We identify the necessary and sufficient conditions to
solve the self-stabilizing leader election in population protocols from the aspects of local memory complexity and fairness
assumptions. This paper shows that under the assumption of global fairness, no protocol using only n−1 states can solve the self-stabilizing leader election in complete interaction graphs, where n is the number of agents in the system. To prove this impossibility, we introduce a novel proof technique, called closed-set
argument. In addition, we propose a self-stabilizing leader election protocol using n states that works even under the unfairness assumption. This protocol requires the exact knowledge about the number of agents
in the system. We also show that such knowledge is necessary to construct any self-stabilizing leader election protocol. 相似文献
2.
Dolev S. Israeli A. Moran S. 《IEEE transactions on pattern analysis and machine intelligence》1995,21(5):429-439
We introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the performance of randomized distributed protocols. We apply it in studying uniform self-stabilizing protocols for leader election under read/write atomicity. We present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique 相似文献
3.
Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing
protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient
fault can cause vast disruption in the system before legitimacy is reached. This paper introduces the notion of fault-containment
to address this particular weakness of self-stabilizing systems. Informally, a fault-containing self-stabilizing protocol,
in addition to providing self- stabilization, contains the effects of faults. This ensures that disruption during recovery from faults, is proportional to the extent of the faults.
The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. The main
result of the paper is a transformer that converts any non-reactive self-stabilizing protocol into an equivalent fault-containing
self-stabilizing protocol that can repair any single fault in the system in O(1) time. For a large class of input protocols, the corresponding output protocols produced by the transformer have O(1) space overhead. The small time and space overhead make the fault-containing self-stabilizing protocol a practical alternative
to the original self-stabilizing protocol. The transformer is based on a novel stabilizing timer paradigm that significantly
simplifies the task of fault-containment. 相似文献
4.
When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to resolve the nondeterminism. It has been observed that for certain applications, notably those in security, the scheduler needs to be restricted so not to reveal the outcome of the protocol’s random choices, or otherwise the model of adversary would be too strong even for “obviously correct” protocols. We propose a process-algebraic framework in which the control on the scheduler can be specified in syntactic terms, and we show how to apply it to solve the problem mentioned above. We also consider the definition of (probabilistic) may and must preorders, and we show that they are precongruences with respect to the restricted schedulers. Furthermore, we show that all the operators of the language, except replication, distribute over probabilistic summation, which is a useful property for verification. 相似文献
5.
Dolev S. Israeli A. Moran S. 《Parallel and Distributed Systems, IEEE Transactions on》1997,8(4):424-440
A distributed system is self-stabilizing if it can be started in any possible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next faulty period is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbors are identical. A distributed system is dynamic if it can tolerate addition or deletion of processors and links without reinitialization. In this work, we study uniform dynamic self-stabilizing protocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stabilizes in O(ΔD log n) time when the number of the processors is unknown and O(ΔD), otherwise. Here Δ denotes the maximal degree of a node, D denotes the diameter of the graph and n denotes the number of processors in the graph. We introduce self-stabilizing protocols for synchronization that are used as building blocks by the leader-election algorithm. We conclude this work by presenting a simple, uniform, self-stabilizing ranking protocol 相似文献
6.
Our purpose in this paper is to propose a self-stabilizing protocol for weakly connected dominating set (WCDS) set in a given
ad hoc network graph. WCDS is a particular variant of graph domination predicates which play an important role in routing
in ad hoc networks. There are many variants of domination problems in bidirectional networks; WCDS is also useful in forming
clusters in ad hoc networks. There are many heuristic and distributed algorithms to compute WCDS in network graphs while almost
all of them will need complete information about the network topology and most of them are not fault tolerant or mobility
tolerant. Self-stabilization is a protocol design paradigm that is especially useful in resource constrained infrastructure-less
networks since nodes can make moves based on local knowledge only and yet a global task is accomplished in a fault tolerant
manner; it also facilitates for nodes to enter and exit the network freely. There exist self-stabilizing protocols for minimal
spanning tree, total domination, and others. We have shown that the paradigm is capable of designing a protocol for WCDS.
Our objective is to mathematically prove the correctness and the convergence of the protocol in any worst-case scenario, as
is usually done for self-stabilizing protocols for other graph predicates used for ad hoc networks. 相似文献
7.
《Journal of Parallel and Distributed Computing》2002,62(5):885-898
This paper presents a uniform randomized self-stabilizing mutual exclusion algorithm for an anonymous unidirectional ring of any size n, running under an unfair distributed scheduler (d-daemon). The system is stabilized with probability 1 in O(n3) expected number of steps, and each process is privileged at least once in every 2n steps, once it is stabilized. 相似文献
8.
Synnöve Kekkonen-Moneta 《Distributed Computing》2002,15(1):39-48
A torus is oriented if the processes have assigned their communication links North-East-South-West labels in a globally consistent
manner. This paper presents an orientation protocol that is self-stabilizing, i.e., resilient to corruption of data stored
in working memories and communication links. The protocol is randomized, uses constant memory space, and orients tori where
the processes do not know the network size and have no identifiers; probabilistic stabilization is proved under a restricted
form of asynchrony and composite atomicity.
Received: November 1998 / Accepted: March 2001 相似文献
9.
Sre
ko Brlek Sardaouna Hamadou John Mullins 《Electronic Notes in Theoretical Computer Science》2007,194(1):61
When modelling cryto-protocols by means of process calculi which express both nondeterministic and probabilistic behavior, it is customary to view the scheduler as an intruder. It has been established that the traditional scheduler needs to be carefully calibrated in order to more accurately reflect the intruder's capabilities for controlling communication channels. We propose such a class of schedulers through a semantic variant called PPCνσ, of the Probabilistic Poly-time Calculus (PPC) of Mitchell et al. [J.C. Mitchell, A. Ramanathan, A. Scedrov, and V. Teague. A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols. Theoretical Computer Science, 353:118–164, 2006] and we illustrate the pertinence of our approach by an extensive study of the Dining Cryptographers (DCP) [David Chaum. The dining cryptographers problem: Unconditional sender and recipient untraceability. J. Cryptology, 1(1):65–75, 1988] protocol. Along these lines, we define a new characterization of Mitchell et al.'s observational equivalence [J.C. Mitchell, A. Ramanathan, A. Scedrov, and V. Teague. A probabilistic polynomial-time process calculus for the analysis of cryptographic protocols. Theoretical Computer Science, 353:118–164, 2006] more suited for taking into account any observable trace instead of just a single action as required in the analysis of the DCP. 相似文献
10.
Distributed queuing is a fundamental coordination problem arising in a variety of applications, including distributed shared memory, distributed directories, and totally ordered multicast. A distributed queue can be used to order events, user operations, or messages in a distributed system. This paper presents a new self-stabilizing distributed queuing protocol. This protocol adds self-stabilizing actions to the arrow distributed queuing protocol, a simple path-reversal protocol that runs on a spanning tree of the network. We present a proof that the protocol stabilizes to a stable state irrespective of the (perhaps faulty) initial state, and also present an analysis of the time until convergence. The self-stabilizing queuing protocol is structured as a layer that runs on top of any self-stabilizing spanning tree protocol. This additional queuing layer is guaranteed to stabilize in time bounded by a constant number of message delays across an edge, thus establishing that the stabilization time for distributed queuing is not much more than the stabilization time for spanning tree maintenance. The key idea in our protocol is that the global predicate defining the legality of a protocol state can be written as the conjunction of many purely local predicates, one for each edge of the spanning tree. 相似文献