Notes.pdf

🗒️ Notes Blockchain (Intro) Decentralised Applications Features Deterministic Algorithms Non-Deterministic Algorithms Cryptography Hash Function Hashing Algorithms Immutability Multithreading...

🗒️ Notes Blockchain (Intro) Decentralised Applications Features Deterministic Algorithms Non-Deterministic Algorithms Cryptography Hash Function Hashing Algorithms Immutability Multithreading Threads and Processes Why Threads? Pros and Cons Parallelism with Multithreading High Performance Computing Blockchain (Intro) provides coordination between many parties when there is no single trusted party append only smart contracts e.g., for cryptocurrencies like Bitcoin Notes 1  Coin Demo A visual demo of cryptocurrency technology. https://coindemo.io/ Decentralised Applications decentralised finance (DeFi) managed through public, transparent programs (e.g., Stablecoins, lending platforms) asset management (NFTs) tokenised assets like art etc. decentralised autonomous organisations (DAOs) decentralised governance - groups managing funds / decisions collectively (e.g., for investments, donations, art collections) new programming model - enables writing decentralised programs, offering new ways to develop apps Features concurrency - many participants can perform transactions concurrently immutability - once transaction added to blockchain, cannot be changed distributed systems network of independent nodes where each node has copy of entire blockchain, no single point of failure, robust against attack Deterministic Algorithms same input → same output Notes 2  same sequence of steps behaviour + outcome predictable predictable - execution path always the same efficient execution - easier to analyse + debug time & space needed known e.g., binary search Non-Deterministic Algorithms same input → multiple potential outputs different choices during execution explore multiple paths at same time randomness in decisions non-predictable theoretical model - try all possible solutions in parallel (theoretically) implementation with randomness - non-determinism can be simulated using randomness can use constraints to convert ND problem to become deterministic - becomes combinatorial problem lab week 2 solution space much smaller through constraints and parallel time & space needed unknown don't know exactly what optimal solution is - will try many e.g., 8 queens puzzle - many valid board configs, travelling salesman problem e.g., ChatGPT Notes 3  💡 Quicksort is both because - final result is the same (D) but pivot varies (ND) - determinant non-deterministic Cryptography public/private key cryptography - allows 2 parties to exchange encrypted info digital signatures - can use public key cryptography to prove doc/email came from certain person ✅ Hash Function mathematical operation - takes an item and reduces it to a number given a string/int/… input, returns a corresponding hash value can use hash of a file to verify its contents secure against unauthorised modifications - data integrity 🔒 verify and securely store passwords 🔑 verify data blocks in cryptocurrencies & other blockchain technologies - all hashes change if any change made so fraud detectable operate at different speeds to suit different purposes 🚅 Properties Notes 4  Deterministic - same input → same hash any difference in inputs → different hash should produce uniform distribution of values shouldn’t have too many inputs that generate same hash 👉 2 different items can result in the same hash (collision) - infinitely many items, only so many possible hashes with limited number of bit irreversible 🚫 has fixed length output 📏 💡 hashing algorithm is deterministic, but hash itself is non-deterministic Hashing Algorithms Secure Hash Algorithm (SHA) - e.g., SHA-256 Message Digest (MD) - e.g.. MD5 Windows NTHash - aka Unicode hash or NTLM Immutability not able to change TODO references in slides for ideas for article, and sample articles (tone etc.) Multithreading Motivations execute different functions concurrently from same app Notes 5  multiple tabs in browser with video, audio, etc. word processor - async spell check, conversion to PDF browser, word processor etc. running at same time Threads and Processes sequential program has single thread of execution called a process concurrent program has multiple threads of control executed as parallel processes Thread independent execution sequence within single process OS & programming languages allow processes to run 2+ functions simultaneously via threading stack segment subdivided into miniature stacks, 1 per thread thread manager switches between threads each thread has own stack, PC, registers threads share same address space - text, data, heap segments (OS scheduler switches between processes) switching between threads has less overhead than switching between processes Notes 6  Why Threads? need many computing entities to exploit features of multiprocessors so can assign tasks to each can execute in parallel on multiprocessors switching between processes has higher overhead vs. threads app can avoid per-process overheads thread creation, deletion, switching cheaper than for processes threads have full access to address space = easy sharing good for speeding up, finding more (optimal) solutions threads = lightweight processes all data except stack and registers shared between threads context switch between 2 threads in same process less costly than switch between 2 processes Pros and Cons 🟢 Pro: easier to support communications between threads (run in same virtual address space) Notes 7  🔴 Con: no memory protection as virtual memory space shared 🔴 Con: race conditions + deadlock threats must be mitigated debugging can be difficult bugs hard to reproduce as thread scheduling not predictable 🟢🔴 Pro & Con: 1 thread can share its stack space via pointer with others 💡 1 process can contain many threads 💡 4 CPUs = only 4 processes at once process has data, code, descriptor. Can have many threads, each of which has its own stack and descriptor. Parallelism with Multithreading multithreaded programs can have several threads running through different code paths at same time in multithreaded process, 0 or more threads threads may be running at same time machine with n CPUs cannot run more than n threads in parallel Notes 8  concurrent programs give effect of parallelism on single core system by sharing CPU among threads (i.e., CPU rapid switching between threads) - called interleaving divide and conquer High Performance Computing accelerated computing AI training (deep learning, computer vision) big data analytics (image processing) submit job? CSIS GPU can run up to 7 different processes in parallel, assuming 7 independent tasks server can be used for training models for FYP use SSH and FTP Notes 9  don’t need to actually understand this, just an example of where parallel computation can be applied αincreases penalty so system learns faster our job is to find the optimal value of α 1. split dataset into training & testing sets to evaluate model’s performance on test data 2. train multiple models with different values of α 3. for each α, fit model on training data and predict test data 4. calculate error for each to quantify performance 1 is sequential, blocks of 2, 3, 4 can be run in parallel See lecture SEQUANTIAL_VS_PARALLEL.pdf for Python implementation Execution 1 is sequential Execution 2 is concurrent Execution 3 is parallel 💡 Concurrently looks like in parallel but really just switching between different tasks very often for input/output processes, use concurrency for running independent things in parallel, use parallelism Notes 10 Notes 11 Notes 12