Soma-notes - User contributions [en]

DistOS 2014W Lecture 18

2014-04-24T14:41:51Z

Eapache: /* Tapestry: */

==Distributed Hash Tables (March 18)==

* [http://en.wikipedia.org/wiki/Distributed_hash_table Wikipedia's article on Distributed Hash Tables]
* [http://pdos.csail.mit.edu/~strib/docs/tapestry/tapestry_jsac03.pdf Zhao et al, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment" (JSAC 2003)]

== Distributed Hash Table Overview ==

A Distributed Hash Table (DHT) is a fast lookup structure of <key,value> pairs,
distributed across many nodes in a network. Keys are hashed to generate the
index at which the value can be found. Depending on the nature of the hash
function, typically, only exact queries may be returned.

Usually, each node has a partial view of
the hash table, as opposed to a full replica. They don't know exactly which other node is responsible for a given key. This has given rise to a number
of different routing techniques:
* A centralized server may maintain a list of all keys and associated nodes at which the value can be found. This method involves a single point of failure.
** eg. Napster
* Flooding: Each node may query all connected nodes. This method has performance and scalability shortcomings but had the benefit of being decentralized.
** eg. Gnutella
* [http://en.wikipedia.org/wiki/Consistent_hashing Consistent Hashing] The keyspace can be partitioned such that nodes will maintain the values for keys that hash to similar indices (e.g., within a certain hamming distance). Given a query, nodes do not know specifically on which node a key is located, but they do know a few nodes (a proper subset of the network) located "closer" to the key. The query then continues onto the closest node. This seems to be the most popular technique for DHTs. It's biggest benefit is that nodes can be added and removed without notifying every other node on the network.
** eg. Tapestry

==Tapestry:==
Tapestry is an overlay network which makes use of a DHT to provide routing for
distributed applications. Similar to IP routing, not all nodes need to be
directly connected to each other: they can query a subset of neighbours for
information about which nodes are responsible for certain parts of the keyspace.
Routing is performed in such a way that nodes are aware of their ''distance''
to the object being queried. Hence objects can be located with low latency
without the need to migrate actual object data between nodes.

Tapestry was built for Oceanstore. Oceanstore was built for the open internet. Nodes would be constantly added and removed. Chances are, the network topology would change. That's why you'd need a dynamic routing system.

In Tapestry, every object and node is identified by a UUID. The system is entirely distributed, decentralized and peer-to-peer. Each node stores a routing table of its various neighbours by the prefix of their UUID. This lets routing occur digit by digit, effectively turning lookup into the traversal of a distributed [https://en.wikipedia.org/wiki/Radix_tree Radix tree].

* DNS as tree but Tapestry as hercically structured.
* How does the information flow? Each node has a neighbour table which that contains the neighbour's number.
** From initialization, each node has a locally optimal routing table that it maintains
** Routing happens digit by digit

* Tapestry API:
** have four operations called PublishObject, UnpublishObject, RouteToObject, RouteToNode.
** each node has ID and each endpoint object has a GUID (Globally unique identifier).

* Tapestry look like operating system.
** it has two models,one is built on UDP protocol and the other on TCP protocol.

Fun fact, it is now called [http://current.cs.ucsb.edu/projects/chimera/ Chimera].

DistOS 2014W Lecture 12

2014-04-24T14:34:51Z

Eapache: /* Introduction */

=Chubby (Feb 13)=
[https://www.usenix.org/legacy/events/osdi06/tech/burrows.html Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems (OSDI 2006)]

==Introduction==

[http://en.wikipedia.org/wiki/Distributed_lock_manager#Google.27s_Chubby_lock_service Chubby], developed at Google, was designed to be a coarse-grained locking service for use within loosely coupled distributed systems (i.e., a network consisting of a high number of small machines). The key contribution was the implementation of Chubby (i.e., there were no new algorithms designed/introduced).

Its purpose is to allow clients to synchronize their activities and to agree on basic information about their environment. It is used to varying degrees by other Google project such as the GFS, MapReduce, and BigTable.

By course grained locking, we mean locking resources for extended lengths of time. For example, electing a primary would handle all access to given data for hours or days.

It is basically a ultra reliable and available file system for very small files that is used as a locking service.

Anil: "Once implemented, Chubby abstracts away all the crazy complicated stuff so you can more easily build your distributed system". Chubby is a tool that gives Google devs important guarantees to build on.

The open-source equivalent is [https://zookeeper.apache.org/ Apache Zookeeper].

==Design==

The funny thing is that Chubby is essentially a filesystem (with files, file permissions, reading/writing, a hierarchal structure, etc.) with a few caveats. Mainly that any file can act as a reader/writer lock and that only whole file operations are performed (i.e., the whole file is written or read), as the files are quite small (256K max). The main reason for implementing the distributed lock service (Chubby) using file system rather than using may be a library based approach was because of the need to make it an easier to use system.

All the locks are fully advisory, meaning others can "go around" whoever has the lock to access the resource (for reading and, sometimes, writing), as opposed to mandatory, mandatory locks giving completely exclusive access to a resource. The reason why chubby goes for advisory locks is that if a client having a lock ends in a problem for some reason there should be a way to release the lock graciously rather than requiring the entire system to be brought down or rebooted.

It can be noted that Linux also utilizes advisory locks as opposed to Windows, which only utilizes mandatory locks. This could be a shortcoming of Windows as, when anything changes regarding the system, the system must be completely rebooted as the locks on files are never broken. With advisory locks, as in Linux, the system need only be rebooted when the kernel is modified/updated.

Chubby also functions as a name server, but only really for functional names/roles , such as for the mail server or a GFS server (i.e., Chubby is mainly used as a name server for logical/symbolic names for roles). It is a centralized place that maps names to resources. A unified interface to do so. The name-value mappings in Chubby allow for a consistent, real-time, overall view of the entire system.

As a name server, Chubby provides guarantees not given with DNS (e.g., DNS is subject to a stale cache) as Chubby provides a unified view of the way things are in the system.

Chubby was made coarse-grained for scalability as coarse-grained locks give the ability to create a distributed system while the fine-grained locks wouldn't scale well. It can also be noted that a fine-grained lock could be implemented on top of the coarse-grained locks. The entire point of Chubby was to give ultra-high availability and integrity.

==Implementation==

* Uses [http://en.wikipedia.org/wiki/Paxos_(computer_science) paxos], which is an insanely complicated way of solving the distributed consensus problem.
** Given many proposed values, it chooses one to be agreed upon.
** More recently, a new consensus algorithm, [https://raftconsensus.github.io/ raft], has been proven which is much simpler to understand if you're interested in that sort of thing. Chubby does not use raft, but it could in theory just swap it in place of paxos.

* Master chubby server with 4 slaves (5 servers total make up a Chubby Cell)
** Master and slaves have all the data.
** Nothing particularity special about the master
** If the master fails, one slave is elected as a new master

==use cases==

==Discussion==

Where else do we see things such as Chubby? Where would you want this consistent, overall view?

You would want this consistent view in any sort of synchronized set of files across a set of systems, such as Dropbox. The main tenants of Chubby's design would hold where you would want to make sure there was an online consensus. It should be noted that this is not like version control as, with version control, everyone has their own copy which are all merged later. However, in this type of system, there is only one version available throughout the distributed system. Chubby's design would differ from Dropbox in that Dropbox is designed so that you can work offline and then synchronize your changes once you are online again (i.e., there can sometimes be more than one version of a file meaning you lack the consistent, overall view given by Chubby).

In Anil's opinion we can think about Chubby as an example of bootstrapping, based on the idea of having/building one good thing to realize your needs rather than adding mechanisms to existing systems. It is nice to have consistency in the world of distributed systems but it comes with a cost, are you willing to pay for it? is one main question distributed system designers, users often encounters. In Anil's view chubby brings down this cost a bit lower. Anil mentioned that one of the main ideas of the Distributed Operating systems course is to understand why you need different algorithms/mechanisms to build a Distributed System rather than looking at the internals of each algorithm in depth.

DistOS 2014W Lecture 12

2014-04-24T14:33:40Z

Eapache: /* Implementation */

=Chubby (Feb 13)=
[https://www.usenix.org/legacy/events/osdi06/tech/burrows.html Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems (OSDI 2006)]

==Introduction==

[http://en.wikipedia.org/wiki/Distributed_lock_manager#Google.27s_Chubby_lock_service Chubby], developed at Google, was designed to be a coarse-grained locking service for use within loosely coupled distributed systems (i.e., a network consisting of a high number of small machines). The key contribution was the implementation of Chubby (i.e., there were no new algorithms designed/introduced).

Its purpose is to allow clients to synchronize their activities and to agree on basic information about their environment. It is used to varying degrees by other Google project such as the GFS, MapReduce, and BigTable.

By course grained locking, we mean locking resources for extended lengths of time. For example, electing a primary would handle all access to given data for hours or days.

It is basically a ultra reliable and available file system for very small files that is used as a locking service.

Anil: "Once implemented, Chubby abstracts away all the crazy complicated stuff so you can more easily build your distributed system". Chubby is a tool that gives Google devs important guarantees to build on.

==Design==

The funny thing is that Chubby is essentially a filesystem (with files, file permissions, reading/writing, a hierarchal structure, etc.) with a few caveats. Mainly that any file can act as a reader/writer lock and that only whole file operations are performed (i.e., the whole file is written or read), as the files are quite small (256K max). The main reason for implementing the distributed lock service (Chubby) using file system rather than using may be a library based approach was because of the need to make it an easier to use system.

All the locks are fully advisory, meaning others can "go around" whoever has the lock to access the resource (for reading and, sometimes, writing), as opposed to mandatory, mandatory locks giving completely exclusive access to a resource. The reason why chubby goes for advisory locks is that if a client having a lock ends in a problem for some reason there should be a way to release the lock graciously rather than requiring the entire system to be brought down or rebooted.

It can be noted that Linux also utilizes advisory locks as opposed to Windows, which only utilizes mandatory locks. This could be a shortcoming of Windows as, when anything changes regarding the system, the system must be completely rebooted as the locks on files are never broken. With advisory locks, as in Linux, the system need only be rebooted when the kernel is modified/updated.

Chubby also functions as a name server, but only really for functional names/roles , such as for the mail server or a GFS server (i.e., Chubby is mainly used as a name server for logical/symbolic names for roles). It is a centralized place that maps names to resources. A unified interface to do so. The name-value mappings in Chubby allow for a consistent, real-time, overall view of the entire system.

As a name server, Chubby provides guarantees not given with DNS (e.g., DNS is subject to a stale cache) as Chubby provides a unified view of the way things are in the system.

Chubby was made coarse-grained for scalability as coarse-grained locks give the ability to create a distributed system while the fine-grained locks wouldn't scale well. It can also be noted that a fine-grained lock could be implemented on top of the coarse-grained locks. The entire point of Chubby was to give ultra-high availability and integrity.

==Implementation==

* Uses [http://en.wikipedia.org/wiki/Paxos_(computer_science) paxos], which is an insanely complicated way of solving the distributed consensus problem.
** Given many proposed values, it chooses one to be agreed upon.
** More recently, a new consensus algorithm, [https://raftconsensus.github.io/ raft], has been proven which is much simpler to understand if you're interested in that sort of thing. Chubby does not use raft, but it could in theory just swap it in place of paxos.

* Master chubby server with 4 slaves (5 servers total make up a Chubby Cell)
** Master and slaves have all the data.
** Nothing particularity special about the master
** If the master fails, one slave is elected as a new master

==use cases==

==Discussion==

Where else do we see things such as Chubby? Where would you want this consistent, overall view?

You would want this consistent view in any sort of synchronized set of files across a set of systems, such as Dropbox. The main tenants of Chubby's design would hold where you would want to make sure there was an online consensus. It should be noted that this is not like version control as, with version control, everyone has their own copy which are all merged later. However, in this type of system, there is only one version available throughout the distributed system. Chubby's design would differ from Dropbox in that Dropbox is designed so that you can work offline and then synchronize your changes once you are online again (i.e., there can sometimes be more than one version of a file meaning you lack the consistent, overall view given by Chubby).

In Anil's opinion we can think about Chubby as an example of bootstrapping, based on the idea of having/building one good thing to realize your needs rather than adding mechanisms to existing systems. It is nice to have consistency in the world of distributed systems but it comes with a cost, are you willing to pay for it? is one main question distributed system designers, users often encounters. In Anil's view chubby brings down this cost a bit lower. Anil mentioned that one of the main ideas of the Distributed Operating systems course is to understand why you need different algorithms/mechanisms to build a Distributed System rather than looking at the internals of each algorithm in depth.

DistOS 2014W Lecture 8

2014-04-23T17:33:56Z

Eapache: /* Class Discussion: */

==NFS and AFS (Jan 30)==

* [http://homeostasis.scs.carleton.ca/~soma/distos/2008-02-11/sandberg-nfs.pdf Russel Sandberg et al., "Design and Implementation of the Sun Network Filesystem" (1985)]
* [http://homeostasis.scs.carleton.ca/~soma/distos/2008-02-11/howard-afs.pdf John H. Howard et al., "Scale and Performance in a Distributed File System" (1988)]

==NFS==
Group 1:

1) per operation traffic.

2) rpc based. Easy with which to program but a very [http://www.joelonsoftware.com/articles/LeakyAbstractions.html leaky abstraction].

3) unreliable

Group 2:

1) designed to share disks over a network, not files

2) more UNIX like. They tried to maintain unix file semantics on the client and server side.

3) portable. It was meant to work (as a server) across many FS types.

4) used UDP: if request dropped, just request again.

5) it is not minimize network traffic.

6) used VNODE, VFS as transparent interfaces to local disks.

7) not have much hardware equipment

8) later versions took on features of AFS

9) stateless protocol conflicts with files being stateful by nature.

Group 3:

1) cache assumption invalid.

2) no dedicated locking mechanism. They couldn't decide on which locking strategy to use, so they left it up to the users of NFS to use their own separate locking service.

3) bad security

Other:
* Client mounts full FS. No common namespace.
* Hostname lookup and address binding happens at mount

==AFS==

Group 1

1) design for 5000 to 10000 clients

2) high integrity.

Group 2

1) designed to share files over a network, not disks. It is one FS.

2) better scalability

3) better security (Kerberos).

4) minimize network traffic.

5) less UNIX like

6) plugin authentication

7) needs more kernel storage due to complex commands

8) inode concept replaced with fid

Group 3

1) cache assumption valid

2) locking

3) good security.

Other:
* Caches full files locally on open. Sends diffs on close.

==Class Discussion:==

NFS and AFS took substantially different approaches to the many problems they faced; while we consider AFS to have made generally better choices in this respect, it was not widely adopted because it was complex and difficult to setup/administer/maintain. NFS however, was comparatively simple. Its protocol and API were relatively stateless (thus it used UDP) and it shared information at the file level rather than the block level. It was also built on RPC, which was convenient to program in but was (as we have already discussed) a bad abstraction since it hid the inherent flakiness of the network. This use of RPC led to security and reliability problems with NFS.

AFS took a more thorough approach to figuring out coherent consistency guarantees and how to implement them efficiently. The AFS designers considered the network as a bottle neck and tried to reduce the amount of chatter over network by making heavy use of caching. The 'open' and 'close' operations in AFS were critical, assuming importance similar in proportion to 'commit' operations in a well-designed database system. The security model of AFS was also interesting in that rather than going for the UNIX access list based implementation AFS used a single sign on system based on Kerberos.

