Soma-notes - User contributions [en]

DistOS 2015W Session 9

2015-04-13T01:49:48Z

Ashley:

* Anderson et al., "SETI@home: An Experiment in Public-Resource Computing" (CACM 2002) [http://dx.doi.org/10.1145/581571.581573 (DOI)] [http://dl.acm.org.proxy.library.carleton.ca/citation.cfm?id=581573 (Proxy)]
* Anderson, "BOINC: A System for Public-Resource Computing and Storage" (Grid Computing 2004) [http://dx.doi.org/10.1109/GRID.2004.14 (DOI)] [http://ieeexplore.ieee.org.proxy.library.carleton.ca/stamp/stamp.jsp?tp=&arnumber=1382809 (Proxy)]
* [http://research.google.com/archive/mapreduce.html Dean & Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters" (OSDI 2004)]
* [http://dl.acm.org/citation.cfm?doid=2517349.2522738 Murray et al., "Naiad: a timely dataflow system" (SOSP 2013)]

Session 9 is about processing large volumes of data (big data).

BOINC and SETI@home are crowdsourced systems that spread the input data across computers via the internet to have each chunk individually processed and returned back to the sender.

MapReduce and Naiad are more technically challenging systems that not only let nodes process individual chunks of data but also combine and fold them together to allow algorithms to process various aggregate results from the input data set.

== BOINC ==

*Public Resource Computing Platform
*Gives scientists the ability to use large amounts of computation resources.
*The clients do not connect directly with each other but instead they talk to a central server located at Berkley
*The goals of Boinc are:
:*1) reduce the barriers of entry
:*2) Share resources among autonomous projects
:*3) Support diverse applications
:*4) Reward participants.
:*5) Provide screensaver graphics

*It can run as applications in common language with no modifications
*A BOINC application can be identified by a single master URL, which serves as the homepage as well as the directory of the servers.
*Servers perform set of function using:
**Scheduling servers: handles Remote Procedure Call from clients
** Data servers:helps to manage the uploads

*Can only work on data that can be split into many small shards and each shard processed entirely independently. Pure mappings on big data, no larger folding capabilities. Was used for scientific purposes mostly.

== SETI@Home ==

*Uses public resource computing to analyze radio signals to find extraterrestrial intelligence
*Need good quality telescope to search for radio signals, and lots of computational power, which was unavailable locally
*It has not yet found extraterrestrial intelligence, but its has established credibility of public resource computing projects
*Originally custom, now uses BOINC as a backbone for the project
*Uses relational database to store information on a large scale, further it uses a multi-threaded server to distribute work to clients
*Quality of data in this architecture is untrustworthy, the main incentive to use it, however, is that it is a cheap and easy way of scaling the work exponentially.
*Provided social incentives to encourage users to join the system.
*This computation model still exists but not in the legitimate world.
*Formed a good concept of public resource computing and a distributed computing by providing a platform independent framework

== MapReduce ==

*A programming model presented by Google to do large scale parallel computations
*Uses the <code>Map()</code> and <code>Reduce()</code> functions from functional style programming languages
:*Map (Filtering)
::*Takes a function and applies it to a bunch of keys to produce values
* Hides parallelization, fault tolerance, locality optimization and load balancing
:*Reduce (Summary)
::*Accumulates results from the data set using a given function
* Very easy to use and understand, with many classic problems fitting this pattern
* Otherwise quite constrained in what exactly can be done
* Uses hashing to distribute similar keys to similar machines, but otherwise spread the load

== Naiad ==

