PaperlayerView exact revision on arXiv

Source-linked AI summary

A Scalable Framework for Wireless Distributed Computing

Songze Li, Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

arXiv:1608.05743v2cs.ITcs.DCmath.IT

TL;DR

Wireless distributed computing must exchange intermediate results over a fixed-bandwidth network as the number of users grows. This paper uses repetitive dataset placement and coding at users and the access point to reduce shuffling load. It reports minimum possible loads for centralized and large-user decentralized settings, while assuming participating users remain active and reliable throughout computation.

  • Problem

    The paper asks whether wireless distributed computing can keep communication load independent of user count despite fixed overall bandwidth as the network grows.

    Source: §I · p. 1

  • Method

    The framework uses repetitive dataset placement to create coding opportunities at users and the access point for shuffling.

    Source: §I · pp. 1–2, §VI · p. 10

  • Results

    Tight lower bounds show the CWDC schemes achieve minimum possible communication loads in the centralized setting and decentralized settings with many users.

    Source: A. Motivating Example · p. 2

  • Takeaways & Limitations

    The proposed loads do not increase with participating-user count, allowing the framework to accommodate more users without extra communication load.

    Source: §III · p. 6, §VI · p. 10

    The analysis assumes all participating users remain active and reliable from the start to the end of collaborative computation.

    Source: §VI · p. 10

Abstract

from arXiv · show

We consider a wireless distributed computing system, in which multiple mobile users, connected wirelessly through an access point, collaborate to perform a computation task. In particular, users communicate with each other via the access point to exchange their locally computed intermediate computation results, which is known as data shuffling. We propose a scalable framework for this system, in which the required communication bandwidth for data shuffling does not increase with the number of users in the network. The key idea is to utilize a particular repetitive pattern of placing the dataset (thus a particular repetitive pattern of intermediate computations), in order to provide coding opportunities at both the users and the access point, which reduce the required uplink communication bandwidth from users to access point and the downlink communication bandwidth from access point to users by factors that grow linearly with the number of users. We also demonstrate that the proposed dataset placement and coded shuffling schemes are optimal (i.e., achieve the minimum required shuffling load) for both a centralized setting and a decentralized setting, by developing tight information-theoretic lower bounds.

I. INTRODUCTION

Wireless distributed computing lets devices collaborate when their individual storage or computing resources are insufficient. Its central challenge is keeping data-shuffling communication scalable as the network grows; the paper proposes a coding-based framework to address this.

I. INTRODUCTION

  • Wireless collaboration lets devices process datasets too large for any one device to store locally, including in the smart-car navigation example.The paper also notes that such computing can reduce reliance on a cloud in settings where cloud access is limited.Source: §I · p. 1
  • Data shuffling can bottleneck scaling because network computation resources grow with the number of users while overall communication bandwidth remains fixed.The introduction cites an observation that data shuffling consumed 33% of job execution time in a Facebook Hadoop cluster.Source: §I · p. 1
  • The paper asks whether wireless distributed computing can keep required communication load fixed and independent of the number of users.Source: §I · p. 1
  • The proposed framework uses redundant user computations to create coding opportunities that reduce communication and support a scalable design.It combines side information from repeated computation, coding packets useful to multiple users, and wireless multicasting.Source: §I · pp. 1–2

A. Motivating Example

A three-user example illustrates how coded shuffling can reduce communication, motivating a general CWDC framework. The proposed design is scalable, extends to decentralized placement, and is shown optimal in specified settings.

A. Motivating Example

  • In the three-user example, each user stores four of six files and needs two more intermediate values for its input.Without coding, the example would require an uplink load of 6 and a downlink load of 6; coded shuffling achieves loads of 3 and 2, respectively.Source: A. Motivating Example · p. 2
  • The general CWDC framework covers arbitrary application types, network sizes, and storage sizes through dataset placement and joint user–access-point coding.Source: A. Motivating Example · p. 2
  • The decentralized scheme places data independently at each user and achieves communication load close to the centralized scheme, particularly with many participating users.Source: A. Motivating Example · p. 2
  • CWDC achieves minimum possible communication loads in the centralized setting and in the decentralized setting with many users, as established by tight lower bounds.Source: A. Motivating Example · p. 2
  • The proposed CWDC scheme reduces communication load versus uncoded shuffling by Θ(K) as the network expands; Fig. 2 compares loads for K=20.Source: A. Motivating Example · p. 2, Figure 2 · p. 3

