Notes

Designing Distributed Systems - Google Case Study Google is a US-based internet company. Born as a research project at Stanford in 1998. Now it has a dominant share of the Internet search market. Capable of diversifying itself: cloud computing. Amazing case study from distributed systems perspective: extremely demanding requirements, particularly in terms of scalability, reliability, performance and openness.

Google Hetereogeneous Business

Overall System Architecture

• Scalability, need to scale up to Ultra-Large Scale distributed system. Google views the problem in 3D:

  • Being able to deal with more data
  • Being able to deal with more queries
  • Seeking better results (more accurate)

• Reliability, Google has stringent reliability requirements, especially with regard to availability of services. This demands both detecting failures and adopting strategies to mask or tolerate such failures. Such strategies rely heavily on the redundancy in the underlying physical architecture.

• Performance, keen on achieving low latency of user interactions.

  • The importance of performance is exemplified by the target of completing web search operations in 0.2 seconds.
  • This applies to a wide range of functions associated with the operation of Google, including web crawling, indexing and sorting.
  • Top performance requires resources to work together, including network, storage and computational resources.

• Openness, strong requirement for openness, particularly to support further development in the range of web applications on offer.

  • It is well known that Google as an organization encourages and nurtures innovation, and this is most evident in the development of new web applications.
  • This is only possible with an infrastructure that is extensible and provides support for the development of new applications.

Google Infrastructure

Hints on distributed computing: MapReduce To complement the storage and coordination services, it is also important to support high-performance distributed computation over the large datasets. This is the main goal of the paradigm MapReduce. There are three key principles:

• Break the input data into a number of chunks. (Map)
• Carry out initial processing on these chunks of data to produce intermediary results. (Map)
• Combine the intermediary results to produce the final output. (Reduce)

The Purpose of the Blockchain The metaphor: Can you remember the last time you bought a CD for yourself in a music store? Well, maybe not so much since nowadays people tend to download music or simply stream it (e.g., Spotify, Apple Music, ...). The real game changer was just a piece of software called Napster (released in 1999) which allowed to share music files among peers. "This system, what's most interesting about it is, you're interacting with peers, you're exchanging information with a person down the street". (Shawn Fanning, cofounder of Napster).

A Revolutionary Change - the Case of Music Industry The music industry has worked for a long time in the following way:

• Musicians made contracts with studios.
• The studios record the songs, produce and market them on a variety of media (e.g., vinyl, tape, or CD).
• These were sold to the customers via a variety of distribution channels, including department stores and specialized shops.
• The studios actually worked as intermediaries between musicians and people who enjoy listening to music.
• The studios could maintain their role as intermediaries due to their exclusive knowledge and skills in producing, marketing, and distributing records.
• This is true till the first decade of the 2000s.

In early 2000s, lots of things changed:

• The digitalization of music, the availability of recording equipment at affordable prices, the growing spread of privately used PCs, and the wide spread of the Internet made music studio dispensable.
• The three functions of music studios - producing, marketing, and distributing records - could be done by the artists and the consumers themselves.
• Napster played a major role in the replacement of the music studios as intermediaries.
• The P2P approach of Napster gave consumers access to a wider range of music than ever before, making the music studios far less relevant and causing them significant losses.

Say bye bye to intermediaries The idea here is simple: a P2P system has the power to completely replace the middlemen with P2P interactions. In the case of the music industry, the studios and their marketing and distribution channels that acted as the middlemen between artists and consumers have been replaced by P2P file sharing systems. The major characteristics that made the music industry so vulnerable to being replaced by P2P systems are the immaterial nature of music and the low costs of copying and transferring data.

What is the potential of a P2P system? The power of peer-to-peer systems is not restricted to the music industry. Each industry that mainly acts as a middleman between producers and customers of immaterial or digital goods and services is vulnerable to being replaced by a peer-to-peer system. An example: the financial industry.

Towards the Full Digitalization? What is it that you have in your bank account or on your credit card?

The concept of digitalization has been around for a long time. Only a small amount of actual money and assets do exist as physical entities like banknotes and coins. All the rest is in the form of immaterial information, namely bits and bytes, in the centralized information technology systems. Actors like banks are just middlemen between procedures and consumers of those bits and bytes.

Each transaction being borrowing, lending or transferring money from one account to another is the transfer of an immaterial good. This is operated by middlemen or intermediaries. The world is full of intermediaries: a simple money transfer across countries involves several intermediaries with a long processing time. Of course, this increases the transaction costs.

So why choosing a P2P system? In a P2P system, the same transfer is much simpler, way faster and would cost less. The transaction is just a transfer of bits and bytes between two nodes, respectively. Again, no middlemen required: interactions occur between contractual partners. The replacement of intermediaries is called disintermediation. Note: disintermediation is considered a serious threat to many business.

