Algorithms for interactive, distributed and networked systems

Bojja Venkatakrishnan, Shaileshh

Permalink

https://hdl.handle.net/2142/98367 Copy

Description

Title

Algorithms for interactive, distributed and networked systems

Author(s)

Bojja Venkatakrishnan, Shaileshh

Issue Date

2017-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Viswanath, Pramod

Doctoral Committee Chair(s)

Viswanath, Pramod

Committee Member(s)

• Hajek, Bruce
• Srikant, R.
• Alizadeh, Mohammad

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Network algorithms
• Interactive communication
• Communication complexity
• Protocol compression
• Scheduling
• Circuit switch
• Data center networks
• Submodularity
• Peer-to-peer
• Streaming
• Topology
• Bitcoin
• Anonymity
• Distributed algorithms
• Cryptocurrency

Abstract

In recent years, massive growth in internet usage has spurred the emergence of complex large-scale networking systems to serve growing user bases, bandwidth and computation requirements. For example, data center facilities -- workhorses of today's internet -- have evolved to house upward of several hundreds of thousands of servers; content distribution networks with high capacity and wide coverage have emerged as a de facto content dissemination modality, and peer-to-peer applications with hundreds of thousands of users are increasingly becoming popular. At these scales, it becomes critical to operate at high efficiencies as the price of idling resources can be significant. In particular, the interaction between agents (servers, peers etc.) is a defining factor of efficiency in these systems -- applications are often communication intensive, whereas agents share links of only limited bandwidth. This necessitates the use of principled algorithms, as efficient communication to a large extent depends on the interaction protocols. We study data center networks and peer-to-peer networks as canonical examples of modern-day large-scale networking systems. Server-to-server interaction is an integral part of the data center's operation. The latency of these interactions is often a significant bottleneck toward overall job completion times. We study complementary approaches toward reducing this latency: (i) design of computation algorithms that minimize interaction and (ii) optimal scheduling algorithms to maximally utilize the network fabric. We also consider peer-to-peer networks as an emerging mode of content distribution and sharing. Unlike data centers, these networks are flexible in their network structure and also scale well, but require decentralized algorithms for control. Of central importance here is the design of a network topology that enables efficient peer interactions for optimal application performance. We propose novel topology designs for two popular applications: (i) multimedia streaming and (ii) anonymity in Bitcoin's peer-to-peer network.

Graduation Semester

2017-08

Type of Resource

text

Permalink

http://hdl.handle.net/2142/98367

Copyright and License Information

Copyright 2017 Shaileshh Bojja Venkatakrishnan

Owning Collections