Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Econ 325 exams > 622 final > Flashcards

622 final Flashcards

1
Q

replication pros

A

improves scalability
distribute requests among replicated data servers
improves robustness
if one data server fails, others may be available
reduces latency of access
(wide-area systems) place data close to where it’s needed
(same box) place frequently accessed data in fast media

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

replication cons

A

hard to maintain replica consistency
expensive in case of frequent updates
decide on replica placement may not be trivial
harder in the case of dynamic placement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

replicationcomes in many forms

A

-load balancing
data requests dynamically allocated to co-located replicasEx: database servers, web-search engines
-mirroring
requests directed to one of geographically dispersed replicasEx: web servers
caching: storing data at a convenient place

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

error

A

unintended state of a component/system

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

fault

A

a component/system characteristic or property that may cause errors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

kinds of faults

A

transient
occurs and disappears; unlikely to reoccur
intermittent
recurrently appears and disappears
permanent
persists until fixed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

failure

A

Failure: external manifestation of an error; undesired behavior

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

fail-stop

A

stops doing anything (“crashes”) on failure & we can reliably detect its failure (e.g., announces failure)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

fail arbitrary/byzantine

A

behaves arbitrarily on failure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

fail-silent

A

crashes on failure, but we can’t distinguish crashes from communication link failures

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

fail-safe

A

may crash or produce other results on failure, but failure cannot do any harm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

fail noisy

A

crashes on failure, we can eventually determine that it crashed (detection may be delayed)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

information redundancy

A

adding extra bits so that errors may be detected and possibly recovered

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

time redundancy

A

retry after detecting failure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

physical redundancy

A

providing extra/replacement components

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Triple modular redundancy

A

(LECTURE 7 SLIDE 20)
If A1 fails in fail-arbitrary way, OK
A2 & A3 outvote in each voter
If A2 & A3 fail in fail-silent way, OK
Only A1’s result received by voters, so it’s the only result used by voters
If A1 & V1 fail in fail-arbitrary way, OK
V2 & V3 will be correct (outvoted by A2 & A3), B1 will produce bad value but will be outvoted by B2 & B3
V10 fail in any way – SYSTEM FAILURE
A1 & A2 fail-arbitrary – SYSTEM FAILURE POSSIBLE (outvote A3)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Byzantine faults

A

Byzantine fault = “anything can happen”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

CAP (Brewer’s) theorem

A

It’s impossible for a distributed data store to simultaneously provide > 2 of 3 guarantees:
Consistency: Every read receives the most recent write or an error [not same as ACID definition]
Availability: Every request receives a response that is not an error
Partition tolerance: The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes
In presence of (network) partition, must choose between consistency & availability

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Consistency > availability:

A

ACID (Atomicity, Consistency, Isolation, Durability)
Traditional database systems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Availability > consistency:

A

Eventual consistency / optimistic replication: if no new updates are made to a given data item, eventually all accesses to it will return the last updated value (“converged”)
BASE (Basically Available, Soft state, Eventual consistency) semantics
Many “NoSQL” databases in this category

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

PACELC

A

PACELC extends CAP:
“if there is a partition (P), how does the system trade off availability and consistency (A and C) [per CAP];
else (E), when the system is running normally without partitions, how does the system trade off latency (L) and consistency (C)?”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

PA/EL systems

A

if a partition occurs, prefer availability (giving up consistency), else prefer lower latency (also giving up consistency) – consistency always less important

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

PC/EC systems

A

PC/EC systems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

PA/EC systems

A

if a partition occurs, prefer availability (giving up consistency), else prefer consistency (giving up lower latency)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Baseline MongoDB classified as PA/EC

A

Without partition, system guarantees reads and writes to be consistent (EC), but MongoDB’s data replication makes it PA:
If the master node fails or is partitioned from the rest of the system, “it stores all writes that have been sent to the master node but not yet replicated in a local rollback directory.”
“Meanwhile, the rest of the system elects a new master to remain available for reads and writes.”
“Therefore, the state of the old master and the state of the new master become inconsistent until the system repairs the failure and uses the rollback directory to reconcile the states, which is a manual process today.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

PC/EL systems

A

