Thursday 10 September 2009

Distributed Systems - Axioms of Distributed Computing

Definition of a Distributed System


A distributed system is one in which independent, self-sufficient, often autonomous and heterogeneous, spatially separated components must use a common interconnect to exchange information in order to coordinate there actions and allow the whole to appear to its users as one single coherent system.



Axioms


An axiom is a statement that is assumed to be true, and this is used as a basis for developing a system. This post will introduce and comment on the axioms used in networks that raise fundamental issues for distributed computing.

There are 8 main axioms in distributed computing. These are:

  1. The Network is not reliable.

  2. Latency is greater than zero.

  3. Bandwidth is less than infinite.

  4. The network is not secure.

  5. Topology does change.

  6. There is more than one administrator

  7. Transport cost is greater than zero.

  8. The network is not homogeneous.


Now let’s go through each one, in more depth.




1. The network is not reliable


Even though it may seem like it, any network, no matter how big or small, is never reliable.

While the time between failures in networked components is very high, the physical fabric is far from immune from failure, real or perceived problems, such as power failures and downtimes. In the presence of security flaws (more in axiom 4), malicious actions like denial-of-service attacks can cause the network to fail.

Another unreliable feature is in the presence of inherent asynchronous and intense competition for concurrent access to resources. In this case, it is difficult to ensure reliable delivery of data (messages).

The most common type of policy to counteract failures is to reduce the caching and replication.




2. Latency is greater than zero


Latency, or lag, is the measurement of time that it takes for data to move from destination to source.

Now, with latency, you may have expected that the reduction in this has been quite rapid of the past few years… sadly, you would be wrong! Over the years, reduction has been slower than expected! To scale things here:

Latency has been reduced 10 times in 10 years, where as Bandwidth has been increased 1000 time in the same period!

This slow reduction is due to the speed of light, which, if you must know is 2.997x108m/s. The speed of light imposes as a physical upper boundary on latency. The simplest of messages takes at least 30ms for a round-trip between the US and Europe! Much higher than the typical latency between the CPU and RAM.




3. Bandwidth is less than infinite


Bandwidth is the measurement of the amount of data that can be communicated within a certain amount of time.

Whilst bandwidth is growing at a faster rate then that by which latency is decreasing, the tendency is for bandwidth to be ‘hogged’ by new kinds of appliances – such as VoIP and IPTV. As well as data - like videos.

Modern representations of data for exchange are verbose, like XML, but their use is growing at a very fast rate.

In a WAN, the rate of packet loss and the round-trip times are large enough that one is inclined to use large packet sizes, thereby ‘hogging’ the bandwidth.




4. The network is not secure


As we all know, no network is ever safe, not even the Internet. While the rate at which new viruses have been created is slowing, it can be seen that spyware is on the rise. Most online users these days have had their computers infected with spyware than viruses.




5. Topology does change


Servers and clients are always being removed and added constantly at a high turnover. The growth in the usage of wireless and mobile devices shows that the rate of change will also grow. The implication is that one should not depend on specific endpoints, and even less on pre-computed routes.  These endpoints should provide location transparency or be discoverable via the registry services.





6. There is more than one administrator


The implication here is that local and isolated decisions are routinely taken without consultation, and furthermore, this can create barriers to communication. Some examples are:

  • Unannounced downtimes,

  • Changing in the firewall,

  • Levels of security permissions,

  • Resource management policy.





7. Transport cost is greater than zero


There are 2 senses in which this holds:

  1. The trip from the application layer down to the transport layer incurs a cost in resource usage and adds to latency because it involves marshalling to get data onto the wire; this can be done by serializing information into bits.

  2. Deploying the interconnect infrastructure incurs significant costs, even if the interconnect is wired or wireless.


The implication is that one should only go through the interconnect if the benefits outweigh the costs.




8. The network is not homogeneous


Any modern, non-trivial network is heterogeneous in several respects:

  • Communication technologies, such as wireless, Bluetooth and WiFi.

  • Protocols, standard or proprietary.

  • Representations, such as ASCII and XML.


The implication here is, as before, that abstraction and interoperability are imperative.

1 comment: