A SCALABLE FRAMEWORK FOR WIRELESSDISTRIBUTED COMPUTING
ABSTRACT
We consider a wireless distributed computing system,in which multiple mobile users, connected wirelessly throughan access point, collaborate to perform a computation task.In particular, users communicate with each other via the accesspoint to exchange their locally computed intermediate computationresults, which is known as data shuffling.Weproposea scalable framework for this system, in which the requiredcommunication bandwidth for data shuffling does not increasewith the number of users in the network. The key idea is toutilize a particular repetitive pattern of placing the data set (thusa particular repetitive pattern of intermediate computations),in order to provide the coding opportunities at both the usersand the access point, which reduce the required uplink communicationbandwidth from users to the access point and thedownlink communication bandwidth from access point to usersby factors that grow linearly with the number of users. We alsodemonstrate that the proposed data set placement and codedshuffling schemes are optimal (i.e., achieve the minimum requiredshuffling load) for both a centralized setting and a decentralizedsetting, by developing tight information-theoretic lower bounds
EXISTING SYSTEM:
Let’s first illustrate our scalable design of wireless distributedcomputing through an example. Consider a scenariowhere 3 mobile users want to run an application (e.g., imagerecognition). Each user has an input (e.g., an image) toprocess using a dataset (e.g., a feature repository of objects)provided by the application. However, the local memory ofan individual user is too small to store the entire dataset,and they have to collaboratively perform the computation. Theentire dataset consists of 6 equally-sized files, and each usercan store at most 4 of them. The computation is performeddistributedly following a commonly used MapReduce-likedistributed computing structure (see e.g., MapReduce andSpark). More specifically, every user computes a Mapfunction, for each of the 3 inputs and each of the 4 filesstored locally, generating 12 intermediate values. Then theusers communicate with each other via an access point they allwirelessly connect to, which we call data shuffling.Afterthedata shuffling, each user knows the intermediate values of hisown input in all 6 files, and passes them to a Reduce functionto calculate the final output result.During data shuffling, since each user already has 4 outof 6 intended intermediate values locally, she would need theremaining 2 from the other users. Thus, one would expect acommunication load of 6 (in number of intermediate values)on the uplink from users to the access point and 6 on the downlinkin which the access point simply forwards the intermediatevalues to the intended users. However, we can take advantageof the opportunities mentioned above to significantly reducethe communication loads.
PROPOSED SYSTEM:
Our main contribution is to provide an affirmative answerto this question by developing a framework for wirelessdistributed computing that utilizes redundant computations atthe users, in order to create coding opportunities that reducethe required communication, achieving a scalable design. Thedeveloped framework can be considered as an extension of ourpreviously proposed coded distributed computing frameworkfor a wireline setting in, into the wireless distributedcomputing domain. To develop such a framework, we exploitthree opportunities in conjunction:1) Side-Information: When a sub-task has been processedin more than one node, the resulting intermediateoutcomes will be available in all those nodes asside-information. This provides some opportunities forcoding across the results and creates packets that areuseful for multiple nodes.2) Coding: We use coding to develop packets useful tomore than one mobile users. This allows us to exploitthe multicasting environment of the wireless mediumand save communication overhead.3) Multicasting: Wireless medium by nature is a multicastingenvironment. It means that when a signal istransmitted, it can be heard by all the nodes. We exploitthis phenomenon by creating and transmitting signalsthat help several user nodes simultaneously.
CONCLUSIONS AND FUTURE DIRECTIONS
In this paper, we proposed a scalable wireless distributedcomputing framework, for both the centralized and the decentralizedsettings, such that the shuffling load does not increasewith the number of participating users. In particular, we use arepetitive placement of the dataset across the users to enablecoding, reducing the shuffling load by a factor that scaleslinearly with the network size.In this paper, we have abstracted out several practical challengesto demonstrate the theoretical feasibility of a scalablewireless distributed computing framework and quantify theresulting gains. Future directions can be to generalize themodel to also incorporate the following important aspects.• Network Heterogeneity. Most mobile networks are het-erogeneous. Different mobile devices have different linkquality, processing power, battery capacity, and QoSrequirement. For example, the proposed coded computingschemes are for a set of mobile users with similaruplink/downlink channel strengths and communicationrates. When users have heterogeneous link capacities,one straightforward solution is to first partition the usersinto groups, such that all users within a group havesimilar channel strength, and then apply the proposedschemes within each group. However, designing theoptimal grouping strategy is a challenging problem thatrequires further exploration. Other than performing thecomputations at the users themselves, the superior computationand storage capacity of a growing number ofedge servers at access points encourage computationoffloading to the edge servers. Another interesting problemis to consider a mobile network of heterogeneoususers with the possibility of performing computations atthe edge servers, and study the optimal scheduling andcommunication schemes .• Computation Heterogeneity. In many wireless distributedcomputing applications (especially for graph processing),the intermediate computation results have heterogeneoussizes. For example, for a navigation application over ahighly clustered map, some parts of the map generatemuch more useful information than the other parts,resulting in highly skewed intermediate results. In suchscenario, the proposed coding scheme still applies, butthe coding operations are not symmetric as in the caseof homogeneous intermediate results (e.g., one may nowneed to compute the XOR of two data segments withdifferent sizes). Alternatively, we can consider a lowcomplexitygreedy approach, in which we perform thedataset placement to maximize the number of multicastingopportunities that simultaneously deliver usefulinformation to the largest possible number of users.Nevertheless, finding the optimal dataset placement andcoding scheme in the case of heterogeneous computationresults remains a challenging open problem.
REFERENCES
[1] S.Li,Q.Yu,M.A.Maddah-Ali,andA.S.Avestimehr,“Posterabstract:A scalable coded computing framework for edge-facilitated wirelessdistributed computing,” in Proc. IEEE/ACM Symp. Edge Comput. (SEC),Oct. 2016, pp. 79–80.
[2] S. Li, Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Edge-facilitatedwireless distributed computing,” in Proc. IEEE GLOBECOM, Dec. 2016,pp. 1–7.
[3] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, “Fog computing and itsrole in the Internet of Things,” in Proc. 1st Ed. MCC Workshop MobileCloud Comput., 2012, pp. 13–16.
[4] U. Drolia et al., “The case for mobile edge-clouds,” in Proc. IEEE 10thInt. Conf. Ubiquitous Intell. Comput. (UIC), Dec. 2013, pp. 209–215.
[5] D. Datla et al., “Wireless distributed computing: A survey of researchchallenges,” IEEE Commun. Mag., vol. 50, no. 1, pp. 144–152,Jan. 2012.
[6] G. Huerta-Canepa and D. Lee, “A virtual cloud computing provider formobile devices,” in Proc. 1st ACM Workshop Mobile Cloud Comput.Services Soc. Netw. Beyond, 2010, Art. no. 1.
[7] M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica, “Managingdata transfers in computer clusters with orchestra,” ACM SIGCOMMComput. Commun. Rev., vol. 41, no. 4, pp. 98–109, Aug. 2011.
[8] S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “Coded MapReduce,”in Proc. 53rd Allerton Conf., Sep. 2015, pp. 964–971.
[9] S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “Fundamental tradeoffbetween computation and communication in distributed computing,” inProc. IEEE ISIT, Jul. 2016, pp. 1814–1818.
[10] S. Li, M. A. Maddah-Ali, Q. Yu, and A. S. Avestimehr. (Apr. 2016).“A fundamental tradeoff between computation and communicationin distributed computing.” [Online]. Available: https://arxiv.org/abs/1604.07086