if a partition occurs, prefer consistency (giving up availability), else (normal case) prefer lower latency (giving up consistency)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

security architecture:

A

set of mechanisms and policiesincorporated in a system for purposes of mitigating the risks from threats

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

threat:

A

potential event that could compromise a security requirement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

attack:

A

realization of a threat

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

vulnerability:

A

a characteristic or flaw in system design or implementation, or in the security procedures, that, if exploited, could result in a security compromise

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

benefit of security:for all threats:

A

expected losses in case of attack,
times chances of attack
- acquisition
- engagement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

cost of security

A

development & maintenance
complex software
infrastructure
product licensing
bigger &/or dedicatedmachines (e.g., firewalls)
degraded performance
encryption, authentication, authorization…

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

protection

A

secure channels
authentication
-communicating parties are who they say they are
-confidentiality and integrity:
third parties cannot interfere in the communication
access control
authorization (authorization != authentication)
-which entities can access which assets and operations
accountability
-always knowing who did what
non-repudiation
-entities cannot get away with denying actions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Trusted Computing Base (TCB)

A

“Set of all security mechanisms in a (distributed) computer system that are needed to enforce a security policy, and thus need to be trusted” [3rd edition pg 507]

Smaller the TCB, the better
Less that must be trusted & less to review)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

trusted vs trustworthy

A

Trusted != trustworthy
Prefer a trustworthy one

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

symmetric encryption

A

aka shared secret key
M = DK (EK (M))
M is the data, D is decrypt, E is encrypt, and k is the key
computationally efficient

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

asymmetric encryption

A

aka public key/private key
M=DK- (EK+ (M))=DK+ (EK- (M))
K+ is public key, and k- is private key
computationally expensive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

hashing & MACs

A

S = H(M), or S = MACK (M)
S, aka digest, is a unique representation of data such that change to the data will change the representation
fixed size and independent of size of M
collision resistant (both weak and strong)
computationally efficient

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

authentication and integrity verification

A

cannot be separated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Access control – general model

A

Subject -> (request for operation) -> Reference Monitor -> (authorized request) -> Object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Access control list (ACL)

A

Each object maintains a list of the access rights of all subjects & their rights
Distributes access control matrix column-wise
There may be a “default” set of rights

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

Capabilities

A

Each subject maintains a list of the objects it controls & the rights over them
Distributes access control matrix row-wise

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

using symmetric encryption for authentication brings up scalability issues

A

in a system with N nodes, each node needs tokeep track of N-1 pair-wise symmetric keysthe number of distinct keys in the system is ~N 2
with asymmetric encryption each nodehas one public key that everyone else usesthe number of distinct keys in the system is ~N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

certification authoritiesdistribute certified public keys

A

a CA stores and makes available pairs<public key, peer identifier>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

Least privilege

A

Each user and program should operate using fewest privileges possible
Limits the damage from an accident, error, or attack
Reduces number of potential interactions among privileged programs
Unintentional, unwanted, or improper uses of privilege less likely
Extend to the internals of a program: only smallest portion of program which needs those privileges should have them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Economy of mechanism/Simplicity

A

Protection system’s design should be simple and small as possible
“techniques such as line-by-line inspection of software and physical examination of hardware that implements protection mechanisms are necessary. For such techniques to be successful, a small and simple design is essential.‘”
Aka “KISS” principle (``keep it simple, stupid’’)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Open design

A

The protection mechanism must not depend on attacker ignorance
Instead, the mechanism should be public
Depend on secrecy of relatively few (and easily changeable) items like passwords or private keys
An open design makes extensive public scrutiny possible
Makes it possible for users to convince themselves system is adequate
Not realistic to maintain secrecy for distributed system

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

Complete mediation(“Non-bypassable”)

A

Every access attempt must be checked; position the mechanism so it cannot be subverted.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

Fail-safe defaults (e.g., permission-based approach)

A

The default should be denial of service, and the protection scheme should then identify conditions under which access is permitted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Separation of privilege

A

Ideally, access to objects should depend on more than one condition, so that defeating one protection system won’t enable complete access

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

Least common mechanism (“limit shared things”)

A

Minimize the amount and use of shared mechanisms (e.g. use of the /tmp or /var/tmp directories)
Shared objects provide potentially dangerous channels for information flow and unintended interactions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Psychological acceptability / Easy to use

A

The human interface must be designed for ease of use so users will routinely and automatically use the protection mechanisms correctly
Mistakes will be reduced if the security mechanisms closely match the user’s mental image of his or her protection goals

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Minimize “attack surface”

A

Key application of least privilege – no interface, no problem
Do users need direct access to database? Maybe not

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

whitelist

A

narrowly identifies what is allowed; all other things forbidden – do this

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

Blacklist

A

list of what is forbidden (all other things permitted) – do not use blacklists (in general)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

SQL injection vulnerability

A

use prepared statements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

Buffer overflows

A

select languages / libraries to eliminate/reduce risk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

Cross-site scripting

A

encode responses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

Password database?

A

Use salted hashes with key-stretching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

Prevent, detect, contain, respond

A

Prevention best, but attackers resourceful
Also work to detect / contain /respond to reduce damage of successful attack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

assurance case

A

Grounds for justified confidence that a claim has been/will be achieved

Claim(s): Top-level claim(s) for a property of a system or product
Arguments: Systematic argumentation justifying this claim
Evidence/assumptions: evidence & explicit assumptions underlying argument

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

Layered architectures

A

Organized into layers, call down to lower layers
Protocol stacks, application layering (stacks)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

Object-based architectures

A

Objects have methods that are called

64
Q

Resource-centered architectures

A

Huge collection of resources (e.g., REST)

65
Q

Event-based architectures

A

Processes can public & subscribe to notifications

66
Q

Centralized organizations

A

Client-server:
Can assign different parts to client vs. server
Multitiered: Server can be client of another server

67
Q

Decentralized organizations

A

Structured peer-to-peer: nodes organized into a specific topology (“overlay network”)
Unstructured peer-to-peer: Each node maintains ad hoc list of neighbors
Hierarchically organized peer-to-peer – special nodes maintain an index (for searching) or broker

68
Q

Edge server

A

Edge servers placed “at the edge” of network
Clients access Internet through edge servers
Edge servers serve (some) content directly – optimize access
E.g., Content Distribution Networks (CDNs)

69
Q

Collaborative distributed systems

A

Decentralized collaboration (often after client/server startup)

70
Q

Physical mobility vs. code migration

A

Term “mobility” has two meanings
Physical mobility - things move in physical space, so physical location changes
(Logical) code migration, aka “code mobility” or “mobile code” – code to be executed moves from one compute element to another
Both can happen together
From here on, we focus on (logical) code migration

71
Q

Code migration motivation

A

local and remote interaction have different semantics in terms of latency, access to memory, partial failure and concurrency

72
Q

code migration idea

A

distributed systems can dynamically change and move the execution units (software components)

73
Q

Two classes of mobility in code migration

A

Weak mobility
Send some code to be executed remotely, start at “beginning”
Link and execute code downloaded from a remote location
E.g., Java Applets, client-side Javascript. Easier to implement!
Strong mobility
Execution units move among locations carrying their execution state with them (not just “start at the beginning”)
E.g., software agents, virtual machine migration

74
Q

Receiver-initiated

A

Migration initiated by target machine

75
Q

Sender-initiated:

A

Migration initiated by machine where code currently resides or is being executed

76
Q

Why Use Mobile Code?

A

Deployment and upgrade of distributed applications
REV and MA: “maintenance agents” go across the network to detect the current configuration/settings, and remove/install components
COD: lazy and automated propagation of changes

Customization of services
Service interfaces are usually defined statically and a priori
A server can be customized according to the specification of the code sent to it
E.g., sending a Postscript to a printer server

Support for disconnected operations
Code mobility to decrease network traffic, or in anticipation of network disconnection

77
Q

Requirements for Mobility

A

Dynamic Reconfiguration
Adaptivity
Asynchronous Interaction
Context-Awareness
Lightweight Middleware

78
Q

Quality of Service (QoS) often involves tradeoffs

A

sophisticated algorithms over large dictionaries
high quality translation

efficient algorithms over most common instances
fast translation

79
Q

MAPE-K framework

A

MAPE-K loop: Monitoring, Analysis, Planning, and Execution - Knowledge

