This paper presents a new distributed approach for generating all prime numbers in a given interval of integers. From Eratosthenes, who elaborated the first prime sieve (more than 2000 years ago), to the current gener...
详细信息
ISBN:
(纸本)9781538655559
This paper presents a new distributed approach for generating all prime numbers in a given interval of integers. From Eratosthenes, who elaborated the first prime sieve (more than 2000 years ago), to the current generation of parallel computers, which have permitted to reach larger bounds on the interval or to obtain previous results in a shorter time, prime numbers generation still represents an attractive domain of research and plays a central role in cryptography. We propose a fully distributed algorithm for finding all primes in the interval [2, n], based on the wheel sieve and the SMER (scheduling by Multiple edgereversal) multigraph dynamics which runs in O(n+ root(n)) computational complexity, close to the theoretical lower bound on sieve methods, that is O(n), without making use of preprocessing techniques.
Wireless Sensor Networks (WSNs) are used in a lot of applications: from smart homes to military enviromnets. In general, WSNs has severe energy restrictions - a sensor usualy has a limited batery and it’s not replace...
详细信息
Wireless Sensor Networks (WSNs) are used in a lot of applications: from smart homes to military enviromnets. In general, WSNs has severe energy restrictions - a sensor usualy has a limited batery and it’s not replaceable. Distributing the sensor in a random mander can lead to a redundancy of some areas and this is desirable to support fail of some sensors. In this work, we propose an distributed algorithm to schedule active sensors to reduce the redundancy of data obtainned by the network and prolong the network lifetime.
We consider wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of a heavy-traffic pattern. We assume some TDMA protocol provides a background of synchronized t...
详细信息
We consider wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of a heavy-traffic pattern. We assume some TDMA protocol provides a background of synchronized time slots and seek to schedule the routes' links to maximize the number of packets that get delivered to their destinations per time slot. Our approach is to construct an undirected graph G and to heuristically obtain node multicolorings for G that can be turned into efficient link schedules. In G each node represents a link to be scheduled and the edges are set up to represent every possible interference for any given set of interference assumptions. We present two multicoloring-based heuristics and study their performance through extensive simulations. One of the two heuristics is based on relaxing the notion of a node multicoloring by dynamically exploiting the availability of communication opportunities that would otherwise be wasted. We have found that, as a consequence, its performance is significantly superior to the other's. (C) 2012 Elsevier B.V. All rights reserved.
In order to increase the visibility of a target pageT, web spammers create hyperlink structures called web bubbles, or link farms. As countermeasure, special mobile agents, called web marshals, are deployed in the det...
详细信息
ISBN:
(纸本)9783642165573
In order to increase the visibility of a target pageT, web spammers create hyperlink structures called web bubbles, or link farms. As countermeasure, special mobile agents, called web marshals, are deployed in the detection and disassembling of link farms. Interestingly, the process of minimizing the number of web marshals and the number of hops needed to dismantle a web bubble is analogous to the graph decontamination problem. A novel distributed algorithm for graph decontamination, which can be used to define the behavior of web marshals, is introduced in this work. The new algorithm is asynchronous and topology independent. Moreover, it presents equal or better performance and needs smaller numbers of web marshals when compared to recent related works targeting only circulant graphs, a typical structure of link farms.
This paper introduces a novel method for the conversion of synchronous cryptographic circuits into equivalent asynchronous ones. The new method is based on ASERT (Asynchronous scheduling by edge reversal Timing), a fu...
详细信息
This paper introduces a novel method for the conversion of synchronous cryptographic circuits into equivalent asynchronous ones. The new method is based on ASERT (Asynchronous scheduling by edge reversal Timing), a fully decentralized timing signaling and synchronization algorithm. From a synthesizable HDL code, an asynchronous timing network, made from standard cells libraries, is generated in order to replace the clock tree of the target circuit. ASERT works with matched delays, local clocks or any equivalent way of determining, statically or dynamically, the operating time of each functional unit. Synchronous to asynchronous conversion of three different cryptographic circuits, including the fully synthesized netlists of AES, Reed-Solomon decoder, and RSA cipher cores, are presented.
In this article, we propose a fully distributed algorithm for finding all primes in a given interval [2..n] (or (L, R), more generally), based on the SMER - scheduling by Multiple edgereversal - multigraph dynamics. ...
详细信息
ISBN:
(纸本)0769524346
In this article, we propose a fully distributed algorithm for finding all primes in a given interval [2..n] (or (L, R), more generally), based on the SMER - scheduling by Multiple edgereversal - multigraph dynamics. Given a multigraph M of arbitrary topology, having N nodes, an SMER-driven system is defined by the number of directed edges (arcs) between any two nodes of M, and by the global period length of all "arc reversals" in M. In the domain of prime numbers generation, such a graph method shows quite elegant, and it also yields a totally new kind of distributed prime sieving algorithms of an entirely original design. The maximum number of steps required by the algorithm is at most n + root n. Although far beyond the O(n/log log n) steps required by the improved sequential "wheel sieve" algorithms, our SMER-based algorithm is fully distributed and of linear (step) complexity. The message complexity of the algorithm is at Most n Delta(N) + root n Delta(N), where Delta(N) denotes the maximum "multidegree" of the arbitrary multigraph M, and the space required per process is linear.
A graph G is used as a model for a resource sharing system, where each vertex represents a process and an edge joining two vertices means that the corresponding processes share a resource. A scheduling of G is a mappi...
详细信息
A graph G is used as a model for a resource sharing system, where each vertex represents a process and an edge joining two vertices means that the corresponding processes share a resource. A scheduling of G is a mapping f : {1, 2, 3,...} -> 2(V(G)), where f (i) consists of processes that are operating at round i. The rate of f is defined as rate(f) = lim sup(n ->infinity) Sigma(i=1)(n) vertical bar f(i)vertical bar/n vertical bar V (G)vertical bar, which is the average fraction of operating processes at each round. A scheduling is fair if adjacent vertices alternate their turns in operating. The operating rate gamma* (G) of G is the maximum rate of a fair scheduling. Fair schedulings of a graph was first studied by Barbosa and Gafni. They introduced the method of "scheduling by edge reversal" which derives a fair scheduling through an acyclic orientation. Through scheduling by edge reversal, Barbosa and Gafni related gamma* (G) to the structure of acyclic orientations of G. We point out that this relation implies that gamma*(G) is equal to the reciprocal of the circular chromatic number of G. Both circular coloring and scheduling by edge reversal have been studied extensively in the past decade. The former by graph theorists, and the latter by computer scientists. However, it seems that neither side knew the existence of the other. This paper intends to build a connection between the two sides. We show that certain open problems concerning scheduling by edge reversal are indeed solved under the language of circular coloring. In the study of fair scheduling, Barbosa and Gafni defined a variation of multiple coloring of graphs: the interleaved p-color, q-tuple colorings. We formulate the interleaved coloring as a graph homomorphism problem. In the study of circular chromatic number, Bondy and Hell defined (p, q)-colorings and also formulated it as a graph homomorphism problem. We prove that the target graph for the interleaved p-color, q-tuple coloring and the target
暂无评论