Lewis Tseng

Nitin H. Vaidya, Lewis Tseng

We consider the problem of reaching consensus in communication networks that are modeled by directed graphs. We assume the existence of a message authentication mechanism (such as digital signatures) to verify the integrity of messages. We identify the necessary and sufficient conditions on the directed communication graph for the following problems to be solvable: (i) exact consensus in synchronous systems; and (ii) approximate consensus in asynchronous systems.

Qinzi Zhang, Lewis Tseng

In this paper, we focus on a popular DML framework -- the parameter server computation paradigm and iterative learning algorithms that proceed in rounds. We aim to reduce the communication complexity of Byzantine-tolerant DML algorithms in the single-hop radio network. Inspired by the CGC filter developed by Gupta and Vaidya, PODC 2020, we propose a gradient descent-based algorithm, Echo-CGC. Our main novelty is a mechanism to utilize the broadcast properties of the radio network to avoid transmitting the raw gradients (full $d$-dimensional vectors). In the radio network, each worker is able to overhear previous gradients that were transmitted to the parameter server. Roughly speaking, in Echo-CGC, if a worker "agrees" with a combination of prior gradients, it will broadcast the "echo message" instead of the its raw local gradient. The echo message contains a vector of coefficients (of size at most $n$) and the ratio of the magnitude between two gradients (a float). In comparison, the traditional approaches need to send $n$ local gradients in each round, where each gradient is typically a vector in an ultra-high dimensional space ($d\gg n$). The improvement on communication complexity of our algorithm depends on multiple factors, including number of nodes, number of faulty workers in an execution, and the cost function. We numerically analyze the improvement, and show that with a large number of nodes, Echo-CGC reduces $80\%$ of the communication under standard assumptions.

Ouns Bouachir, Moayad Aloqaily, Lewis Tseng et al.

Blockchain has revolutionized how transactions are conducted by ensuring secure and auditable peer-to-peer coordination. This is due to both the development of decentralization, and the promotion of trust among peers. Blockchain and fog computing are currently being evaluated as potential support for software and a wide spectrum of applications, ranging from banking practices and digital transactions to cyber-physical systems. These systems are designed to work in highly complex, sometimes even adversarial, environments, and to synchronize heterogeneous machines and manufacturing facilities in cyber computational space, and address critical challenges such as computational complexity, security, trust, and data management. Coupling blockchain with fog computing technologies has the potential to identify and overcome these issues. Thus, this paper presents the knowledge of blockchain and fog computing required to improve cyber-physical systems in terms of quality-of-service, data storage, computing and security.