80
Q

Public key cryptography

A

Every user has a private key and a public key (numbers)
Everyone knows user’s public key
Private key is the user’s secret, never shared with anyone

Public key is uniquely determined by the private key

Virtually impossible to compute private key from public key

Can be used for encryption and digital signatures

81
Q

Digital signatures

A

User wants to send a message and prove that he wrote it

Takes message and private key and performs a computation to create a signature

Recipient compares the signature against the message and the user’s known public key

Only the user who possesses the private key can sign messages, does not need to share the private key

82
Q

Hash functions

A

Takes arbitrary data and transforms it to a 256-bit number
The hash of random data is essentially a random number

83
Q

Bitcoin system components

A

A transaction structure for specifying and changing ownership

A p2p network for propagating, verifying and storing transaction data

A proof-of-work system (hashing, “mining”) for:
Synchronizing transactions
Determining initial distribution of coins

84
Q

Coins (bitcoin)

A

The fundamental building block of Bitcoin is a “coin”
A coin is characterized by:
Unique ID
Quantity (denomination) – arbitrary number with 8 decimal places
Owner

Coins can be split and merged
If Alice wants to send bitcoins to Bob, she will merge some of her coins and split the result between her and Bob

85
Q

Transactions

A

The owner of a coin is identified by an “address”

Each address is associated with a private key

To use a coin, the owner must provide a digital signature with the associated private key (ECDSA)

The process where coins are merged and split is called a “transaction”

86
Q

Transaction structure

A

A transaction can have any number of inputs and outputs
An output specifies a receiving address and amount
An input references a previous unspent output
The total value of all inputs must be at least the total value of all outputs
The transaction is identified by a hash of its data
The hash must be signed by the private key corresponding to every input address
An address is a hash of an ECDSA public key
More generally, an output specifies a script with the conditions to allow spending it

87
Q

Problem: Double spending

A

Using the same output (“coin”) to pay 2 different recipients
No agreement on who is the “true” recipient
One recipient will be out of his coins (presumably after providing some product)
Some way to determine order of transactions is needed

Traditional solution: Central authority

Naïve decentralized solutions have vulnerabilities

The first working decentralized solution is the blockchain

88
Q

Solution: The blockchain

A

Transactions are grouped into blocks
Blocks are confirmed with proof of work
A transaction is considered final if it is included in a confirmed block
Each block references a previous block to form a chain
In case of conflict, the transaction with more compute power spent on confirmation wins
Attacks require having more compute power than the rest of the network

89
Q

Block structure

A

Transactions are organized in a Merkle tree with a resulting root hash

The block header consists of the Merkle root, the hash of the previous block, other metadata, and a nonce

The block is identified by the SHA-256 hash of its header

A block is valid only if its hash is lower than the target

90
Q

Proof of work (block chain)

A

A block with given data and nonce has a very low probability of being valid
Miners try different nonces and compute the resulting hash (billions of tries per second) until they match the target, and release the resulting block
The existence of a block which includes a transaction proves that computational work has been done by a node which considers this transaction valid
Each block references the previous one. Each transaction gets increasingly more powerful proof of work
In case of competing branches, the one with the most proof of work is selected

A transaction “buried” under several blocks is very hard to revert mistakenly or maliciously
Reverting a transaction requires catching up with the computation of the honest network, which is unlikely without greater hashrate
Any change to a transaction invalidates all proof of work
Hash target is adjusted every 2016 blocks (roughly 2 weeks) so that on average one block is found every 10 minutes

91
Q

Creation of coins

A

Every block is allowed one special “generation transaction”
A generation transaction has a single special input, and any number of outputs
Value of input: New coins + tx fees
New coins: 50∙2^(−⌊𝐻/210000⌋ ) (starts at 50 BTC per block and halves roughly once every 4 years)
Incentivizes securing the network by hashing
Robust way to determine initial distribution

92
Q

nodes

A

nodes make up the bitcoin network
anybody can connect to other nodes and download the blockchain
nodes listen to transactions and check if they are valid
valid transactions are forwarded and stored, invalid ones rejected

93
Q

mining

A

