共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
《Journal of Parallel and Distributed Computing》2000,60(5):566-584
We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. This measure of fault tolerance is similar to the competitive factor of on-line algorithms: in both cases, the performance of an algorithm lacking some crucial information is compared to the performance of an “off-line” algorithm, one that is given this information as input. It is also the first known tool to measure and compare fault tolerance of broadcasting schemes in trees. We seek broadcasting schemes with low vulnerability, working for tree networks. It turns out that schemes that give the best broadcasting time in a fault-free environment may have very high vulnerability, i.e., poor fault tolerance, for some trees. The main result of this paper is an algorithm that, given an arbitrary tree T and an integer k, computes a broadcasting scheme B with lowest possible k-vulnerability among all schemes working for T. Our algorithm has running time O(kn2+n2 log n), where n is the size of the tree. We also give an algorithm to find a “universally fault-tolerant” broadcasting scheme in a tree T: one that approximates the lowest possible k-vulnerability, for all k simultaneously. 相似文献
3.
4.
The problem of finding a spanning forest of a graph
in a distributed-processing environment is studied.
If an input graph is weighted, then the goal is to find
a minimum-weight spanning forest.
The processors communicate by broadcasting.
The output consists of the edges that make
a spanning forest and have been broadcast on the network.
Input edges are distributed among the processors, with
each edge held by one processor.
The underlying broadcast network is implemented as a multiple-access
channel.
If exactly one processor attempts to perform a broadcast,
then the broadcast is successful.
A message broadcast successfully is delivered to all the
processors in one step.
If more than one processors broadcast simultaneously, then the
messages interfere with each other and no processor can
receive any of them.
Optimality of algorithmic solutions is investigated,
by way of comparing deterministic with randomized algorithms,
and adaptive with oblivious ones.
Lower bounds are proved that either justify the optimality
of specific algorithms or show that the optimal performance
depends on a class of algorithms. 相似文献
5.
We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length , for every n-node graph of diameter D, thus improving a result of Gąsieniec et al. (PODC 2005) [17] and solving a problem stated there. Unless the inclusion NP BPTIME( holds, the length of a polynomially constructible deterministic broadcast scheme is optimal.A preliminary version of this paper (with a weaker result) appeared in the Proc. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’2004), August 2004, Harvard University, Cambridge, USA, LNCS 3122, 171–182. Research of the second author supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. Part of this work was done during the second author’s visit at the Max-Planck-Institut für Informatik. 相似文献
6.
在介绍环Zn上广义圆锥曲线的阶和基点、离散对数问题、明文嵌入与译码算法的基础上,研究多重数字签名中的广播多重数字签名。该方案的安全性是基于大整数分解的困难问题和离散对数问题,而且其在点的计算、明文嵌入都较容易实现,还能抵抗Pohlig-Hellman攻击以及小指数攻击和Wiener攻击。 相似文献
7.
《Journal of Parallel and Distributed Computing》1994,22(2):295-313
We propose a nonredundant broadcasting scheme for injured hypercube multicomputers with direct-connection capability, that is, where each hypercube node has a separate router. The proposed scheme is first presented to cover faulty links only. Under the assumption that no more than n − 1 faulty links exist in an injured n-cube, the proposed scheme is optimal in the sense that it generates a spanning binomial tree from a given node whenever there exists such a tree originated from that node. The scheme is also extended to cover both node and link faults. Although the extended scheme is no longer optimal, we show that by using the extended scheme the maximum number of routing steps required from the source node s to any other node a is H(s, a) + 2, where H stands for the Hamming distance. The proposed scheme uses global network information. Evaluation studies show that the proposed scheme achieves optimal broadcasting a high percentage of times. 相似文献
8.
Krzysztof Diks Andrzej Lingas Andrzej Pelc 《Journal of Parallel and Distributed Computing》1999,59(3):524
We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of its already obtained messages to one of its children. A k-message broadcasting scheme prescribes in which time unit a given node should send a message to which child. It is k-optimal if it achieves the smallest possible time for broadcasting k messages from the source to all nodes. We give an algorithm to construct a k-optimal broadcasting scheme for an arbitrary n-node tree. The time complexity of our algorithm is O(nk), i.e., the best possible. 相似文献
9.
Richard J. Orgass 《Software》1981,11(12):1265-1271
A well designed file system can significantly simplify the design of and increase the reliability of interactive programs. A summary of the specifications of a convenient file system that is substantially independent of the host operating system and some experiences using the system are described. 相似文献
10.
We consider broadcasting among n processors, f of which can be faulty. A fault-free processor, called the source, holds a piece of information which has to be transmitted
to all other fault-free processors. We assume that the fraction f/n of faulty processors is bounded by a constant γ<1 . Transmissions are fault free. Faults are assumed to be of the crash type: faulty processors do not send or receive messages. We use the whispering model: pairs of processors communicating in one round must form a matching. A fault-free processor sending a message to
another processor becomes aware of whether this processor is faulty or fault free and can adapt future transmissions accordingly.
The main result of the paper is a broadcasting algorithm working in O( log n) rounds and using O(n) messages of logarithmic size, in the worst case. This is an improvement of the result from [17] where O ((log n)
2
) rounds were used. Our method also gives the first algorithm for adaptive distributed fault diagnosis in O( log n) rounds.
Received May 1997; revised May 1998. 相似文献
11.
通过分析FTP超大文件上传的技术实现方法,对断点续传在算法复杂性上进行讨论,提出了基于事务完整性的解决方案,并在实践中得到了成功应用。 相似文献
12.
彭家寅 《计算机工程与应用》2021,57(10):88-93
利用一个五粒子团簇态为信道,分别提出了三个关于二粒子态和单粒子态的双向受控量子信息传输协议。在第一个协议中,通过引入辅助粒子,实施受控非门运算和Bell态测量,Alice能把二粒子未知态传送给Bob,同时Bob也能把单粒子未知态传送给Alice。在第二个方案中,通过引入辅助粒子、巧妙构造正交基和执行单粒子投影测量,Alice能帮助Bob远程地制备二粒子已知态,同时Bob也能帮助Alice远程地制备单粒子已知态。由于他们充分利用了前馈策略去构造测量基,制备任务能够完美完成。在第三个方案中,结合前两个方案的特点,Alice能成功将二粒子未知态传送给Bob,Bob也完美地在Alice处制备单粒子已知态。上述三个方案离开监控者的允许是不能实现的。 相似文献
13.
14.
基于Silverlight大文件上传的两种实现方案 总被引:1,自引:0,他引:1
介绍了实现开发RIA(富媒体Rich Internet Applications)应用的Silverlight技术.利用Silverliht客户端编程的特点,及其与WEB服务器通信的机制,提出了两种实现大文件上传方案,并对两种方案进行了对比分析.两种方案都能很好地解决大文件上传的难题,具有一定的应用价值. 相似文献
15.
光突发交换是实现IP/DWDM网络的一种非常有前途的方案.已有的FF调度算法和LAU调度算法都没有考虑QoS功能、波长转换等因素,在此基础上,进行了部分改进.提出了两种改进型的网络数据信道调度算法:优化波长转换调度算法OWCT和重分服务(RFA)调度算法.通过NS2仿真实验验证,证明这两种改进型的数据信道调度算法在确保高优先权的数据可靠性传输方面、减少光突发交换网络中的光信号的波长转换次数方面,与已有的FF调度算法和LAU调度算法相比,具有更好的性能. 相似文献
16.
Automation and Remote Control - We consider the problem of optimizing the operation of a queuing system in which the number of working service channels can be changed in a controlled manner at... 相似文献
17.
18.
李志伟 《计算机工程与应用》2003,39(11):103-105
文章简要介绍了贪心算法的基本原理,详细阐述了怎样合理地分配文件在磁盘中的存储位置以产生最小的期望检索时间,并给出了相应的贪心算法描述程序。 相似文献
19.
对于每个用户配置4根天线的X信道,提出了一种改进的干扰消除方法.每个用户采用速率为2的空时分组码,通过在每个用户的发送信号中引入零元素,消除了接收端的非期望接收码字;通过对空时码字进行预编码使得每个接收端的期望接收码字正交传输,从而消除了期望接收码字间的干扰.与相同场景中的已有方案相比,所提方案在保持相同传输效率的同时,极大地减少了反馈量.仿真结果验证了所提方案的有效性. 相似文献
20.
We consider the optimal control problem for the load of several communication channels defined by independent Markov jump processes. Implicit information on the state of a channel is available in the form of a flow of losses whose intensity is proportional to the controllable load of this channel. The optimized functionals take into account the total throughput of channels and energy costs for data transmission over a fixed interval of time. We obtain optimal filtering equations for joint estimation of channel states. We construct a locally optimal strategy that explicitly depends on the set of state estimates. 相似文献