B. Prior Works

This paper extends coded distributed computing from wireline links to wireless systems that communicate through an access point. It designs codes at both users and the access point, and develops an optimal decentralized placement and shuffling scheme.

B. Prior Works

  • The paper extends wireline coded distributed computing, [10] to wireless systems and develops a framework with constant communication loads.Source: B. Prior Works · p. 3
  • Unlike the wireline setting, the wireless scheme designs codes at the access point for downlink communication as well as at users for uplink communication.Source: B. Prior Works · p. 3
  • For decentralized placement, each user independently chooses its stored data, and the proposed placement and communication scheme achieves minimum loads asymptotically.Source: B. Prior Works · p. 3
  • Unlike coded caching,, the access point stores no dataset and performs no computation; the scheme designs codes at users and the access point for shuffling.Source: B. Prior Works · p. 3
  • The paper distinguishes its setting from edge-computation offloading: the access point facilitates communication, while computation remains distributed among users.Source: B. Prior Works · p. 3

II. SYSTEM MODEL

The system models users computing over a shared dataset, with an access point relaying intermediate results during shuffling. Dataset placement and coding determine the communication load between computation phases.

System model

  • Each user has an orthogonal uplink to the access point, whose downlink transmissions are received by all users.The access point is assumed not to have the dataset; it forms a broadcast message from decoded uplink messages.Source: §II · pp. 3, 5

Dataset placement

  • Each user stores a fraction µ of the dataset, with 1/K ≤ µ < 1, so no user stores it all but the users collectively can store it.The file selections, called dataset placement, are design parameters chosen before computation.Source: §II · p. 4

Computation model

  • Each user's computation is decomposed into Map functions that produce intermediate values and a Reduce function that combines them into an output.The paper imposes no constraint on the Map and Reduce functions; they may be linear or nonlinear.Source: §II · p. 4

Input assumption

  • Because input size D is much smaller than intermediate-value size T, inputs are assumed known to every user before computation.This makes the overhead of disseminating inputs negligible.Source: §II · p. 4

Computation phases

  • During shuffling, users exchange via the access point the intermediate values they did not compute locally and need for Reduce.The shuffle consists of uplink communication from users and downlink communication from the access point.Source: §II · pp. 4–5

Communication loads

  • Uplink load is the total bits sent by users divided by NT; downlink load is the access-point message size divided by NT.Here NT is the number of bits in the intermediate values required by a user.Source: §II · p. 5

III. THE PROPOSED CWDC SCHEME

The proposed CWDC scheme combines dataset placement with coded uplink and downlink shuffling in a centralized setting. Its loads remain independent of user count for large networks, and the scheme is presented as optimal for minimizing both loads.

Dataset placement

  • For centralized placement, files are grouped into batches labeled by user subsets, and each file is stored by µK users.When µK is not an integer, the scheme partitions files between placements using the floor and ceiling storage levels.Source: §III · pp. 5–6

Coded shuffling

  • For each user subset of size µK+1, users XOR segments of requested values, and the access point broadcasts random linear combinations to that subset.The combinations let users cancel locally known segments and recover their requested ones; access-point coding yields a downlink reduction factor of µK+1.Source: §III · pp. 5–6

Performance and optimality

  • For large K, CWDC communication loads are independent of K, while coding reduces uncoded uplink and downlink loads by factors µK and µK+1, respectively.The stated factors scale linearly with the number of users; the scheme is optimal in minimizing communication loads.Source: §III · p. 6

Joint design

  • The wireless scheme jointly designs uplink and downlink shuffling to minimize both communication loads.The paper contrasts this with wired distributed computing, where one data-shuffling scheme between servers is designed.Source: §III · p. 6

Coding scope

  • The proposed communication coding is in-network coding, distinct from compression, and can be applied after intermediate values are compressed.Compression reduces the information bits requested; the coded scheme then delivers those values over wireless links.Source: §III · p. 6

Scope and extension

  • The paper frames decentralized placement as a more practical extension, where files are placed before the participating users are known.The described scheme in this section is for centralized placement, designed with the number and identities of participating users known.Source: §III · pp. 5, 7

IV. THE PROPOSED CWDC SCHEME FOR THE DECENTRALIZED SETTING