DistOS 2014W Lecture 6

2014-04-23T17:23:42Z

Eapache:

'''the point form notes for this lecture could be turned into full sentences/paragraphs'''

==The Early Web (Jan. 23)==

* [https://archive.org/details/02Kahle000673 Berners-Lee et al., "World-Wide Web: The Information Universe" (1992)], pp. 52-58
* [http://www.youtube.com/watch?v=72nfrhXroo8 Alex Wright, "The Web That Wasn't" (2007)], Google Tech Talk

== Group Discussion on "The Early Web" ==

Questions to discuss:

# How do you think the web would have been if not like the present way?
# What kind of infrastructure changes would you like to make?

=== Group 1 ===
: Relatively satisfied with the present structure of the web some changes suggested are in the below areas:
* Make use of the greater potential of Protocols
* More communication and interaction capabilities.
* Implementation changes in the present payment method systems. Example usage of "Micro-computation" - a discussion we would get back to in future classes. Also, Cryptographic currencies.
* Augmented reality.
* More towards individual privacy.

=== Group 2 ===
==== Problem of unstructured information ====
A large portion of the web serves content that is overwhelmingly concerned about presentation rather than structuring content. Tim Berner-Lees himself bemoaned the death of the semantic web. His original vision of it was as follows:


<blockquote>I have a dream for the Web [in which computers] become capable of analyzing all the data on the Web – the content, links, and transactions between people and computers. A "Semantic Web", which makes this possible, has yet to emerge, but when it does, the day-to-day mechanisms of trade, bureaucracy and our daily lives will be handled by machines talking to machines. The "intelligent agents" people have touted for ages will finally materialize.<ref>{{cite book |last=Berners-Lee |first=Tim |authorlink=Tim Berners-Lee |coauthors=Fischetti, Mark |title=Weaving the Web |publisher=HarperSanFrancisco |year=1999 |pages=chapter 12 |isbn=978-0-06-251587-2 |nopp=true }}</ref></blockquote>

For this vision to be true, information arguably needs to be structured, maybe even classified. The idea of a universal information classification system has been floated. The modern web is mostly developed by software developers and similar, not librarians and the like.



Also, how does one differentiate satire from fact?

==== Valuation and deduplication of information ====
Another problem common with the current web is the duplication of information. Redundancy is not in itself harmful to increase the availability of information, but is ad-hoc duplication of the information itself?

One then comes to the problem of assigning a value to the information found therein. How does one rate information, and according to what criteria? How does one authenticate the information? Often, popularity is used as an indicator of veracity, almost in a sophistic manner. See excessive reliance on Google page ranking or Reddit score for various types of information consumption for research or news consumption respectively.

=== On the current infrastructure ===
The current <em>internet</em> infrastructure should remain as is, at least in countries with not just a modicum of freedom of access to information. Centralization of control of access to information is a terrible power. See China and parts of the Middle-East. On that note, what can be said of popular sites, such as Google or Wikipedia that serve as the main entry point for many access patterns?

The problem, if any, in the current web infrastructure is of the web itself, not the internet.

=== Group 3 ===
* What we want to keep
** Linking mechanisms
** Minimum permissions to publish
* What we don't like
** Relying on one source for document
** Privacy links for security
* Proposal
** Peer-peer to distributed mechanisms for documenting
** Reverse links with caching (distributed cache) that doesn't compromise anything
** More availability for user - what happens when system fails?
** Key management to be considered - Is it good to have centralized or distributed mechanism?
** Make information centric as opposed to host centric

=== Group 4 ===
* An idea of web searching for us
* A suggestion of a different web if it would have been implemented by "AI" people
** AI programs searching for data - A notion already being implemented by Google slowly.
* Generate report forums
* HTML equivalent is inspired by the AI communication
* Higher semantics apart from just indexing the data
** Problem : "How to bridge the semantic gap?"
** Search for more data patterns

== Group design exercise — The web that could be ==

The web as it currently stands (and to the distress of librarians everywhere) is a vast soup of unstructured information. Many ideas for "the web that could be" focus on a web for structured information, but this hits several difficulties:

* Nobody has ever been able to agree on a universal classification system for all potential information.
* The training overhead of classifiers (e.g., librarians) is high. See the master's that a librarian would need.

Our current solution is a combination of various technologies including search engines and brute-force indexing, natural language processing, and tagging via the "semantic web". Unfortunately this system has its own problems:

* The semantic web has effectively died because nobody bothered tagging anything.
* The problem of information duplication when information gets redistributed across the web. However, we do want redundancy.
* Too much developed by software developers
* Too reliant on Google for web structure
** See search-engine optimization
* Problem of authentication (of the information, not the presenter)
** Too dependent at times on the popularity of a site, almost in a sophistic manner.
** See Reddit
* How do you programmatically distinguish satire from fact

Other problems discussed include:

* Information doesn't have the same persistence, see bitrot and Vint Cerf's talk.
* Too concerned with presentation now.
* The web's structure is also “shaped by inbound links but would be nice a bit more”
* Infrastructure doesn't need to change per se.
** The distributed architecture should still stay. Centralization of control of allowed information and access is terrible power. See China and the Middle-East.
** Information, for the most part, in itself, exists centrally (as per-page), though communities (to use a generic term) are distributed.
* Need more sophisticated natural language processing.

== Class discussion ==

Focusing on vision, not the mechanism.

* Reverse linking
* Distributed content distribution (glorified cache)
** Both for privacy and redunancy reasons
** Suggested centralized content certification, but doesn't address the problem of root of trust and distributed consistency checking.
*** Distributed key management is a holy grail
*** What about detecting large-scale subversion attempts, like in China
* What is the new revenue model?
** What was TBL's revenue model (tongue-in-cheek, none)?
** Organisations like Google monetized the internet, and this mechanism could destroy their ability to do so.
* Search work is semi-distributed. Suggested letting the web do the work for you.
* Trying to structure content in a manner simultaneously palatable to both humans and machines.
* Using spare CPU time on servers for natural language processing (or other AI) of cached or locally available resources.
* Imagine a smushed Wolfram Alpha, Google, Wikipedia, and Watson, and then distributed over the net.
* The document was TBL's idea of the atom of content, whereas nowaday we really need something more granular.
* We want to extract higher-level semantics.
* Google may not be pure keyword search anymore. It essentially now uses AI to determine relevancy, but we still struggle with expressing what we want to Google.
* What about the adversarial aspect of content hosters, vying for attention?
* People do actively try to fool you.
* Compare to Google News, though that is very specific to that domain. Their vision is a semantic web, but they are incrementally building it.
* In a scary fashion, Google is one of the central points of failure of the web. Even scarier is less technically competent people who depend on Facebook for that.
* There is a semantic gap between how we express and query information, and how AI understands it.
* Can think of Facebook as a distributed human search infrastructure.
* The core service/function of an operating system is to locate information. '''Search is infrastructure.'''
* The problem is not purely technical. There are political and social aspects.
** Searching for a file on a local filesystem should have a unambiguous answer.
** Asking the web is a different thing. “What is the best chocolate bar?”
* Is the web a network database, as understood in COMP 3005, which we consider harmful.
* For two-way links, there is the problem of restructuring data and all the dependencies.
* Privacy issues when tracing paths across the web.
* What about the problem of information revocation?
* Need more augmented reality and distributed and micro payment systems.
* We need distributed, mutually untrusting social networks.
** Now we have the problem of storage and computation, but also take away some of of the monetizationable aspect.
* Distribution is not free. It is very expensive in very funny ways.
* The dream of harvesting all the computational power of the internet is not new.
** Startups have come and gone many times over that problem.
* Google's indexers understands quite well many documents on the web. However, it only '''presents''' a primitive keyword-like interface. It doesn't expose the ontology.
* Organising information does not necessarily mean applying an ontology to it.
* The organisational methods we now use don't use ontologies, but rather are supplemented by them.

Adding couple of related points Anil mentioned during the discussion:
Distributed key management is a holy grail no one has ever managed to get it working. Now a days databases have become important building blocks of the Distributed Operating System. Anil stressed the fact that Databases can in fact be considered as an OS service these days. The question “How you navigate the complex information space?” has remained a prominent question that The Web have always faced.

DistOS 2014W Lecture 5

2014-04-23T17:13:57Z

Eapache: misc cleanup

=The Mother of all Demos (Jan. 21)=

* [http://www.dougengelbart.org/firsts/dougs-1968-demo.html Doug Engelbart Institute, "Doug's 1968 Demo"]
* [http://en.wikipedia.org/wiki/The_Mother_of_All_Demos Wikipedia's page on "The Mother of all Demos"]

= Introduction =

Anil set the theme of the discussion for the week: to try and understand what the early visionaries/researchers wanted the computer to be and what it has become. Putting this in other words, what was considered fundamental those days and where do those stand today? It is to be noted that features that were easier to implement using simple mechanisms were carried forward whereas the ones which demanded more complex systems or the one which were found out to add not much value in the near feature were pegged down in the order. In the same context, the following observations were made: (1) truly distributed computational infrastructure really makes sense only when we have something to distribute (2) use cases drive the large distributed systems, a good example is The Web. Another key observation from Anil was that there was always a Utopian aspect to the early systems be it NLS, ARPANET or Alto; security aspects were never considered essential in those systems, as they were assumed to operate in a trusted environment.

; Operating system
: The software that turns the computer you have into the one you want (Anil)

* What sort of computer did we want to have?
* What sort of abstractions did they want to be easy? Hard?
* What could we build with the internet (not just WAN, but also LAN)?
* Most dreams people had of their computers smacked into the wall of reality.

= MOAD review in groups =

* Chorded keyboard unfortunately obscure, partly because the attendees disagreed with the long-term investment of training the user.
* View control → hyperlinking system, but in a lightweight (more like nanoweight) markup language.
* Ad-hoc ticketing system
* Ad-hoc messaging system
** Used on a time-sharing systme with shared storage,
* Primitive revision control system
* Different vocabulary:
** Bug and bug smear (mouse and trail)
** Point rather than click

= Class review =

* Doug died Jul 2 2013
* Doug himself called it an “online system”, rather than offline composition of code using card punchers as was common in the day.
* What became of the tech:
** Chorded keyboards:
*** Exist but obscure
** Pre-ARPANET network:
*** Time-sharing mainframe
*** 13 workstations
*** Telephone and television circuit
** Mouse
*** “I sometimes apologize for calling it a mouse”
** Collaborative document editing integrated with screen sharing
** Videoconferencing
*** Part of the vision, but more for the demo at the time,
** Hyperlinks
*** The web on a mainframe
** Languages
*** Metalanguages
**** “Part and parcel of their entire vision of augmenting human intelligence.”
**** You must teach the computer about the language you are using.
**** They were the use case. It was almost designed more for augmenting programmer intelligence rather than human intelligence.
*** It was normal for the time to build new languages (domain-specific) for new systems. Nowadays, we standardize on one but develop large APIs, at the expense of conciseness. We look for short-term benefits; we minimize programmer effort.
*** Compiler compiler
** Freeze-pane
** Folding—Zoomable UI (ZUI)
*** Lots of systems do it, but not the default
*** Much easier to just present everything.
** Technologies the required further investment got left behind.
* The NLS had little to no security
** There was a minimal notion of a user
** There was a utopian aspect. Meanwhile, the Mac had no utopian aspect. Data exchange was through floppies. Any network was small, local, ad-hoc, and among trusted peers.
** The system wasn't envisioned to scale up to masses of people who didn't trust each other.
** How do you enforce secrecy.
* Part of the reason for lack of adoption of some of the tech was hardware. We can posit that a bigger reason would be infrastructure.
* Differentiate usability of system from usability of vision
** What was missing was the polish, the ‘sexiness’, and the intuitiveness of later systems like the Apple II and the Lisa.
** The usability of the later Alto is still less than commercial systems.
*** The word processor was modal, which is apt to confuse unmotivated and untrained users.
* In the context of the Mother of All Demos, the Alto doesn't seem entirely revolutionary. Xerox PARC raided his team. They almost had a GUI; rather they had what we call today a virtual console, with a few things above.
* What happens with visionaries that present a big vision is that the spectators latch onto specific aspects.
* To be comfortable with not adopting the vision, one must ostracize the visionary. People pay attention to things that fit into their world view.
* Use cases of networking have changed little, though the means did
* Fundamentally a resource-sharing system; everything is shared, unlike later systems where you would need to explicitly do so. Resources shared fundamentally sense to share: documents, printers, etc.
* Resource sharing was never enough. '''Information-sharing''' was the focus.

“Mother of all demos” is nickname for Engelbart who could make the computers help humans become smarter.

*More interesting in this works that:
"His idea included seeing computing devices as a means to communicate and retrieve information, rather than just crunch numbers. This idea is represented in NLS”On-Line system”.

*Some information about NLS system:
1) NLS was a revolutionary computer collaboration system from the 1960s.
2) Designed by Douglas Engelbart and implemented by researchers at the Augmentation Research Center (ARC) at the Stanford Research Institute (SRI).
3) The NLS system was the first to employ the practical use of :
a) hypertext links,
b) the mouse,
c) raster-scan video monitors,
d) information organized by relevance,
e) screen windowing,
f) presentation programs,
g) and other modern computing concepts.

= Alto review =

* Fundamentally a personal computer
* Applications:
** Drawing program with curves and arcs for drawing
** Hardware design tools (mostly logic boards)
** Time server
* Less designed for reading than the NLS. More designed around paper. Xerox had a laser printer, and you would read what you printed. Hypertext was deprioritized, unlike the NLS vision had focused on what could not be expressed on paper.
* Xerox had almost an obsession with making documents print beautifully.

= Alto vs NLS =
NLS and Alto both had text processing, drawing, programming environments, some form of email (communication). Alto had WYSIWYG everything.

Alto not built on a mainframe. NLS 'resource sharing' was based around the mainframe. Alto had the idea of sharing via the network (ie. printer server).

Alto focused a lot less on 'hypertext'. Less about navigating deep information. It used the paper metaphor. It implemented existing metaphors and adapted them to the PC. Alto people came from a culture that really valued printed paper.

DistOS 2014W Lecture 1

2014-04-20T17:59:53Z

Eapache: cleanup

== What is an Operating System? ==

In general, an OS allows you to run the same applications on (slightly) different hardware. Here are a few thoughts on what the responsibilities and functionality are of modern operating systems, and what we expect from something calling itself an OS:
* A hardware abstraction layer such that diverse hardware resources can be accessed uniformly by software
* A consistent execution environment, which hardware doesn't provide (ie. code written to interface &emdash; think portable code)
* Management of I/O (such as user I/O, machine I/O i.e. network I/O, sensors, videos, etc.)
* Resource management through multiplexing and policy use
** Multiplexing (sharing): one resource wanted by multiple users
* Communication infrastructure (for example inter-process communication) between the users (process, applications) of the operating system.
* Management of synchronization and concurrency issues

We could also say that an OS turns the computer you have into the computer you want. An OS can be defined by the role it plays in the programming of systems. It takes care of resource management and creates abstraction. An OS turns hardware into the computer/API/interface we '''want''' to program.

This is similar to how the browser is becoming the OS of the web. The browser is
the key abstraction needed to run web apps. It is the interface web developers target.
It doesn't matter what you consume a given website on (eg. a phone, tablet,
etc.), the browser abstracts the device's hardware and OS away.

== What is a distributed OS? ==

Anil prefers to think of this 'logically' rather than functionally/physically. This is
because the old distributed operating system (DOS) model applies to systems today which we
don't consider distributed (ie. managing multiple cores, etc). The traditional definition is systems that
manage their resources over a Network.

A lot of these definitions are hard to peg down because simplicity always gets in
the way of truth. These concepts to do not fit into well defined classes.

To draw parallels to our previous definition of operating systems, a distributed OS takes the distributed pieces of a system, and turn it into the system you want.

It is good to think about about DOSes within the context of who/what is in
control, in terms of who makes and enforces decisions in DOSes. In essence, who is in charge? The traditional kernel-process model is a dictatorship, an authoritarian
model of control. The kernel controls what lives or dies. The internet, in contrast, is decentralised (eg. DNS&emdash;to some extent, ignoring centralized roots). Distributed systems may have distributed
policies where there is not one source of power. Even in DOS we see instances of authoritarian/centralized approaches one example being the walled garden model employed by Apple's iOS. Anil's observation is that centralized systems has an inherent fragility built into and these kind of systems come into existence and disappear after a while. Examples being AOL, Myspace. Even Facebook also looks to be a possible candidate for a similar fate. Also, concentrations on policy will tend to fall apart in the future.

DistOS 2014W Lecture 16

2014-03-11T14:25:23Z

Eapache: Created page with "Public Resource Computing"

Public Resource Computing

DistOS 2014W Lecture 15

2014-03-06T15:57:02Z

Eapache:

Can we do any kind of distributed system without crypto? We can't trust crypto...

Perhaps probabilistically...

Want to be able to put data in, have it distributed, and be able to get it out on some other machine.

Availability: "distribute the crap out of it", doesn't need crypto.

Integrity: hashing, but we assume hashes can be forged. If we want to know that we got the same file, then simply send each other the file and compare.

DistOS 2014W Lecture 15

2014-03-06T15:53:19Z

Eapache: Created page with "Can we do any kind of distributed system without crypto? We can't trust crypto..."

Can we do any kind of distributed system without crypto? We can't trust crypto...

DistOS 2014W Lecture 7

2014-01-28T15:56:23Z

Eapache: /* Unix and Plan 9 */

== Project ==

We discussed moving the proposal due date back a week. We also discussed spending the class prior to that date discussing the primary papers people had chosen in order to provide preliminary feedback. Anil spent some time going through the papers from OSDI12 and discussing which ones would make good projects and why.

* Pick a primary paper.
* Find papers that cite that paper, papers it cites, etc. to collect a body of related work.
* Don't just give a history, tell a story!

== Unix and Plan 9 ==

UNIX was built as "a castrated version of Multix", which was a very complex system. Multix was, arguably, so far ahead of its time that we are only just achieving their ambitions now. Unix was much more modest, and therefore much more achievable and successful. Just enough infrastructure to avoid reinventing the wheel. Just a couple of programmers making something for their own use. Unix was not designed as product or commercial entity at all. It was licensed out because AT&T was under severe antitrust scrutiny at the time.

They wanted few, simple abstractions so they made everything a file. Berkeley promptly broke this abstraction by introducing sockets for networking. Plan 9 finally introduced networking using the right abstractions, but was too late. Arguably the reason the BSD folks didn't use the file abstraction was because of the difference in reliability. Files are generally reliable, and failures with them are catastrophic so many applications simply didn't include logic to handle such IO errors. Networks are much less reliable and applications have to be able to deal gracefully with timeouts and other errors.

DistOS 2014W Lecture 7

2014-01-28T15:51:38Z

Eapache: /* Unix and Plan 9 */

DistOS 2014W Lecture 7

2014-01-28T15:42:31Z

Eapache: /* Unix and Plan 9 */

DistOS 2014W Lecture 7

2014-01-28T15:30:50Z

Eapache: /* Project */

DistOS 2014W Lecture 7

2014-01-28T15:30:20Z

Eapache: /* Project */

DistOS 2014W Lecture 7

2014-01-28T15:26:28Z

Eapache: /* Project */

DistOS 2014W Lecture 7

2014-01-28T15:23:26Z

Eapache: Created page with "== Project == We discussed moving the proposal due date back a week. We also discussed spending the class prior to that date discussing the primary papers people had chosen i..."

DistOS 2014W Lecture 2

2014-01-19T20:01:32Z

Eapache: Created page with "(Not sure who originally volunteered to add this lecture, but they haven't put it up so I'm uploading my incomplete notes. Hopefully somebody will be able to fill it in with m..."

(Not sure who originally volunteered to add this lecture, but they haven't put it up so I'm uploading my incomplete notes. Hopefully somebody will be able to fill it in with more detail.)

We now have a working definition of a Distributed OS, so we look a little closer at the underlying network. The internet (and thus the vast majority of distributed OS work today) occurs over the [https://en.wikipedia.org/wiki/TCP_IP| TCP and IP protocols].

Anil observed that the Dist. OS abstractions which succeed are ones that don't hide the network. For example, the remote procedure call (RPC) style abstractions have generally failed because they try to hide the untrusted nature of the network. The result has been a hodge-podge of firewall software which is primarily for blocking RPC-based protocols like SMB, NFS, etc. REST, on the other hand, has succeeded on the open web because it doesn't "hide the network" in this way.

DistOS 2014W Lecture 4

2014-01-16T16:02:41Z

Eapache: /* CPU, Memory, Disk */

Discussions on the Alto

==CPU, Memory, Disk==

====CPU====

The general hardware architecture of the CPU was biased towards the user, meaning that a greater focus was put on IO capabilities and less focus was put on computational power (arithmetic etc). There were two levels of task-switching; the CPU provided sixteen fixed-priority tasks with hardware interrupts, each of which was permanently assigned to a piece of hardware. Only one of these tasks (the lowest-priority) was dedicated to the user. This task actually ran a virtualized BCPL machine (a C-like language); the user had no access at all to the underlying microcode. Other languages could be emulated as well.

====Memory====

The Alto started with 64K of 16-bit words of memory and eventually grew to 256K words. However, the higher memory was not accessible except through special tricks, similar to the way that memory above 4GB is not accessible today on 32-bit systems without special tricks.

====Task Switching====

One thing that was confusing was that they refer to tasks both as the 16 fixed hardware tasks and the many software tasks that could be multiplexed onto the lowest-priority of those hardware tasks. In either case, task switching was cooperative; until a task gave up control by running a specific instruction, no other task could run. From a modern perspective this looks like a major security problem, since malicious software could simply never relinquish the CPU. However, the fact that hardware was first-class in this sense (with full access to the CPU and memory) made the hardware simpler because much of the complexity could be done in software. Perhaps the first hints of what we now think of as drivers?

====Disk and Filesystem====

To make use of disk controller read,write,truncate,delete and etc. commands were made available.To reduce the risk of global damage structural information was saved to label in each page.hints mechanism was also a available using directory get where file resides in disk.file integrity a was check using seal bit and label.

==Ethernet, Networking protocols==

==Graphics, Mouse, Printing==

===Graphics===

A lot of time was spent on what paper and ink provides us in a display sense, constantly referencing an 8.5 by 11 piece of paper as the type of display they were striving for. This showed what they were attempting to emulate in the Alto's display. The authors proposed 500 - 1000 black or white bits per inch of display (i.e. 500 - 100 dpi). However, they were unable to pursue this goal, instead settling for 70 dpi for the display, allowing them to show things such as 10 pt text. They state that a 30 Hz refresh rate was found to not be objectionable. Interestingly, however, we would find this objectionable today--most likely from being spoiled with the sheer speed of computers today, whereas the authors were used to slower performance. The Alto's display took up '''half''' the Alto's memory, a choice we found very interesting.

Another interesting point was that the authors state that they thought it was beneficial that they could access display memory directly rather than using conventional frame buffer organizations. While we are unsure of what they meant by traditional frame buffer organizations, it is interesting to note that frame buffer organizations is what we use today for our displays.

===Mouse===

The mouse outlined in the paper was 200 dpi (vs. a standard mouse from Apple which is 1300 dpi) and had three buttons (one of the standard configurations of mice that are produced today). They were already using different mouse cursors (i.e., the pointer image of the cursor on screen). The real interesting point here is that the design outlined in the paper was so similar to designs we still use today. The only real divergence was the use of optical mice, although the introduction of optical mice did not altogether halt the use of non-optical mice. Today, we just have more flexibility with regards to how we design mice (e.g., having a scroll wheel, more buttons, etc.).

===Printer===

They state that the printer should print, in one second, an 8.5 by 11 inch page defined with 350 dots/inch (roughly 4000 horizontal scan lines of 3000 dots each). Ironically enough, this is not even what they had wanted for the actual Alto display. However, they did not have enough memory to do this and had to work around this by using things such as an incremental algorithm and reducing the number of scan lines. We were disappointed that they did not actually discuss the hardware implementation of the printer, only the software controller. However, it is interesting that the fact they are dividing the memory requirements of the printer between the hardware itself and the computer was quite a modern idea at the time, and still is.

===Other Interesting Notes===

We found it interesting that peripheral devices were included at all.

The author makes a passing mention to having a tablet to draw on. However, he stated that no one really liked having the tablet as it got in the way of the keyboard.

The recurring theme of lack of memory to implement what they had originally envisioned.

==Applications, Programming Environment==

DistOS 2014W Lecture 4

2014-01-16T15:56:36Z

Eapache: /* CPU, Memory, Disk */

Discussions on the Alto

==CPU, Memory, Disk==

====CPU====

The general hardware architecture of the CPU was biased towards the user, meaning that a greater focus was put on IO capabilities and less focus was put on computational power (arithmetic etc). There were two levels of task-switching; the CPU provided sixteen fixed-priority tasks with hardware interrupts, each of which was permanently assigned to a piece of hardware. Only one of these tasks (the lowest-priority) was dedicated to the user. This task actually ran a virtualized BCPL machine (a C-like language); the user had no access at all to the underlying microcode. Other languages could be emulated as well.

====Memory====

The Alto started with 64K of 16-bit words of memory and eventually grew to 256K words. However, the higher memory was not accessible except through special tricks, similar to the way that memory above 4GB is not accessible today on 32-bit systems without special tricks.

====Task Switching====

One thing that was confusing was that they refer to tasks both as the 16 fixed hardware tasks and the many software tasks that could be multiplexed onto the lowest-priority of those hardware tasks. In either case, task switching was cooperative; until a task gave up control by running a specific instruction, no other task could run. From a modern perspective this looks like a major security problem, since malicious software could simply never relinquish the CPU. However, the fact that hardware was first-class in this sense (with full access to the CPU and memory) made the hardware simpler because much of the complexity could be done in software. Perhaps the first hints of what we now think of as drivers?

====Disk and Filesystem====

==Ethernet, Networking protocols==

==Graphics, Mouse, Printing==

===Graphics===

A lot of time was spent on what paper and ink provides us in a display sense, constantly referencing an 8.5 by 11 piece of paper as the type of display they were striving for. This showed what they were attempting to emulate in the Alto's display. The authors proposed 500 - 1000 black or white bits per inch of display (i.e. 500 - 100 dpi). However, they were unable to pursue this goal, instead settling for 70 dpi for the display, allowing them to show things such as 10 pt text. They state that a 30 Hz refresh rate was found to not be objectionable. Interestingly, however, we would find this objectionable today--most likely from being spoiled with the sheer speed of computers today, whereas the authors were used to slower performance. The Alto's display took up '''half''' the Alto's memory, a choice we found very interesting.

Another interesting point was that the authors state that they thought it was beneficial that they could access display memory directly rather than using conventional frame buffer organizations. While we are unsure of what they meant by traditional frame buffer organizations, it is interesting to note that frame buffer organizations is what we use today for our displays.

===Mouse===

The mouse outlined in the paper was 200 dpi (vs. a standard mouse from Apple which is 1300 dpi) and had three buttons (one of the standard configurations of mice that are produced today). They were already using different mouse cursors (i.e., the pointer image of the cursor on screen). The real interesting point here is that the design outlined in the paper was so similar to designs we still use today. The only real divergence was the use of optical mice, although the introduction of optical mice did not altogether halt the use of non-optical mice. Today, we just have more flexibility with regards to how we design mice (e.g., having a scroll wheel, more buttons, etc.).

===Printer===

===Other Interesting Notes===

We found it interesting that peripheral devices were included at all.

The author makes a passing mention to having a tablet to draw on. However, he stated that no one really liked having the tablet as it got in the way of the keyboard.

==Applications, Programming Environment==

DistOS 2014W Lecture 4

2014-01-16T15:54:53Z

Eapache: /* CPU, Memory, Disk */

Discussions on the Alto

==CPU, Memory, Disk==

The general hardware architecture of the CPU was biased towards the user, meaning that a greater focus was put on IO capabilities and less focus was put on computational power (arithmetic etc). There were two levels of task-switching; the CPU provided sixteen fixed-priority tasks with hardware interrupts, each of which was permanently assigned to a piece of hardware. Only one of these tasks (the lowest-priority) was dedicated to the user. This task actually ran a virtualized BCPL machine (a C-like language); the user had no access at all to the underlying microcode. Other languages could be emulated as well.

The Alto started with 64K of 16-bit words of memory and eventually grew to 256K words. However, the higher memory was not accessible except through special tricks, similar to the way that memory above 4GB is not accessible today on 32-bit systems without special tricks.

One thing that was confusing was that they refer to tasks both as the 16 fixed hardware tasks and the many software tasks that could be multiplexed onto the lowest-priority of those hardware tasks. In either case, task switching was cooperative; until a task gave up control by running a specific instruction, no other task could run. From a modern perspective this looks like a major security problem, since malicious software could simply never relinquish the CPU. However, the fact that hardware was first-class in this sense (with full access to the CPU and memory) made the hardware simpler because much of the complexity could be done in software. Perhaps the first hints of what we now think of as drivers?

==Ethernet, Networking protocols==

==Graphics, Mouse, Printing==

===Graphics===

A lot of time was spent on what paper and ink provides us in a display sense, constantly referencing an 8.5 by 11 piece of paper as the type of display they were striving for. This showed what they were attempting to emulate in the Alto's display. The authors proposed 500 - 1000 black or white bits per inch of display (i.e. 500 - 100 dpi). However, they were unable to pursue this goal, instead settling for 70 dpi for the display, allowing them to show things such as 10 pt text. They state that a 30 Hz refresh rate was found to not be objectionable. Interestingly, however, we would find this objectionable today--most likely from being spoiled with the sheer speed of computers today, whereas the authors were used to slower performance. The Alto's display took up '''half''' the Alto's memory, a choice we found very interesting.

Another interesting point was that the authors state that they thought it was beneficial that they could access display memory directly rather than using conventional frame buffer organizations. While we are unsure of what they meant by traditional frame buffer organizations, it is interesting to note that frame buffer organizations is what we use today for our displays.

===Mouse===

The mouse outlined in the paper was 200 dpi (vs. a standard mouse from Apple which is 1300 dpi) and had three buttons (one of the standard configurations of mice that are produced today). They were already using different mouse cursors (i.e., the pointer image of the cursor on screen). The real interesting point here is that the design outlined in the paper was so similar to designs we still use today. The only real divergence was the use of optical mice, although the introduction of optical mice did not altogether halt the use of non-optical mice. Today, we just have more flexibility with regards to how we design mice (e.g., having a scroll wheel, more buttons, etc.).

===Printer===

===Other Interesting Notes===

We found it interesting that peripheral devices were included at all.

The author makes a passing mention to having a tablet to draw on. However, he stated that no one really liked having the tablet as it got in the way of the keyboard.

==Applications, Programming Environment==

DistOS 2014W Lecture 4

2014-01-16T15:45:50Z

Eapache: /* CPU, Memory, Disk */