Biblio

Since the number of processors and cores on a single chip is increasing, the interconnection among them becomes significant. Network-on-Chip (NoC) has direct access to all resources and information within a System-on-Chip (SoC), rendering it appealing to attackers. Malicious attacks targeting NoC are a major cause of performance depletion and they can cause arbitrary behavior of links or routers, that is, Byzantine faults. Byzantine faults have been thoroughly investigated in the context of Distributed systems however not in Very Large Scale Integration (VLSI) systems. Hence, in this paper we propose a novel fault model followed by the design and implementation of lightweight algorithms, based on Software Defined Network-on-Chip (SDNoC) architecture. The proposed algorithms can be used to build highly available NoCs and can tolerate Byzantine faults. Additionally, a set of different scenarios has been simulated and the results demonstrate that by using the proposed algorithms the packet loss decreases between 65% and 76% under Transpose traffic, 67% and 77% under BitReverse and 55% and 66% under Uniform traffic.

Shared register emulations on top of message-passing systems provide an illusion of a simpler shared memory system which can make the task of a system designer easier. Numerous shared register applications have a considerably high read-to-write ratio. Thus, having algorithms that make reads more efficient than writes is a fair trade-off.Typically, such algorithms for reads and writes are asymmetric and sacrifice the stringent consistency condition atomicity, as it is impossible to have fast reads for multi-writer atomicity. Safety is a consistency condition that has has gathered interest from both the systems and theory community as it is weaker than atomicity yet provides strong enough guarantees like "strong consistency" or read-my-write consistency. One requirement that is assumed by many researchers is that of the reliable broadcast (RB) primitive, which ensures the "all or none" property during a broadcast. One drawback is that such a primitive takes 1.5 rounds to complete and requires server-to-server communication.This paper implements an efficient multi-writer multi-reader safe register without using a reliable broadcast primitive. Moreover, we provide fast reads or one-shot reads – our read operations can be completed in one round of client-to-server communication. Of course, this comes with the price of requiring more servers when compared to prior solutions assuming reliable broadcast. However, we show that this increased number of servers is indeed necessary as we prove a tight bound on the number of servers required to implement Byzantine-fault tolerant safe registers in a system without reliable broadcast.We extend our results to data stored using erasure coding as well. We present an emulation of single-writer multi-reader safe register based on MDS codes. The usage of MDS codes reduces storage and communication costs. On the negative side, we also show that to use MDS codes and at the same time achieve one-shot reads, we need even more servers.

This paper addresses the problem of distributed multi-agent optimization in which each agent i has a local cost function hi(x), and the goal is to optimize a global cost function that aggregates the local cost functions. Such optimization problems are of interest in many contexts, including distributed machine learning, distributed resource allocation, and distributed robotics. We consider the distributed optimization problem in the presence of faulty agents. We focus primarily on Byzantine failures, but also briey discuss some results for crash failures. For the Byzantine fault-tolerant optimization problem, the ideal goal is to optimize the average of local cost functions of the non-faulty agents. However, this goal also cannot be achieved. Therefore, we consider a relaxed version of the fault-tolerant optimization problem. The goal for the relaxed problem is to generate an output that is an optimum of a global cost function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, there must exist weights αi for i∈N such that αi ≥ 0 and ∑i≥ Nαi=1, and the output is an optimum of the cost function ∑i≥ N αihi(x). Ideally, we would like αi=1/textbarNtextbar for all i≥ N, however, this cannot be guaranteed due to the presence of faulty agents. In fact, the maximum number of nonzero weights (αi's) that can be guaranteed is textbarNtextbar-f, where f is the maximum number of Byzantine faulty agents. We present an iterative distributed algorithm that achieves optimal fault-tolerance. Specifically, it ensures that at least textbarNtextbar-f agents have weights that are bounded away from 0 (in particular, lower bounded by 1/2textbarNtextbar-f\vphantom\\). The proposed distributed algorithm has a simple iterative structure, with each agent maintaining only a small amount of local state. We show that the iterative algorithm ensures two properties as time goes to ∞: consensus (i.e., output of non-faulty agents becomes identical in the time limit), and optimality (in the sense that the output is the optimum of a suitably defined global cost function).