take the hash of the previous block and all transactions. guess a random number, hash it.
published with the block to other nodes
the miner is allowed to send themselves 25 bitcoins from nowhere
miners mine at the margin and need to pay electricity, creating a liquid market for bitcoins

94
Q

why are bitcoins valuable?

A

only 21 million will ever be created.
divisible into 100 million satoshis
cannot be easily seized or censored
ignorant to borders or location
transaction clears within 10-60 minutes
programmable and permissionless

95
Q

problems of bitcoin

A

can only handle 7 transactiosn per second

fungibility cannot be guaranteed
unexpected behavior of bitcoin software
information security in a horrible state
minig consumes vast amounts of energy
attractive for criminals
strong fluctuations in value

96
Q

how a blockchain works

A

Although the accepted chain can be considered a list, the block chain is best represented with a tree.
The longest path representsthe accepted chain.
A participant choosing toextend an existing path in the block chain indicates a votetowards consensus on that path. The longer the path, themore computation was expended building it.

97
Q

etherium

A

Contracts are the main building blocks of Ethereum.
A contract is a computer program that lives inside the distributed Ethereum network and has its own ether balance, memory and code.
Every time you send a transaction to a contract, it executes its code, which can store data, send transactions and interact with other contracts.
Contracts are maintained by the network, without any central ownership or control.
Contracts are written in languages instantly familiar to any programmer and powered by Ether, Ethereum’s cryptofuel.

98
Q

Kubernetes (K8s)

A

“a portable, extensible open-source platform
for managing containerized workloads and services,
that facilitates both declarative configuration and automation.”

99
Q

What’s a container?

A

A container image is
“a lightweight, stand-alone, executable package of a piece of software that includes everything needed to run it: code, runtime, system tools, system libraries, settings”*

A container (e.g., as implemented by Docker) is
a (mostly) isolated process running a container image
isolates “software from its surroundings”*

Advantages of containers:
“containerized software will always run the same, regardless of the environment.”*
Faster start & lower resource vs. VMs (shared kernel)

100
Q

Container orchestration engines

A

Kubernetes
Docker Swarm
Apache Mesos

101
Q

Declarative aspect of kubernetics

A

Just declare “what you want”
K8s notices & fixes differences of reality vs. request
Automatically handles computer crashes, etc.

102
Q

K8S Typical assumption: Cattle > Pets

A

Pets: Servers… treated as indispensable or unique systems that can never be down. Typically they are manually built & managed”
“Cattle: Arrays of >2 servers, that are built using automated tools, and are designed for failure, where [no 1..3] are irreplaceable. Typically, during failure events no human intervention is required as the array exhibits attributes of “routing around failures” by restarting failed servers or replicating data…”

103
Q

K8s: Worker-side

A

Worker node, aka node: a VM or physical machine that has the services necessary to run pods and is managed by the K8s master components

104
Q

K8S Pod:

A

group of 1+ containers with shared storage/network & a spec for how to run the containers
Always co-located and co-scheduled, and run in a shared context
Defined by a “Podspec”
An application-specific “logical host” - contains one or more application containers which are relatively tightly coupled
Each pod had its own IP address & runs on a worker node
Routinely destroyed/created (not necessarily same IP address)

105
Q

K8S Kubelet

A

primary “node agent” that runs on each node
takes a set of PodSpecs and ensures that the containers described in those PodSpecs are running and healthy

106
Q

K8s: Master side (top) API server

A

Services REST operations and provides the frontend to the cluster’s shared state through which all other components interact
validates and configures data for the api objects which include pods, services, replicationcontrollers, and others

107
Q

K8S kubectl

A

a command line interface for running commands against Kubernetes clusters

108
Q

K8s controller manager

A

Kubernetes controller manager: “a daemon that embeds the core control loops shipped with Kubernetes”
Control loop = non-terminating loop that regulates the state of the system

109
Q

K8s scheduler

A

schedules pods onto nodes
If a pod hasn’t been assigned a node, assign it
Does not run pods – schedules them to be run

110
Q

K8s key term: etcd

A

“Consistent and highly-available [distributed] key-value store used as Kubernetes’ backing store for all cluster data”
Globally available
Implemented using the Raft algorithm (with some tweaks, discussed later)

111
Q

