Distributed Systems

Synchronous and asynchronous Distributed Systems. The notion of time: physical and logical clocks, synchronization of physical and logical clocks, global states. Distributed coordination: group communication, message ordering, mutual exclusion algorithms, election algorithms. Transactions: ACID properties, serializability, concurrency control (locking, optimistic concurrency control, timestamp ordering). Distributed transactions and concurrency control: distributed atomic transactions, TPC, deadlock detection, error recovery. Data replication: CAP theorem, consistency levels, gossip protocols. Structured and unstructured Peer-to-Peer networks, Distributed Hash Tables and basic functionality, Chord. Consensus in Distributed Systems: The Byzantine Generals Problem, the FLP theorem, Paxos distributed consensus algorithm. Distributed Storage Systems (GFS, HDFS, BigTable), distributed processing programming models, MapReduce and Bulk Synchronous Parallel. Distributed Systems paradigms: Hadoop, Spark, Blockchain.