The decentralized CWDC scheme uses independent random dataset placement and coded uplink/downlink shuffling. Its communication loads approach the centralized scheme’s at large user counts, while information loss vanishes.

IV. THE PROPOSED CWDC SCHEME FOR THE DECENTRALIZED SETTING

  • Each user independently stores μN files chosen uniformly at random; for large N, information loss approximately equals (1 − μ)^K and quickly converges to zero as K increases.The dataset is placed before computation, without requiring knowledge of the other participating users.Source: §IV · p. 7
  • The shuffling scheme groups files by how many users store them, then applies the centralized coded communication schemes opportunistically to each group.For any subset S, the number of files stored exclusively by its users is approximately μ^|S|(1 − μ)^(K−|S|)N for large N.Source: §IV · p. 7
  • With high probability for sufficiently large N, the scheme has information loss Δ = (1 − μ)^K and achieves the stated communication loads.The supplied theorem passage does not include the load expressions.Source: §IV · p. 7
  • For large K, decentralized and centralized communication loads are close, and both decentralized loads approach 1/μ − 1.At K = 20, the decentralized loads are higher but numerically close to the centralized loads.Source: §IV · p. 7
  • Uniform random placement concentrates files near μK storing users as K grows, matching the centralized scheme’s optimal placement and explaining the small asymptotic performance gap.Almost all files are stored by approximately μK users for large K.Source: §IV · p. 7

V. OPTIMALITY OF THE PROPOSED CWDC SCHEMES

Information-theoretic lower bounds characterize minimum communication loads in the centralized setting and bound decentralized loads when K is large and information loss vanishes. The proposed schemes attain these bounds in their stated regimes.

V. OPTIMALITY OF THE PROPOSED CWDC SCHEMES

  • The centralized lower bounds apply to any dataset placement and communication schemes, showing that optimizing uplink and downlink loads involves no fundamental tension.The proposed centralized scheme attains both minimum loads simultaneously.Source: §V · p. 8
  • The centralized scheme minimizes both uplink and downlink loads, while the decentralized scheme is asymptotically optimal for large K.For the decentralized bound, information loss must approach zero.Source: §V · pp. 8–9
  • For centralized schemes, the lower bound on minimum uplink load uses the lower convex envelope of points indexed by dataset storage fractions.A file of T bits known at j users and needed by another user requires at least T/j uplink bits from those users.Source: §V · pp. 8–9
  • The downlink lower bound is derived by enhancing the system with the access point as a K + 1th user that stores all files and broadcasts.Because this enhancement cannot increase the minimum load, its lower bound also applies to the original system.Source: §V · p. 9
  • For decentralized placement with vanishing information loss, both communication loads are lower bounded by 1/μ − 1 when K is large.The proposed decentralized scheme’s asymptotic loads coincide with this bound.Source: §V · p. 9

VI. CONCLUSIONS AND FUTURE DIRECTIONS

The framework provides scalable wireless distributed computing in centralized and decentralized settings, with shuffling load that does not grow with the number of users. Its scope leaves practical challenges and several extensions for future work.

VI. CONCLUSIONS AND FUTURE DIRECTIONS

  • The framework keeps shuffling load independent of user count in both centralized and decentralized settings through repetitive dataset placement that enables coding.The resulting reduction scales linearly with network size.Source: §VI · p. 10
  • The schemes assume similar user channel strengths and communication rates; optimal grouping for heterogeneous link capacities remains an open challenge.The discussion also identifies computation and storage at edge servers as a setting for future scheduling and communication studies.Source: §VI · p. 10
  • For heterogeneous intermediate-result sizes, coding still applies, but finding the optimal dataset placement and coding scheme remains open.The passage also describes a greedy placement approach that seeks multicast opportunities for the largest possible number of users.Source: §VI · p. 10
  • The analysis assumes all users remain active and reliable throughout computation, leaving users that disconnect, leave, or join mid-process for future consideration.Coded task assignment using MDS codes is proposed as one possible way to provide robustness to stragglers or failures.Source: §VI · p. 10
  • The schemes cover one Map-Reduce stage, while optimal schemes for applications with multiple computation stages remain an open direction.The passage describes general multi-stage applications as computations interconnected in a directed acyclic graph.Source: §VI · p. 11
Loading 1608.05743v2…