Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it but unknow...
详细信息
Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence, we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents. As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: team size, in which every agent has to find the total number of agents;leader election, in which all agents have to output the label of a single agent;perfect renaming, in which all agents have to adopt new and different labels from the set {1, ... , k}, where k is the number of agents;and gossiping, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm, we solve all of these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents.
In communication networks such as social networks, wireless networks and biology networks, it is of importance to find all cliques which can help understand the network topology. The clique structures can also be util...
详细信息
ISBN:
(纸本)9781509003297
In communication networks such as social networks, wireless networks and biology networks, it is of importance to find all cliques which can help understand the network topology. The clique structures can also be utilized in facilitating message forwarding in wireless networks. For instance, using a set of cliques of maximal and disjoint, one of the nodes in each clique can be elected to forward messages, by which the duplicate message transmissions can be efficiently reduced. Further, it is well known that the maximum clique problem (MCP) is closely related to the maximum independent set and the vertex cover problems. In recent years, the fundamental problem of finding maximal cliques or maximum cliques has attracted lots of attentions. However, few of these works focus on distributed solutions in wireless networks. In this paper, we pay our attention to this missing corner of research. Specifically, we first give a distributed algorithm which can compute all maximal cliques in a wireless network represented by a graph. The algorithm takes O(n) time and uses O(mn) messages, where n is the number of nodes and m the number of edges. Then, with the proposed algorithms MCP (maximum clique problem) and UMCP (unique MCP), we show that a unique maximum clique can be selected from all maximal cliques in O(n) rounds and using O(mn) messages. To the best of our knowledge, our algorithms are the first deterministic distributed solutions for MCP in wireless networks.
We consider the following problem： for a collection of points in an n-dimensional space, find a linear projection mapping the points to the ground field such that different points are mapped to different values. Such...
详细信息
We consider the following problem： for a collection of points in an n-dimensional space, find a linear projection mapping the points to the ground field such that different points are mapped to different values. Such projections are called normal and are useful for making algebraic varieties into normal positions. The points may be given explicitly or implicitly and the coefficients of the projection come from a subset S of the ground field. If the subset S is small, this problem may be hard. This paper deals with relatively large S, a deterministic algorithm is given when the points are given explicitly, and a lower bound for success probability is given for a probabilistic algorithm from in the literature.
The basic theories of load forecasting on the power system are summarized. Fractal theory, which is a new algorithm applied to load forecasting, is introduced. Based on the fractal dimension and fractal interpolation ...
详细信息
The basic theories of load forecasting on the power system are summarized. Fractal theory, which is a new algorithm applied to load forecasting, is introduced. Based on the fractal dimension and fractal interpolation function theories, the correlation algorithms are applied to the model of short-term load forecasting. According to the process of load forecasting, the steps of every process are designed, including load data preprocessing, similar day selecting, short-term load forecasting, and load curve drawing. The attractor is obtained using an improved deterministic algorithm based on the fractal interpolation function, a day's load is predicted by three days' historical loads, the maximum relative error is within 3.7%, and the average relative error is within 1.6%. The experimental result shows the accuracy of this prediction method, which has a certain application reference value in the field of short-term load prediction.
Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic al...
详细信息
ISBN:
(纸本)9781450329446
Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set {1,...,L}, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Two main efficiency measures of a rendezvous algorithm's performance are its time (the number of rounds until the meeting) and its cost (the combined number of edge traversals by both agents). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Indeed, this is a lower bound on both the time and the cost of rendezvous. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (known to both agents) and the size L of the label space. We present two natural rendezvous algorithms. algorithm Cheap has cost O(E) (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly E) and time O(EL). algorithm Fast has both time and cost O(E log L). Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any rendezvous algorithm of cost asymptotically E (i.e., of cost E+o(E)) must have time Omega(EL). On the other hand, we show that any rendezvous algorithm with time complexity O(E log L) must have cost Omega(E log L). Moreover, while our algorithms work for arbitrary connected graphs and arbitrary starting times of the agents, these lower bounds hold even in a scenario that is very favorable for poten
Asynchrony is one of the main challenges in distributed computing. Some tasks, such as distributed Byzantine consensus, are impossible in the asynchronous setting, while they can be carried out synchronously. For othe...
详细信息
Asynchrony is one of the main challenges in distributed computing. Some tasks, such as distributed Byzantine consensus, are impossible in the asynchronous setting, while they can be carried out synchronously. For other tasks, such as rendezvous in arbitrary graphs, the best known synchronous algorithm has cost much lower than the best asynchronous one. Various degrees of asynchrony and synchrony and comparisons between them in terms of feasibility of distributed tasks have been particularly intensely studied in the context of mobile agents computing. However, somewhat surprisingly, there are no results showing a provable difference of cost between the synchronous and asynchronous versions of a task executed by mobile agents. The aim of this paper is to fill up this gap. We show for the first time that for some natural task executed by mobile agents in a network, the optimal cost of its deterministic solution in the asynchronous setting has higher order of magnitude than that in the synchronous scenario. The task for which we show this difference is well-studied: that of rendezvous of two agents in an infinite oriented grid. More precisely, we consider two agents with distinct integer labels starting at a distance D in the infinite oriented grid. Each agent knows D and its own label but not the label of the other agent and it does not know the position of the other agent relative to its own. Agents do not have any global system of coordinates. They have to meet in a node or inside an edge of the grid, and the cost of a rendezvous algorithm is the number of edge traversals by both agents until the meeting. We show that in the synchronous scenario rendezvous can be performed at cost O (Dl), where E is the length of the (binary representation of the) smaller label, while cost Omega(D-2 + D(l) is needed for asynchronous completion of rendezvous. Hence, for instances with l = o(D), the optimal cost of asynchronous rendezvous is asymptotically larger than that of synchrono
Two mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can ...
详细信息
ISBN:
(纸本)9783662439517
Two mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to delay faults: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability 0 < p < 1), unbounded adversarial (the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial (the adversary can delay an agent for at most c consecutive rounds, where c is unknown to the agents). The quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals. For random faults, we show an algorithm with cost polynomial in the size n of the network and polylogarithmic in the larger label L, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous is not feasible, even in the class of rings. Under this scenario we give a rendezvous algorithm with cost O(nl), where l is the smaller label, working in arbitrary trees, and we show that Omega(l) is the lower bound on rendezvous cost, even for the two-node tree. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in n, and logarithmic in the bound c and in the larger label L.
It has been known that the primes are infinite in number but the exact sequence of primes is not predictable. Prime numbers and computers have been linked since the 1950s. Computer security authorities use extremely l...
详细信息
ISBN:
(纸本)9781479965854
It has been known that the primes are infinite in number but the exact sequence of primes is not predictable. Prime numbers and computers have been linked since the 1950s. Computer security authorities use extremely large prime numbers when they devise cryptographs, like RSA (short for Rivest, Shamir, and Adleman) algorithm, for protecting vital information that is transmitted between computers. There are many primality testing algorithms including mathematical models and computer programs. However, they are very time and energy consuming when the given number n is very large. In this paper, we propose a Compute Unified Device Architecture (CUDA)-accelerated deterministic algorithm to determine whether an input number is prime or composite much faster to save energy. We develop and implement the proposed algorithm using a system with an 8-core CPU and a 448-core GPu. Experimental results indicate that up to 45x speedup and 88% energy saving can be achieved for 20-digit decimal numbers.
This paper deals with the development of methodology suited for design of computation algorithm which is able to determine power losses of electronic systems based on measured temperature distribution. Second part of ...
详细信息
ISBN:
(纸本)9788026102762
This paper deals with the development of methodology suited for design of computation algorithm which is able to determine power losses of electronic systems based on measured temperature distribution. Second part of paper is given to development of methodology for optimal selection of mentioned active components for thermal simulation model of given electronic system. Finally experimental verification of proposed methodology is presented.
A team consisting of an unknown number of mobile agents starting from different nodes of an unknown network, possibly at different times, have to explore the network: Every node must be visited by at least one agent, ...
详细信息
A team consisting of an unknown number of mobile agents starting from different nodes of an unknown network, possibly at different times, have to explore the network: Every node must be visited by at least one agent, and all agents must eventually stop. Agents are anonymous (identical), execute the same deterministic algorithm, and move in synchronous rounds along links of the network. They are silent: They cannot send any messages to other agents or mark visited nodes in any way. In the absence of any additional information, exploration with termination of an arbitrary network in this model, devoid of any means of communication between agents, is impossible. Our aim is to solve the exploration problem by giving to agents very restricted local traffic reports. Specifically, an agent that is at a node nu in a given round is provided with three bits of information answering the following questions: Am I alone at nu? Did any agent enter nu in this round? Did any agent exit v in this round? We show that this small amount of information permits us to solve the exploration problem in arbitrary networks. More precisely, we give a deterministic terminating exploration algorithm working in arbitrary networks for all initial configurations that are not perfectly symmetric;that is, in which there are agents with different views of the network. The algorithm works in polynomial time in the (unknown) size of the network. A deterministic terminating exploration algorithm working for all initial configurations in arbitrary networks does not exist.
暂无评论