Wrapping up the concept of P2P system P2P systems are distributed software systems which consist of nodes which make their computational resources directly available to other nodes. Each node has equal rights and roles even if nodes have different resources. Each node is both a supplier and a consumer of resources. P2P systems are generally distributed, but can come in the form of a hybrid architecture.

Linking P2P system with Blockchain Remember the concept of integrity? A system behaves as intended. Purely distributed P2P systems may use blockchain to achieve and to maintain system integrity. Here is the take out:

"Blockchain is the technology used to achieve and maintain integrity in purely distributed systems".

So why all this hype about blockchain? Purely distributed P2P systems have commercial potential (e.g., think about the music industry). Purely distribute P2P systems use blockchain to achieve and maintain integrity, which is a fundamental requirement for such systems. Plus: blockchain enables the disintermediation.

Integrity is not the only word... The main purpose of the blockchain is to maintain integrity. Why maintaining integrity in distributed systems and purely distributed P2P systems in particular is such a challenge? Here comes another keyword: trust. There exists a subtle relation between integrity and trust.

The metaphor: have you ever heard the expression "herding cats"? This illustrates the challenges of herding a group of obstinate and intractable animals (hums?) that do not accept or recognize a central authority. This is what happens in purely distributed P2P systems in which individual and independent nodes have no central control or coordination.

Trust and Integrity in P2P systems We know what integrity is: a nonfunctional aspect of a system to be safe, consistent, correct and free of corruption and errors. Trust is the human belief in the reliability and truth of someone or something without a proof or a further investigation. In a Bayesian flavor, trust is given a priori and then gets updated based on the results of interactions. In a P2P system, integrity is a necessary condition to fulfill the expectations of the users and thus reinforce their trust in the system. Whenever trust is not reinforced due to a lack of integrity, users will abandon the system. How do we achieve and maintain integrity in such systems? This depends on several factors like:

• Knowledge about the number of nodes
• Knowledge about the trustworthiness of the nodes.

If both of theme are known, the chances of achieving integrity are higher. Note: running a P2P system over the Internet that is open and public is challenging because neither the number of nodes nor the trustworthiness of them are known.

Integrity Threats in P2P systems Two main categories:

• Technical failures (easy to fix, just replace the broken hardware/software).
• Deliberate attacks by malicious peers (way more complex to deal with).

There exist plenty of malicious attacks:

• Distributed Denial-of-Service (DoS): massive connections to a server making it inoperable.
• Network poisoning: injection of massive amount of useless data in the network. Also used as a fodder to DoS.
• Privacy breaches and Identity steal.

Blockchain as a problem solver When all the conditions are met, reaching integrity as well as trust and maintain them is easy. What if none of those conditions are met? What if we have to face the worst-case scenario?

The blockchain comes into play in this kind of situation. The blockchain plays a major role when we have an unknown number of peers with unknown reliability and trustworthiness. This is a well known problem in computer science called the Byzantine Generals' Problem.

Ok then, but what is a blockchain? At this point, it should be clear what is the purpose of a blockchain. Though, we still miss a formal definition of it. We can think of a blockchain in four different ways:

• As a Data Structure
• As an Algorithm
• As a Technology
• As a general term to identify purely distributed P2P systems within a common application area.

Blockchain as a Data Structure In computer science and software engineering, a data structure is a way to organize data regardless of their concrete informational content.

Blockchain refers to data put together into units called blocks. Think of these blocks much like pages in a book: they are connected to one another like a chain. In relation to a book, the words and sentences are the information to be stored. They are written on different pages instead of being written on a large spool. The pages are connected with one another via their position in the book and via the page numbers. You can determine if someone removed a page from the book by checking whether the page numbers continue without leaving out a number. The information on the pages as well as the pages within the book are ordered. The ordering is an important detail, which will be used extensively. The chaining of the data blocks in the data structure is achieved by using a very special numbering system (more on that later).

Blockchain as an Algorithm An algorithm is just a collection of information put together into a sequence which a computer can understand and execute. Instruction often involves data structures. When used as a name for an algorithm, blockchain refers to a sequence of instructions that negotiates the informational content of many blockchain-data-structures in a purely distributed peer-to-peer system.

Blockchain as a Technology and More Seeing the blockchain as a technology means to view it in the big picture. The technology involve data structures that contain information as well as the algorithms needed to make something with that information. The technology also involves cryptography and security tools. Combined together they can be used to achieve integrity and trust in a purely distributed P2P system.

Combining everything we know Let's try to come up with an intermediary definition of blockchain: "The blockchain is a purely distributed peer-to-peer system of ledgers that utilizes a software unit that consist of an algorithm, which negotiates the informational content of ordered and connected blocks of data together with cryptographic and security technologies in order to achieve and maintain its integrity". First proposed in 2008 under the pseudonym of Satoshi Nakamoto with the paper: Bitcoin: a peer-topper electronic cash system. The definition does not talk about Bitcoin or any cryptocurrency. The blockchain has a wide and diverse range of applications.