We study the distributed complexity of computing a maximal independent set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism available. Specifically, ...
详细信息
ISBN:
(纸本)9781581139945
We study the distributed complexity of computing a maximal independent set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism available. Specifically, we propose a novel randomized algorithm that computes a MIS in time O(log2n) with high probability, where n is the number of nodes in the network. This significantly improving on the best previously known solutions. A lower bound of Ω(log2n/log log n) given in [11] implies that our algorithm's running time is close to optimal. Our result shows that the harsh radio network model imposes merely an additional O(log n) factor compared to Luby's MIS algorithm in the message passing model. This has important implications in the context of ad hoc and sensor networks whose characteristics are closely captured by the radio network model. Copyright 2005 ACM maximal independent sets, radio network,.
In this paper, we study bounds for the α-approximate effectiveness of non-decreasing (μ + λ)-archiving algorithms that optimize the hypervolume. A (μ + λ)-archiving algorithm defines how μ individuals are to be ...
详细信息
We study the problem of exploring all nodes of an unknown directed graph. A searcher has to construct a tour that visits all nodes, but only has information about the parts of the graph it already visited. The goal is...
详细信息
In this paper we study the NP-complete problem of finding small fc-dominating sets in general graphs, which allow κ - 1 nodes to fail and still dominate the graph. The classic minimum dominating set problem is a spec...
详细信息
Recently, a number of frameworks were proposed to extend interface theory to the domains of single-processor and distributed real-time systems. This paper unifies some of these approaches and proves properties like re...
详细信息
ISBN:
(纸本)1595935428
Recently, a number of frameworks were proposed to extend interface theory to the domains of single-processor and distributed real-time systems. This paper unifies some of these approaches and proves properties like refinement and independent implementability. We also explicitly state the requirements to a framework for these properties to be fulfilled. Further, a new notion of adaptive interfaces is introduced that supports the design by providing mechanisms for propagating system constraints, such as (end-to-end) delays, available computing and communication resources, buffer spaces, and energy. Guarantees and assumptions on interfaces are not any longer static but adapt according to the system environment. This can be used to answer synthesis questions at design time or to adapt system parameters to changing environment requirements at run-time. The applicability of the presented framework is proven by adapting it to a number of different real-time analysis models. Copyright 2006 ACM.
In this paper we look at the difficulty of fixing solutions of classic network problems. We study local changes in graphs (edge resp. node insertion resp. deletion), and network problems (e.g. maximal independent set,...
详细信息
The reduced feature size of electronic systems and the demand for high performance lead to increased power densities and high chip temperatures, which in turn reduce the system reliability. Thermal-aware task allocati...
详细信息
Community related applications such as dating platforms, instant messengers, or file-sharing tools enjoy a great popularity in the Internet. Motivated by this success, community-awareness also has become a hot topic i...
Running each application of a many-core system on an isolated (virtual) guest machine is a widely considered solution for performance and reliability issues. When a new application is started, the guest machine is ass...
详细信息
Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish b...
详细信息
ISBN:
(纸本)1595933840
Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimixe the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. By giving tight hounds on the price of anarchy, we show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. Finally, we establish the complexity of Nash equilibria in our game theoretic model of P2P networks. Specifically, we prove thai it is NP-hard to decide whether our game has a Nash equilibrium and can stabilize. Copyright 2006 ACM.
暂无评论