*A programming model similar to <code>MapReduce</code> but with streaming capabilities so that data results are almost instantaneous
*A distributed system for executing data parallel cyclic dataflow programs offering high throughput and low latency
*Aims to provide a general purpose system which will fulfill the requirements and the will also support wide variety of high level programming models.
*Highly used for parallel execution of data
*Provides the functionality of checkpoint and restoring
*A complex framework that can be the backend for simpler models of computation like LINQ or MapReduce to be built on top of.
*Real Time Applications:
:*Batch iterative Machine Learning:
VW, an open source distributed machine learning performs iteration in 3 phases: each process updates local state; processes independently training on local data; and process jointly performed global average which is All Reduce.
:*Streaming Acyclic Computation
When compared to a system called [http://research.microsoft.com/apps/pubs/default.aspx?id=163832 Kineograph] ( also done by Microsoft ), which processes twitter handles and provides counts of the occurrence of hashtags as well as links between popular tags, was written using Naiad in 26 lines of code and ran close to 2X faster.
* Naiad paper won the best paper award in SOSP 2013, check-out this link in Microsoft Research website http://research.microsoft.com/en-us/projects/naiad/ . Down in this page you can see some videos that explains naiad including Derek's Murray presentation at SOSP 2013.

DistOS 2015W Session 9

2015-04-13T01:43:45Z

Ashley:

* Anderson et al., "SETI@home: An Experiment in Public-Resource Computing" (CACM 2002) [http://dx.doi.org/10.1145/581571.581573 (DOI)] [http://dl.acm.org.proxy.library.carleton.ca/citation.cfm?id=581573 (Proxy)]
* Anderson, "BOINC: A System for Public-Resource Computing and Storage" (Grid Computing 2004) [http://dx.doi.org/10.1109/GRID.2004.14 (DOI)] [http://ieeexplore.ieee.org.proxy.library.carleton.ca/stamp/stamp.jsp?tp=&arnumber=1382809 (Proxy)]
* [http://research.google.com/archive/mapreduce.html Dean & Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters" (OSDI 2004)]
* [http://dl.acm.org/citation.cfm?doid=2517349.2522738 Murray et al., "Naiad: a timely dataflow system" (SOSP 2013)]

== BOINC ==

*Public Resource Computing Platform
*Gives scientists the ability to use large amounts of computation resources.
*The clients do not connect directly with each other but instead they talk to a central server located at Berkley
*The goals of Boinc are:
:*1) reduce the barriers of entry
:*2) Share resources among autonomous projects
:*3) Support diverse applications
:*4) Reward participants.
:*5) Provide screensaver graphics

*It can run as applications in common language with no modifications
*A BOINC application can be identified by a single master URL, which serves as the homepage as well as the directory of the servers.
*Servers perform set of function using:
**Scheduling servers: handles Remote Procedure Call from clients
** Data servers:helps to manage the uploads

*Can only work on data that can be split into many small shards and each shard processed entirely independently. Pure mappings on big data, no larger folding capabilities. Was used for scientific purposes mostly.

== SETI@Home ==

*Uses public resource computing to analyze radio signals to find extraterrestrial intelligence
*Need good quality telescope to search for radio signals, and lots of computational power, which was unavailable locally
*It has not yet found extraterrestrial intelligence, but its has established credibility of public resource computing projects
*Originally custom, now uses BOINC as a backbone for the project
*Uses relational database to store information on a large scale, further it uses a multi-threaded server to distribute work to clients
*Quality of data in this architecture is untrustworthy, the main incentive to use it, however, is that it is a cheap and easy way of scaling the work exponentially.
*Provided social incentives to encourage users to join the system.
*This computation model still exists but not in the legitimate world.
*Formed a good concept of public resource computing and a distributed computing by providing a platform independent framework

== MapReduce ==

*A programming model presented by Google to do large scale parallel computations
*Uses the <code>Map()</code> and <code>Reduce()</code> functions from functional style programming languages
:*Map (Filtering)
::*Takes a function and applies it to a bunch of keys to produce values
* Hides parallelization, fault tolerance, locality optimization and load balancing
:*Reduce (Summary)
::*Accumulates results from the data set using a given function
* Very easy to use and understand, with many classic problems fitting this pattern
* Otherwise quite constrained in what exactly can be done
* Uses hashing to distribute similar keys to similar machines, but otherwise spread the load

== Naiad ==

*A programming model similar to <code>MapReduce</code> but with streaming capabilities so that data results are almost instantaneous
*A distributed system for executing data parallel cyclic dataflow programs offering high throughput and low latency
*Aims to provide a general purpose system which will fulfill the requirements and the will also support wide variety of high level programming models.
*Highly used for parallel execution of data
*Provides the functionality of checkpoint and restoring
*A complex framework that can be the backend for simpler models of computation like LINQ or MapReduce to be built on top of.
*Real Time Applications:
:*Batch iterative Machine Learning:
VW, an open source distributed machine learning performs iteration in 3 phases: each process updates local state; processes independently training on local data; and process jointly performed global average which is All Reduce.
:*Streaming Acyclic Computation
When compared to a system called [http://research.microsoft.com/apps/pubs/default.aspx?id=163832 Kineograph] ( also done by Microsoft ), which processes twitter handles and provides counts of the occurrence of hashtags as well as links between popular tags, was written using Naiad in 26 lines of code and ran close to 2X faster.
* Naiad paper won the best paper award in SOSP 2013, check-out this link in Microsoft Research website http://research.microsoft.com/en-us/projects/naiad/ . Down in this page you can see some videos that explains naiad including Derek's Murray presentation at SOSP 2013.

DistOS 2015W Session 10

2015-04-13T01:41:19Z

Ashley:

* [http://en.wikipedia.org/wiki/Distributed_hash_table Wikipedia's article on Distributed Hash Tables]
* [http://en.wikipedia.org/wiki/Kademlia Wikipedia's article on Kademlia]
* [http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf Maymounkov and Mazieres, "Kademlia: A Peer-to-peer information system based on the XOR Metric" (2002)]
* [http://en.wikipedia.org/wiki/Tapestry_%28DHT%29 Wikipedia's article on Tapestry]
* [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)]
* [https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Geambasu.pdf Geambasu et al., "Comet: An active distributed key-value store" (OSDI 2010)]

Session 10 is about Distributed Hash Tables. How they work, various algorithmic options (keyspace partitioning being a major example) and some of the earliest implementations.

(Feel free to tweak the questions!)

==Kademlia==
Members: Kirill, Deep, Jason, Hassan

* '''Why are DHTs relevant to distributed OSs?'''
** Using many system, having repetition
** DHT to distributed content over multiple nodes
** Decentralized therefore peer-to-peer

* '''How is content divided?'''
** File hashes
** Node ID to locate the value
** 160 bit key space, binary tree for partition and searching down the tree

* '''How is the network traversed?'''
** Highest prefix and increase the number of digit it used to get close to the target nodes

* '''What trust assumptions does the system make?'''
** DHT by itself is insecure
** The academic and practitioner communities have realized that all current DHT designs suffer from a security weakness, known as the Sybil attack
** K-buckets
*** Binary tree with each node having k-buckets as leaf
*** Any given k-node is very unlikely to fail within an hour of each other
*** New nodes are only inserted when there is room in the bucket or the oldest node doesn't respond
** Uses UDP therefore packets are often lost

* '''Performance constraints?'''
** Binary tree traversing, therefore traversing is maximum O(log n)

* '''What non-DHT internet infrastructure would you replace with a DHT? How suitable is Kademlia for this purpose?'''
** DNS
** Any kind of meta-data service

==Comet==
Members: Mohamed Ahmed, Apoorv Sangal, Ambalica Sharma

* Why are DHTs relevant to distributed OSs?
DHT is an infrastructure than enables many clients to share information, and scale to handle node arrival, departure and failure. DHT's serve many of the design goals of disbtributed operating systems. The paper states that "DHTs are increasingly used to support a variety of distributed applications, such as file-sharing, distributed resource tracking, end-system multicast, publish-subscribe systems, distributed search engines"

* How is content divided?
One of the three main components of the comet system is a routing substrate which
implements the value/node mapping. This allows a client to find the node htat stores
a specific data item. Since Comet uses a DHT implementation, routing occurs by applying
a hash function to the key to compute node ID's that store the associated value.

* How is the network traversed?

* What trust assumptions does the system make?
Assumes clients re untrusted autonomous nodes.

A client node running Comet should be protected from the execution of handlers
e.g. an executing handler cannot corrupt the node or use unlimited resources.
Handlers should not be able to mount messaging attacks on other nodes.

Users downloading Comet must trust it and have guarantees about its behavior. For this reason, Comet enforces four important restrictions:
1. Limited knowledge: an ASO is not aware of other objects
or resources stored on the same node and has no
direct way to learn about them.
2. Limited access: an object handler can manipulate only its own value and cannot modify the values of other objects on its storage node.
3. Limited communication: an active storage object cannot
send arbitrary messages over the network.
4. Limited resource consumption: an ASO’s resource usage is strictly bounded, e.g., the system limits the amount of computation and memory it can consume.

* Performance constraints?

* What non-DHT internet infrastructure would you replace with a DHT? How suitable is Comet for this purpose?

==Tapestry==
Members: Ashley, Dany, Alexis, Khaled

* Why are DHTs relevant to distributed OSs?

Because they provide a way to distribute information over large networks (distributed key/value store).

* How is content divided?

Uses consistent hashing (SHA-1), upon node creation (join) creates optimal routing table.

* How is the network traversed?

You look at your neighbours, you see which neighbour is closest to your destination, and recurse.

* What trust assumptions does the system make?

It assumes the system is entirely trustworthy from adversaries. While network failures may happen and nodes may go down, no node will explicitly try to mess with the network.

* Performance constraints?

O(log n) access times to any given node. Best effort publishing/unpublishing via decentralized object location routing.

* What non-DHT internet infrastructure would you replace with a DHT? How suitable is Tapestry for this purpose?

== Other Resources ==
*[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1610546&tag=1 A survey and comparison of peer-to-peer overlay network schemes]
*[http://link.springer.com/article/10.1007/s12083-012-0157-3 Collaborative Applications over Peer-to-Peer Systems – Challenges and Solutions]

DistOS 2015W Session 11

2015-04-13T01:36:57Z

Ashley:

* [http://research.google.com/archive/bigtable-osdi06.pdf Chang et al., "BigTable: A Distributed Storage System for Structured Data" (OSDI 2006)]
* [http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf DeCandia et al., "Dynamo: Amazon’s Highly Available Key-value Store" (SOSP 2007)]
* [http://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf Lakshman & Malik, "Cassandra - A Decentralized Structured Storage System" (LADIS 2009)]
* [https://www.usenix.org/conference/osdi12/technical-sessions/presentation/corbett Corbett et al., "Spanner: Google’s Globally-Distributed Database" (OSDI 2012)]

Session 11's theme is about Distributed Hash Tables as they are used and implemented by large commercial companies, for what purposes, and with what specializations or design constraints. Two papers focus on Google, while Facebook and Amazon get one each.

==BigTable==
* Google System used for storing data of various Google Products, for instance Google Analytics, Google Finance, Orkut, Personalized Search, Writely, Google Earth and many more
* Big table is
** Sparse
** Persistant
** Muti dimensional Sorted Map
*It is indexed by
** Row Key: Every read or write of data under single row key is atomic. Each row range is called Tablet. Select Row key to get good locality for data access.
** Column Key: Grouped into sets called Column Families. Forms basic unit of Access Control.All data stored is of same type.Syntax used: ''family:qualifier''
** Time Stamp:Each cell consists of multiple versions of same data which are indexed by Timestamps.In order to avoid collisions, Timestamps need to be generated by applications.
* Big Table '''API''': Provides functions for
** Creating and Deleting
*** Tables
*** Column Families
**Changing Cluster
**Changing Table
**Column Family metadata like Access Control Rights.
** Set of wrappers which allow Big Data to be used both as
*** Input source
***Output Target
*The timestamp mechanism in BIG table helps clients to access recent versions of data with simple accessing aspects of using row and column.
*Parallel computation and cluster management system makes BIG table flexible and highly scalable.

== Dynamo==
* Amazon's Key Value Store
*Availability is the buzz word for Dynamo. Dynamo=Availability
*Shifted Computer Science paradigm from caring about the consistency to availability.
*Sacrifices consistency under certain failure scenarios.
*Treats failure handling as normal case without impact on availability and performance.
*Data is partitioned and replicated using consistent hashing and consistency is facilitated by use of object versioning.
* This system has certain requirements such as:
** Query Model: Simple read and write operations to data item that are uniquely identified by a key.
**ACID properties: Atomicity, Consistency, Isolation, Durability.
**Efficiency: System needs to function on a commodity hardware infrastructure.
* Service Level Agreements(SLA): They are a negotiated contract between a client and a service regarding characteristics related to systems. They are used in order to guarantee that in a bounded time period, an application can deliver it's functionality.
* System Architecture: It consists of ''System Interface'', ''Partitioning Algorithm'', ''Replication'',''Data Versioning''.
* Successfully handles
** Server Failure
** Data Centre Failure
** Network Partitions
* Allows service owners to customize their own storage systems according to their storage systems to meet the desired performance, durability and consistency SLAs.
* Building block for highly available applications.

==Cassandra==
* Facebook's storage system to fulfil needs of the Inbox Search Problem
*Partitions data across the cluster using consistent hashing.
*Distributed multi dimensional map indexed by a key
* In it's data model:
** Columns grouped together into sets called column families. Column Families further of 2 types:
***Simple column families
***Super column families
* API consists of :
** Insert
**Get
** Delete
* System Architecture consists of :
** Partitioning: Takes place using consistent hashing
**Replication: Each item replicated at n hosts where "n" is the replication factor configured per system.
** Membership: Cluster membership is based on Scuttle butt which is a highly efficient anti-entropy Gossip based mechanism.The Membership further has sub part such as:
***Failure Detection
**Bootstrapping
** Scaling the cluster
*It can run cheap commodity hardware and handle high throughput
*Its multiple usable structure makes it very scalable

=Spanner=
* Google's scalable, multi version, globally distributed database.
* Has been built on top of the Google's Big table.
*Provided data consistency and Supports SQL like Interface.
* Uses a separate high-reliability time service to guarantee the correctness properties around concurrency control.
** The timestamps are utilized.
*It shares data across machines and migrates data automatically across machines
*Data Control Functions in spanner controls latency and performance

DistOS 2015W Session 12

2015-04-13T01:10:53Z

Ashley:

* [http://static.usenix.org/legacy/events/osdi10/tech/full_papers/Beaver.pdf Beaver et al., "Finding a needle in Haystack: Facebook’s photo storage" (OSDI 2010)]
* [https://www.usenix.org/conference/osdi12/technical-sessions/presentation/gordon Gordon et al., "COMET: Code Offload by Migrating Execution Transparently" (OSDI 2012)]
* [https://www.usenix.org/conference/osdi14/technical-sessions/presentation/muralidhar Muralidhar et al., "f4: Facebook's Warm BLOB Storage System" (OSDI 2014)]
* [https://www.usenix.org/conference/osdi14/technical-sessions/presentation/zhang Zhang et al., "Customizable and Extensible Deployment for Mobile/Cloud Applications" (OSDI 2014)]

Session 12 had two separate themes running through their papers.

The first was the storage of large volumes of data that would never be modified, rarely be deleted, and read with varying frequency distributions. This was a specific sub problem of the more general challenge of high performance scalable & reliable distributed storage, and once more leads the solvers at hand (Facebook) to design specialized systems to the exploit the specifics of the sub problem for superior performance.

The second was a return to code offloading mechanisms that could turn programs distributed, in a new modern context. COMET works by taking existing smartphone applications and splicing the user interaction and computation between the phone and an external server. Sapphire provides a whole cluster of deployment modules that one can mix & match and apply to conformant programs to turn them into distributed applications.

=Haystack=
* Facebook's Photo Application Storage System.
* Previous Fb photo storage based on NFS design. The reason why NFS didn't work is that it took 3 file-system accesses per logical photo read. Haystack only needs one access.
*Main goals of Haystack:
** High throughput with low latency. It uses one disk operation to provide these.
**Fault tolerance
**Cost effective
**Simple
*Facebook stored all images in haystack with a CDN in front to cache hot data. Haystack still needs to be fast since accessing non-cached data is still common.
*Haystack reduces the memory used for ''filesystem metadata''
*It has 2 types of metadata:
**''Application metadata''
**''File System metadata''
* The architecture consists of 3 components:
**Haystack Store
**Haystack Directory
**Haystack Cache
*Pitchfork and bulk sync were used to tolerate faults. theTfault tolerance works in a very profound way to make haystack feasible and reliable

=Comet=
*Introduced the concept of distributed shared memory (DSM). In a DSM, RAMs from multiple servers would appear as if they are all belonging to one server, allowing better scalability for caching.
*DSM provides advatage over RPC(Remote Procedure Call) including multi threading suuport, thread migration during execution.
*client and server model maintain consistency using DSM
*Comet model works by offloading the computation intensive process from the mobile to only one server.
*The offloading process works by passing the computation intensive process to the server and hold it on the mobile device. Once the process on the server completes, it returns the results and the handle back to the mobile device. In other words, the process does not get physically offloaded to the server but instead it runs on the server and stopped on the mobile device.

=F4=
* Warm Blob Storage System.
** Warm Blob is a store for large quantities of immutable data that isn't frequently accessed, but must still be available.
** Built to reduce the overhead of haystack for old data that doesn't need to be quite as available. Generally data that is a few months old is moved from Haystack to Warm Blob.
** F4 reduce the space usage of Haystack from a replication factor of 3.6 to 2.8 or 2.1 using Reed Solomon coding and XOR coding respectively but still provides consistency.
** Less robust to data center failures as a result.
*Reed Solomon coding basically use(10,4) which means 10 data and 4 parity blocks in a stripe, and can thus tolerate losing up to 4 blocks which means it can tolerate 4 rack failure and use 1.4 expansion factor.Two copies of this would be 2* 1.4= 2.8 effective replication factor.
*XOR coding use(2,1) across three data center and use 1.5 expansion factor which gives 1.5*1.4= 2.1 effective replication factor.
*The caching mechanism provides the reduction in load on storage system and it makes BLOB scaleable.

=Sapphire=
*Represents a building block towards building this global distributed systems. The main critique to it is that it didn’t present a specific use case upon which their design is built upon.
*Sapphire does not show their scalability boundaries. There is no such distributed system model that can be “one size fits all”, most probably it will break in some large scale distributed application.
*Reaching this global distributed system that address all the distributed OS use cases will be a cumulative work of many big bodies and building it block by block and then this system will evolve by putting all these different building blocks together. In other words, reaching a global distributed system will come from a “bottom up not top down approach” [Somayaji, 2015].
*The concept of separate application logic from deployment logic helps programmers in making a flexible system. The other important part that makes it as a scalable system was that it is object based and could be integrated with any object oriented language.

DistOS 2015W Session 9

2015-04-12T20:09:34Z

Ashley: /* BOINC */

== BOINC ==

*Public Resource Computing Platform
*Gives scientists the ability to use large amounts of computation resources.
*The clients do not connect directly with each other but instead they talk to a central server located at Berkley
*The goals of Boinc are:
:*1) reduce the barriers of entry
:*2) Share resources among autonomous projects
:*3) Support diverse applications
:*4) Reward participants.
:*5) Provide screensaver graphics

*It can run as applications in common language with no modifications
*A BOINC application can be identified by a single master URL, which serves as the homepage as well as the directory of the servers.
*Servers perform set of function using:
**Scheduling servers: handles Remote Procedure Call from clients
** Data servers:helps to manage the uploads

*Can only work on data that can be split into many small shards and each shard processed entirely independently. Pure mappings on big data, no larger folding capabilities. Was used for scientific purposes mostly.

== SETI@Home ==

*Uses public resource computing to analyze radio signals to find extraterrestrial intelligence
*Need good quality telescope to search for radio signals, and lots of computational power, which was unavailable locally
*It has not yet found extraterrestrial intelligence, but its has established credibility of public resource computing projects
*Originally custom, now uses BOINC as a backbone for the project
*Uses relational database to store information on a large scale, further it uses a multi-threaded server to distribute work to clients
*Quality of data in this architecture is untrustworthy, the main incentive to use it, however, is that it is a cheap and easy way of scaling the work exponentially.
*Provided social incentives to encourage users to join the system.
*This computation model still exists but not in the legitimate world.
*Formed a good concept of public resource computing and a distributed computing by providing a platform independent framework

== MapReduce ==

*A programming model presented by Google to do large scale parallel computations
*Uses the <code>Map()</code> and <code>Reduce()</code> functions from functional style programming languages
:*Map (Filtering)
::*Takes a function and applies it to a bunch of keys to produce values
* Hides parallelization, fault tolerance, locality optimization and load balancing
:*Reduce (Summary)
::*Accumulates results from the data set using a given function
* Very easy to use and understand, with many classic problems fitting this pattern
* Otherwise quite constrained in what exactly can be done
* Uses hashing to distribute similar keys to similar machines, but otherwise spread the load

== Naiad ==

*A programming model similar to <code>MapReduce</code> but with streaming capabilities so that data results are almost instantaneous
*A distributed system for executing data parallel cyclic dataflow programs offering high throughput and low latency
*Aims to provide a general purpose system which will fulfill the requirements and the will also support wide variety of high level programming models.
*Highly used for parallel execution of data
*Provides the functionality of checkpoint and restoring
*A complex framework that can be the backend for simpler models of computation like LINQ or MapReduce to be built on top of.
*Real Time Applications:
:*Batch iterative Machine Learning:
VW, an open source distributed machine learning performs iteration in 3 phases: each process updates local state; processes independently training on local data; and process jointly performed global average which is All Reduce.
:*Streaming Acyclic Computation
When compared to a system called [http://research.microsoft.com/apps/pubs/default.aspx?id=163832 Kineograph] ( also done by Microsoft ), which processes twitter handles and provides counts of the occurrence of hashtags as well as links between popular tags, was written using Naiad in 26 lines of code and ran close to 2X faster.
* Naiad paper won the best paper award in SOSP 2013, check-out this link in Microsoft Research website http://research.microsoft.com/en-us/projects/naiad/ . Down in this page you can see some videos that explains naiad including Derek's Murray presentation at SOSP 2013.