Songze Li

Prof. Songze Li

1. Thrust of Internet of Things, The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China
+1

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 September 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
SLSongze Li
Songze Li
MMMohammad Ali Maddah-Ali
Mohammad Ali Maddah-Ali
QYQian Yu
Qian Yu
AAA. Salman Avestimehr
A. Salman Avestimehr
How can we optimally trade extra computing power to reduce the communication load in distributed computing? We answer this question by characterizing a fundamental tradeoff between computation and communication in distributed computing, i.e., the two are inversely proportional to each other. More specifically, a general distributed computing framework, motivated by commonly used structures like MapReduce, is considered, where the overall computation is decomposed into computing a set of “Map” and “Reduce” functions distributedly across multiple computing nodes. A coded scheme, named “coded distributed computing” (CDC), is proposed to demonstrate that increasing the computation load of the Map functions by a factor of r (i.e., evaluating each function at r carefully chosen nodes) can create novel coding opportunities that reduce the communication load by the same factor. An information-theoretic lower bound on the communication load is also provided, which matches the communication load achieved by the CDC scheme. As a result, the optimal computation-communication tradeoff in distributed computing is exactly characterized. Finally, the coding techniques of CDC is applied to the Hadoop TeraSort benchmark to develop a novel CodedTeraSort algorithm, which is empirically demonstrated to speed up the overall job execution by 1.97× -3.39×, for typical settings of interest.

29 May 2017 in IEEE/ACM Transactions on Networking
Verified
Journal Article
Open access
SLSongze Li
Songze Li
QYQian Yu
Qian Yu
MMMohammad Ali Maddah-Ali
Mohammad Ali Maddah-Ali
AAA. Salman Avestimehr
A. Salman Avestimehr
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 data set (thus a particular repetitive pattern of intermediate computations), in order to provide the coding opportunities at both the users and the access point, which reduce the required uplink communication bandwidth from users to the 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 data set 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.

14 April 2017 in IEEE Communications Magazine
Verified
Journal Article
Closed access
SLSongze Li
Songze Li
MMMohammad Ali Maddah-Ali
Mohammad Ali Maddah-Ali
AAA. Salman Avestimehr
A. Salman Avestimehr
Redundancy is abundant in fog networks (i.e., many computing and storage points) and grows linearly with network size. We demonstrate the transformational role of coding in fog computing for leveraging such redundancy to substantially reduce the bandwidth consumption and latency of computing. In particular, we discuss two recently proposed coding concepts, minimum bandwidth codes and minimum latency codes, and illustrate their impacts on fog computing. We also review a unified coding framework that includes the above two coding techniques as special cases, and enables a trade-off between computation latency and communication load to optimize system performance. At the end, we will discuss several open problems and future research directions.

15 July 2020 in IEEE Transactions on Information Forensics and Security
Verified
Journal Article
Closed access
SLSongze Li
Songze Li
MYMingchao Yu
Mingchao Yu
CYChien-Sheng Yang
Chien-Sheng Yang
AAAmir Salman Avestimehr
Amir Salman Avestimehr
SKSreeram Kannan
Sreeram Kannan
PVPramod Viswanath
Pramod Viswanath
Today's blockchain designs suffer from a trilemma claiming that no blockchain system can simultaneously achieve decentralization, security, and performance scalability. For current blockchain systems, as more nodes join the network, the efficiency of the system (computation, communication, and storage) stays constant at best. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. In this paper, we settle the trilemma by demonstrating a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: “polynomially coded sharding” scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

3 March 2023 in IEEE Journal on Selected Areas in Communications
Verified
Journal Article
Closed access
TJTayyebeh Jahani-Nezhad
Tayyebeh Jahani-Nezhad
MMMohammad Ali Maddah-Ali
Mohammad Ali Maddah-Ali
SLSongze Li
Songze Li
Giuseppe CaireGiuseppe Caire
Giuseppe Caire
We propose SwiftAgg+, a novel secure aggregation protocol for federated learning systems, where a central server aggregates local models of N ∈ N distributed users, each of size L ∈ N, trained on their local data, in a privacy-preserving manner. SwiftAgg+ can significantly reduce the communication overheads without any compromise on security, and achieve optimal communication loads within diminishing gaps. Specifically, in presence of at most D = o(N) dropout users, SwiftAgg+ achieves a per-user communication load of (1+ O (1/ N )) L symbols and a server communication load of (1+ O ( 1/ N )) L symbols, with a worst-case information-theoretic security guarantee, against any subset of up to T = o(N) semi-honest users who may also collude with the curious server. Moreover, the proposed SwiftAgg+ allows for a flexible trade-off between communication loads and the number of active communication links. In particular, for T < N – D and for any K ∈ N, SwiftAgg+ can achieve the server communication load of (1 + T/K ) L symbols, and peruser communication load of up to (1 + T + D / K ) L symbols, where the number of pair-wise active connections in the network is N /2( K + T + D + 1).

20 August 2020 in Foundations and Trends® in Communications and Information Theory
Verified
Journal Article
Closed access
PDF file
SLSongze Li
Songze Li
SASalman Avestimehr
Salman Avestimehr
We introduce the concept of “coded computing”, a novel computing paradigm that utilizes coding theory to effectively inject and leverage data/computation redundancy to mitigate several fundamental bottlenecks in large-scale distributed computing, namely communication bandwidth, straggler’s (i.e., slow or failing nodes) delay, privacy and security bottlenecks. More specifically, for MapReduce based distributed computing structures, we propose the “Coded Distributed Computing” (CDC) scheme, which injects redundant computations across the network in a structured manner, such that in-network coding opportunities are enabled to substantially slash the communication load to shuffle the intermediate computation results. We prove that CDC achieves the optimal tradeoff between computation and communication, and demonstrate its impact on a wide range of distributed computing systems from cloud-based datacenters to mobile edge/fog computing platforms. Secondly, to alleviate the straggler effect that prolongs the executions of distributed machine learning algorithms, we utilize the ideas from error correcting codes to develop “Polynomial Codes” for computing general matrix algebra, and “Lagrange Coded Computing” (LCC) for computing arbitrary multivariate polynomials. The core idea of these proposed schemes is to apply coding to create redundant data/computation scattered across the network, such that completing the overall computation task only requires a subset of the network nodes returning their local computation results. We demonstrate the optimality of Polynomial Codes and LCC in minimizing the computation latency, by proving that they require the least number of nodes to return their results. Finally, we illustrate the role of coded computing in providing security and privacy in distributed computing and machine learning. In particular, we consider the problems of secure multiparty computing (MPC) and privacy-preserving machine learning, and demonstrate how coded computing can be leveraged to provide efficient solutions to these critical problems and enable substantial improvements over the state of the art. To illustrate the impact of coded computing on real world applications and systems, we implement the proposed coding schemes on cloud-based distributed computing systems, and significantly improve the run-time performance of important benchmarks including distributed sorting, distributed training of regression models, and privacy-preserving training for image classification. Throughout this monograph, we also highlight numerous open problems and exciting research directions for future work on coded computing.