Task offloading in fog computing has emerged as a pivotal solution to address the computational constraints of IoT devices, particularly for delay-sensitive applications. This paper introduces a distributed algorithm ...
详细信息
Task offloading in fog computing has emerged as a pivotal solution to address the computational constraints of IoT devices, particularly for delay-sensitive applications. This paper introduces a distributed algorithm for Maximum Utility Task Offloading, where the utility is defined as the inverse of the service delay. Unlike existing centralized approaches, our method leverages a decentralized framework, enabling user devices and access points to collaboratively optimize task assignments without reliance on a central authority. The problem is modelled as a maximum-weight matching problem on bipartite graphs, and we present a deterministic distributed algorithm with a (1/3-epsilon)-approximation ratio for any epsilon>0 under the CONGEST model of computation in O(1/epsilon log(2) (Delta/epsilon)log(1+root epsilon) (1/D))-round, where Delta is the maximum degree of the network graph and D is the minimum service delay in the network. Our approach scales efficiently as it is independent of the network size and adapts to the dynamic nature of IoT environments, incorporating realistic constraints such as communication delays and heterogeneous resource availability. Extensive simulations validate the efficacy of the proposed algorithm across diverse scenarios, including varying workload distributions and network densities. Results demonstrate comparable performance with respect to centralized greedy approaches, while providing substantial benefits in terms of scalability and adaptability.
This article deals with the issue of guaranteeing properties in distributed Virtual Environments (DVEs) without a server. This issue is particularly relevant in the case of online games, that operate in a fully distri...
详细信息
ISBN:
(纸本)9783030576752;9783030576745
This article deals with the issue of guaranteeing properties in distributed Virtual Environments (DVEs) without a server. This issue is particularly relevant in the case of online games, that operate in a fully distributed framework and for which network resources such as bandwidth are the critical resources. Players typically need to know the distance between their character and other characters, at least approximately. They all share the same position estimation algorithm but, in general, do not know the current positions of others. We provide a synchronized distributed algorithm A(lc) to guarantee, at any time, that the estimated distance d(est) between any pair of characters A and B is always a 1 + epsilon approximation of the current distance d(act), regardless of movement pattern, and then prove that if characters move randomly on a d-dimensional grid, or follow a random continuous movement on up to three dimensions, the number of messages of Ate is optimal up to a constant factor. In a more practical setting, we also show that the number of messages of A(lc) for actual game traces is much less than the standard algorithm sending actual positions at a given frequency.
We consider distributedalgorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximationdistributed algorithm for maximum weighted matching, whose running tim...
详细信息
We consider distributedalgorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximationdistributed algorithm for maximum weighted matching, whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. This is, to the best of our knowledge, the first log-time distributed algorithm that achieves constant approximation for maximum weighted matching on general graphs. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give a distributed algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion for any constant epsilon > 0. For weighted dynamic graphs we give a constant-factor approximationdistributed algorithm that runs in constant time for each insertion or deletion.
This paper considers the problem of calculating dominating sets in bounded degree networks. In these networks, the maximal degree of any node is bounded by delta, which is usually significantly smaller than n, the tot...
详细信息
ISBN:
(纸本)9781605588889
This paper considers the problem of calculating dominating sets in bounded degree networks. In these networks, the maximal degree of any node is bounded by delta, which is usually significantly smaller than n, the total number of nodes in the system. Such networks arise in various settings of wireless and peer-to-peer communication. A trivial approach of choosing all nodes into the dominating set yields an algorithm with an approximation ratio of delta + 1. We show that any deterministic algorithm with a non-trivial approximation ratio requires Omega(log* n) rounds, meaning effectively that no local o(delta)-approximation deterministic algorithm may ever exist. On the positive side, we show two deterministic algorithms that achieve logo and 2 log delta-approximation in O(delta(3) +log* n) and O(delta(2) log delta + log* n) time, respectively. These algorithms rely on coloring rather than node IDs to break symmetry.
We consider distributedalgorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximationdistributed algorithm for weighted maximum matching;whose running time...
详细信息
ISBN:
(纸本)9781595936165
We consider distributedalgorithms for approximate maximum matching on general graphs. Our main result is a randomized (4 + epsilon)-approximationdistributed algorithm for weighted maximum matching;whose running time is O(log n) for any constant epsilon > 0, where n is the number of nodes in the graph. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give an algorithm that maintains a (1 + epsilon)-approximation in O(1/epsilon) time for each node insertion or deletion. For weighted dynamic graphs we give a constant-factor approximation algorithm that runs in constant time for each insertion or deletion.
暂无评论