اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Capacity of Smartphone Peer-to-Peer Networks
196
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study three capacity problems in the mobile telephone model, a network abstraction that models the peer-to-peer communication capabilities implemented in most commodity smartphone operating systems. The capacity of a network expresses how much sustained throughput can be maintained for a set of communication demands, and is therefore a fundamental bound on the usefulness of a network. Because of this importance, wireless network capacity has been active area of research for the last two decades. The three capacity problems that we study differ in the structure of the communication demands. The first problem is pairwise capacity, where the demands are (source, destination) pairs. Pairwise capacity is one of the most classical definitions, as it was analyzed in the seminal paper of Gupta and Kumar on wireless network capacity. The second problem we study is broadcast capacity, in which a single source must deliver packets to all other nodes in the network. Finally, we turn our attention to all-to-all capacity, in which all nodes must deliver packets to all other nodes. In all three of these problems we characterize the optimal achievable throughput for any given network, and design algorithms which asymptotically match this performance. We also study these problems in networks generated randomly by a process introduced by Gupta and Kumar, and fully characterize their achievable throughput. Interestingly, the techniques that we develop for all-to-all capacity also allow us to design a one-shot gossip algorithm that runs within a polylogarithmic factor of optimal in every graph. This largely resolves an open question from previous work on the one-shot gossip problem in this model.
قيم البحث
اقرأ أيضاً
In this paper, we study the fundamental problem of gossip in the mobile telephone model: a recently introduced variation of the classical telephone model modified to better describe the local peer-to-peer communication services implemented in many po
pular smartphone operating systems. In more detail, the mobile telephone model differs from the classical telephone model in three ways: (1) each device can participate in at most one connection per round; (2) the network topology can undergo a parameterized rate of change; and (3) devices can advertise a parameterized number of bits about their state to their neighbors in each round before connection attempts are initiated. We begin by describing and analyzing new randomized gossip algorithms in this model under the harsh assumption of a network topology that can change completely in every round. We prove a significant time complexity gap between the case where nodes can advertise $0$ bits to their neighbors in each round, and the case where nodes can advertise $1$ bit. For the latter assumption, we present two solutions: the first depends on a shared randomness source, while the second eliminates this assumption using a pseudorandomness generator we prove to exist with a novel generalization of a classical result from the study of two-party communication complexity. We then turn our attention to the easier case where the topology graph is stable, and describe and analyze a new gossip algorithm that provides a substantial performance improvement for many parameters. We conclude by studying a relaxed version of gossip in which it is only necessary for nodes to each learn a specified fraction of the messages in the system.
Scalability and security problems of the centralized architecture models in cyberphysical systems have great potential to be solved by novel blockchain based distributed models.A decentralized energy trading system takes advantage of various sources
and effectively coordinates the energy to ensure optimal utilization of the available resources. It achieves that goal by managing physical, social and business infrastructures using technologies such as Internet of Things (IoT), cloud computing and network systems. Addressing the importance of blockchain-enabled energy trading in the context of cyberphysical systems, this article provides a thorough overview of the P2P energy trading and the utilization of blockchain to enhance the efficiency and the overall performance including the degree of decentralization, scalability and the security of the systems. Three blockchain based energy trading models have been proposed to overcome the technical challenges and market barriers for better adoption of this disruptive technology.
Volunteer Computing, sometimes called Public Resource Computing, is an emerging computational model that is very suitable for work-pooled parallel processing. As more complex grid applications make use of work flows in their design and deployment it
is reasonable to consider the impact of work flow deployment over a Volunteer Computing infrastructure. In this case, the inter work flow I/O can lead to a significant increase in I/O demands at the work pool server. A possible solution is the use of a Peer-to- Peer based parallel computing architecture to off-load this I/O demand to the workers; where the workers can fulfill some aspects of work flow coordination and I/O checking, etc. However, achieving robustness in such a large scale system is a challenging hurdle towards the decentralized execution of work flows and general parallel processes. To increase robustness, we propose and show the merits of using an adaptive checkpoint scheme that efficiently checkpoints the status of the parallel processes according to the estimation of relevant network and peer parameters. Our scheme uses statistical data observed during runtime to dynamically make checkpoint decisions in a completely de- centralized manner. The results of simulation show support for our proposed approach in terms of reduced required runtime.
The dynamic behavior of a multiagent system in which the agent size $s_{i}$ is variable it is studied along a Lotka-Volterra approach. The agent size has hereby for meaning the fraction of a given market that an agent is able to capture (market share
). A Lotka-Volterra system of equations for prey-predator problems is considered, the competition factor being related to the difference in size between the agents in a one-on-one competition. This mechanism introduces a natural self-organized dynamic competition among agents. In the competition factor, a parameter $sigma$ is introduced for scaling the intensity of agent size similarity, which varies in each iteration cycle. The fixed points of this system are analytically found and their stability analyzed for small systems (with $n=5$ agents). We have found that different scenarios are possible, from chaotic to non-chaotic motion with cluster formation as function of the $sigma$ parameter and depending on the initial conditions imposed to the system. The present contribution aim is to show how a realistic though minimalist nonlinear dynamics model can be used to describe market competition (companies, brokers, decision makers) among other opinion maker communities.
Random hashing is a standard method to balance loads among nodes in Peer-to-Peer networks. However, hashing destroys locality properties of object keys, the critical properties to many applications, more specifically, those that require range searchi
ng. To preserve a key order while keeping loads balanced, Ganesan, Bawa and Garcia-Molina proposed a load-balancing algorithm that supports both object insertion and deletion that guarantees a ratio of 4.237 between the maximum and minimum loads among nodes in the network using constant amortized costs. However, their algorithm is not straightforward to implement in real networks because it is recursive. Their algorithm mostly uses local operations with global max-min load information. In this work, we present a simple non-recursive algorithm using essentially the same primitive operations as in Ganesan {em et al.}s work. We prove that for insertion and deletion, our algorithm guarantees a constant max-min load ratio of 7.464 with constant amortized costs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