K8s term: Deployment

A

A deployment = declarative update for Pods and ReplicaSets
Simplified: declare the number of replicas & the template for the pods
Makes it easy to deploy replicas, change # of replicas

112
Q

K8s key term: Service

A

Kubernetes Service: an abstraction which defines a logical set of Pods and a policy by which to access them
sometimes called a micro-service
Set of Pods targeted by a Service is (usually) determined by a Label Selector

113
Q

K8s key term: kube-proxy

A

kube-proxy:
Kubernetes network proxy runs on each node
Reflects services as defined in the Kubernetes API on each node and can do simple TCP and UDP stream forwarding or round robin TCP and UDP forwarding across a set of backends

114
Q

Prometheus

A

Kubernetes is often used with Prometheus
Prometheus = an open-source systems monitoring and alerting toolkit

115
Q

Container formats/standards

A

Docker: Popular container system
There are others (e.g., rkt)
Open Container Initiative (OCI) established by Dockers & others defined 2 specs:
Runtime Specification (runtime-spec): outlines how to run a “filesystem bundle” that is unpacked on disk.
Image Specification (image-spec)
An OCI implementation:
downloads an OCI Image
unpacks it into an OCI Runtime filesystem bundle…
that is run by an OCI Runtime

116
Q

why formal methods

A

FM spec language can reduce requirement ambiguity
FM can prove “always” or “never”

117
Q

Making formal methods affordable

A

Many backoff approaches exist to limit costs. One grouping is:*
Level 0: Formal specification created, then program informally developed from it. “Formal methods lite”
Level 1: Level 0, + prove some select properties or formal refinement from specification towards program
Level 2: Fully prove claims, mechanically checked
Any of the above can apply to a subset of components or properties

118
Q

Predicate logic

A

define expressions with just:
Boolean variables
Operators: and (∧); or (∨); not (¬)
Parentheses allowed
Predicate logic too limited for many problems
Useful in some cases, e.g., dependency analysis
Can be used to implement more sophisticated systems
Provides the basis for FOL & other logic systems

119
Q

First-order logic (FOL)

A

FOL widely used mathematical logic
Aka “first-order predicate logic” or “first-order predicate calculus”
Basis of most FM software languages for specs

In traditional FOL, every expression is either a:
Term (an object / “non-boolean”): a variable, a constant, or a function f(term1, term2, …)
Typically there’s a “domain of discourse” (aka “universe”), the set of entities over which variables may range. E.G., “integers” or “real numbers”
Formula (a truth value / “boolean”): see next slide, includes predicates (“functions” that return truth value)
Can have variables & constants (must distinguish)
Prolog convention: Variable if begin with uppercase, else constant
Math convention: Variables begin with w, x, y, z
In FOL, functions & predicates can’t be variables

120
Q

Higher-order logics (HOL)

A

strongest math notation (+ functions can vary/be objects)
Again, can add “theories” about integers, etc. to HOL

121
Q

Stronger logic notations

A

provide more capability
But tend to be harder to automatically analyze
Often want “weakest” language that meets needs

122
Q

secure software 10 slides 22-23

A

FOL formula notation

123
Q

Quantifiers

A

∀ X expression = “for all”
“Loops” over everything X could be, is true iff the expression is always true for all allowed values of X
∃ X expression = “there exists”
True iff there is some allowed value of X where the expression is true

∀ X (man(X) → mortal(X))
“For all X, if X is a man, then X is mortal”

124
Q

Beware if something can be an empty set – especially with forall!

A

Surprisingly, these can BOTH be true at the SAME time:
∀ X (martian(X) → green(X)) “All Martians are green”
∀ X (martian(X) → ¬green(X)) “All Martians are not green”
Why? If there are no Martians, both expressions are true
martian(X)→… => ¬martian(X) ∨ … => T ∨ … => T
Without Martians they all simplify to ∀ X T, which is true

125
Q

separation logic

A

Extension of Hoare logic developed by John C. Reynolds, Peter O’Hearn, Samin Ishtiaq and Hongseok Yang
Describes “states” consisting of a:
store (“stack-oriented variables”) and a
heap (“dynamically-allocated objects”)
Defines a set of operations about them
“Frame rule” enables local reasoning
A program that executes safely in a small state can also execute in any bigger state and that its execution will not affect the additional part of the state when certain conditions proved
E.G., Coq “Ynot” library implements separation logic
Can apply separation logic concepts using traditional FOL

