Home

Rational Agent Agent An entity that perceives and acts Anything that can be viewed as perceiving its environment through sensors; acting upon that environment through actuators. Agent function A function from percept histories to actions, i.e., $f: P^* \rightarrow A$ Agent program Runs on the physical architecture to perform $f$ agent = ...

Synchronization Primitives Why do we need synchronization primitives? To deal with busy wait problem Synchronization Primitives OS-level APIs that the program may call Semaphores Monitors Semaphores Internally, each semaphores has A boolean value - initially true A queue of blocked processes - initially empty P(): if (value ...

417. Pacific Atlantic Water Flow Solutions Search from sea to see which tile can be achieved by both sea.

Mutual Exclusion Problem Context: Shared memory systems Multi-processor computers Multi-threaded programs Critical Section A section of the code that needs to be executed atomically. A common means for unrelated object to communicate with each other. RequestCS + ReleaseCS Why do we need software solutions? Locking is in OS level, i...

Model Interleaving Model of Computation Assuming the all events are instantaneous, that no two events are simultaneous, and that a shared physical clock is available, we can totally order all the events in the system. Logical clock A mechanism to generate a total order that could have happened in the system Distributed computation A glo...

Causal Order If s1 happened before s2, and r1 and r2 are on the same process, then r1 must be before r2 If on different process, then don’t care Causal Ordering Protocol Each process maintains n by n matrix M This is not the matrix clock M[i, j]: # of messages sent from i to j, as known by process i If process i send a messag...

Global Snapshot Definition An algorithm that captures a global state is called a global snapshot algorithm Goal Take a snapshot of the global computation Difficulties No process has access to the global state of the system Time-Based Model A snapshot of local states on n processes taken at exactly the same time Happened-Before Model A ...

Consistency Correctness conditions of executions Which behaviors are correct when multiple processes invoke methods concurrently on a shared object Current object Allows multiple processes to execute its operations concurrently Consistency Consistency specifies what behavior is allowed when a shared object is accesses by multiple processes...