126
Q

Types of formal methods tools

A

Verification tools
Major verification approaches include:
Theorem-provers: Automated & interactive
Satisfiability (SAT) solvers: Boolean-only or modulo theories
Model-checkers
Abstract interpretation / symbolic execution (for programs)

127
Q

Theorem provers

A

Accepts assumptions (“givens”) & goal in some notation
Tries to produce proof of goal, starting from assumptions…
Using only a sequence of allowed inference rules & theorems

128
Q

Formal proof:

A

Every step fully justified by accepted rule
“Proof checker” can verify proof - easy to build, enabling separate third-party verification. Supports “Proof carrying code”

129
Q

Theorem proving tools may be either:

A

Automated (automatic, but typically only FOL & can fail)
Interactive (“proof assistant”) (requires far more expertise)

130
Q

Boolean satisfiability (SAT) solvers

A

automated tools that:
Given predicate logic expressions (boolean variables, and, or, not)…
Find variable assignments to make true OR report unsatisfiable

131
Q

Satisfiability Modulo Theories (SMT) solvers

A

automated tools
Given expressions in richer notation beyond predicate logic
Typically FOL + “theories” (variables may be integers, reals, etc.)
E.g., (x+y ≥ 0) ∧ (y > 0) is satisfiable with integers x=1,y=2
Reports satisfiable (“sat”) (maybe with satisfying variables) or “unsat” or “unknown” (e.g., ran out of time/memory)
To determine if “X is always true”, supply “not X”… returns unsat
Some can also provide proof (if can’t, how verify results?)

132
Q

Model-checkers (aka property checkers)

A

Given a system model, exhaustively check if meets a given requirement
Requirement is often narrow property, often temporal requirement
System is represented as a finite-state machine (FSM)
Exhaustively explore state (conceptually)
Clever approaches  orders-of-magnitude faster vs. brute force. E.g.:
Symbolically represent FSM, e.g., using binary decision diagrams (BDDs)
Abstraction (simplify system for this specific property)
Bounded model checking - unroll FSM for fixed number of steps (build on SAT)
Only shows true/false for that many steps!!
Counterexample guided abstraction refinement (CEGAR)

133
Q

TLA+

A

“general-purpose formal specification language that is particularly useful for describing concurrent and distributed systems.
The TLA+ proof language is declarative, hierarchical, and scalable to large system specifications. It provides a consistent abstraction over the various “backend” verifiers.”

134
Q

TLA+ Proof System (TLAPS)

A

mechanically checks TLA+ proofs
Copyright Inria and Microsoft Corporation
BSD-style OSS license
By default it tries to prove it using an SMT solver (by default CVC3), Zenon (tableax-based FOL prover), and then Isabelle’s “auto” tactic
Has been used to prove designs of practical systems

135
Q

(Storage Component) Hadoop Distributed File System (HDFS)

A

): A distributed file system that provides high-throughput access
Many other data storage approaches also in use
E.G., Apache Cassandra, Apache Hbase, Apache Accumulo (NSA-contributed)

136
Q

(Scheduling) Hadoop YARN

A

A framework for job scheduling and cluster resource management

137
Q

(Processing) Hadoop MapReduce (MR2)

A

A YARN-based system for parallel processing of large data sets
Other execution engines increasingly in use, e.g., Spark

138
Q

Hadoop HDFS

A

Stores large files (typically gigabytes-terabytes) across multiple machines, replicating across multiple hosts
File system intentionally not fully POSIX-compliant
Write-once-read-many access model for files. A file once created, written, and closed cannot be changed. This assumption simplifies data coherency issues and enables high throughput data access
Intend to add support for appending-writes in the future
Can rename & remove files

139
Q

MapReduce

A

a programming model for processing and generating large data sets with a parallel, distributed algorithm on a cluster

Programmer defines two functions, map & reduce
Map(k1,v1) → list(k2,v2). Takes a series of key/value pairs, processes each, generates zero or more output key/value pairs
Reduce(k2, list (v2)) → list(v3). Executed once for each unique key k2 in the sorted order; iterate through the values associated with that key and produce zero or more outputs

140
Q

MapReduce Combiner

A

If defined, runs after Mapper & before Reducer on every node that has run a map task
Combiner receives as input all data emitted by the Mapper instances on a given node
Combiner output sent to the Reducers, instead of the output from the Mappers
Is a “mini-reduce” process which operates only on data generated by one machine

141
Q

MapReduce problems:

A

Many problems aren’t easily described as map-reduce
Persistence to disk typically slower than in-memory work

142
Q

Apache Spark

A

Processing engine; instead of just “map” and “reduce”, defines a large set of operations (transformations & actions)
Operations can be arbitrarily combined in any order
Open source software
Supports Java, Scala and Python
Original key construct: Resilient Distributed Dataset (RDD)
Original construct, so we’ll focus on that first
More recently added: DataFrames & DataSets
Different APIs for aggregate data

143
Q

Resilient Distributed Dataset (RDD) – key Spark construct

A

RDDs represent data or transformations on data
RDDs can be created from Hadoop InputFormats (such as HDFS files), “parallelize()” datasets, or by transforming other RDDs (you can stack RDDs)
Actions can be applied to RDDs; actions force calculations and return values
Lazy evaluation: Nothing computed until an action requires it
RDDs are best suited for applications that apply the same operation to all elements of a dataset

144
Q

Spark transformation: map(func)

A

: Return a new distributed dataset formed by passing each element of the source through a function func.

145
Q

Spark transformation: filter(func):

A

Return a new dataset formed by selecting those elements of the source on which func returns true
union(otherDataset): Return a new dataset that contains the union of the elements in the source dataset and the argument.

146
Q

Spark transformation: intersection(otherDataset):

A

Return a new RDD that contains the intersection of elements in the source dataset and the argument.

147
Q

Spark transformation: distinct([numTasks])):

A

Return a new dataset that contains the distinct elements of the source dataset

148
Q

Spark transformation: join(otherDataset, [numTasks]):

A

When called on datasets of type (K, V) and (K, W), returns a dataset of (K, (V, W)) pairs with all pairs of elements for each key. Outer joins are supported through leftOuterJoin, rightOuterJoin, and fullOuterJoin.

149
Q

(spark action)reduce(func):

A

Aggregate the elements of the dataset using a function func (which takes two arguments and returns one). The function should be commutative and associative so that it can be computed correctly in parallel.

150
Q

(spark action) collect():

A

Return all the elements of the dataset as an array at the driver program. This is usually useful after a filter or other operation that returns a sufficiently small subset of the data.

151
Q

(spark action) count():

A

Return the number of elements in the dataset

152
Q

Spark – RDD Persistence

A

You can persist (cache) an RDD
When you persist an RDD, each node stores any partitions of it that it computes in memory and reuses them in other actions on that dataset (or datasets derived from it)
Allows future actions to be much faster (often >10x).
Cache is fault-tolerant –
Can manually call unpersist()

153
Q

DataFrame

A

Unlike an RDD, data organized into named columns, e.g. a table in a relational database.
Imposes a structure onto a distributed collection of data, allowing higher-level abstraction

154
Q

Dataset:

A

Extension of DataFrame API which provides type-safe, object-oriented programming interface (compile-time error detection)

155
Q

API distinction: typing

A

Python & R don’t have compile-time type safety checks, so only support DataFrame
Error detection only at runtime
Java & Scala support compile-time type safety checks, so support both DataSet and DataFrame

156
Q

Spark vs. Hadoop MapReduce

A

Performance: Spark normally faster but with caveats
Spark can process data in-memory; Hadoop MapReduce persists back to the disk after a map or reduce action
Spark generally outperforms MapReduce, but it often needs lots of memory to do well; if there are other resource-demanding services or can’t fit in memory, Spark degrades
MapReduce easily runs alongside other services with minor performance differences, & works well with the 1-pass jobs it was designed for
Ease of use: Spark is easier to program
Data processing: Spark more general
Maturity: Spark maturing, Hadoop MapReduce mature

Econ 325 exams (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions