- Independent entities cooperating to solve big problems.
- Key points:
- Even if one entity fails, work can still happen.
- Entities communicate through messages over a network, not sharing memory or time.
- Appears as one big entity to users.
- it can be loosely coupled, or tight coupled depends upon the architecture
- No shared clock
- No Shared Memory
- Geographical separation.( we can run node in any country,city etc , distance doesn't matter )
- Autonomy and heterogeneity: Entities are loosely connected, with different speeds and operating systems, cooperating by offering services or solving problems together.
- Resource sharing.
- Access to geographically remote data and resources.
- Enhanced reliability: Ensures availability, integrity, and fault-tolerance.
- Increased performance/cost ratio: Achieved through resource sharing and remote data access.
- Scalability.
- Modularity and incremental expandability.
Blocking/Non-blocking, Synchronous/Asynchronous Primitives:
-
Blocking: Control returns after the operation completes.
- Example: A blocking Send() or Receive() halts the process until the action is finished.
-
Non-blocking: Control returns immediately after invocation, allowing the process to proceed without waiting for the operation to complete.
- Example: A non-blocking Send() allows the process to continue while the data is still being transmitted.
-
Synchronous: Send and Receive operations handshake, with each step waiting for the previous one to complete.
-
Asynchronous: Actions occur independently and do not wait for each other.
Buffered vs. Unbuffered Options:
- Buffered:
- Data is first copied from the user buffer to a kernel buffer, then to the network.
- Buffered Receive ensures data has a storage place in the kernel if it arrives before the Receive() is invoked.
- Unbuffered:
- Data is copied directly from the user buffer to the network.
Send():
- Parameters: destination, user buffer.
Receive():
- Parameters: source, user buffer.
Completion Checking for Non-blocking Primitives:
- Polling: Continuously check if the handle is flagged.
- Wait Call: Blocks until one of the handles is posted.
- Wait Call Behavior:
- Blocks if the primitive hasn't completed.
- Returns immediately if the primitive has completed.
- Communication subsystem sets handle value and signals process on completion.
Processor Synchrony:
- In distributed systems, complete synchrony is impractical; synchronization occurs at larger code steps.
- Barrier Synchronization: Ensures no processor proceeds to the next code step until all have completed the previous one.
Libraries and Standards:
- Tools and guidelines to facilitate communication between distributed entities, ensuring consistency and understanding.
- Examples include MPI (Message Passing Interface) and PVM (Parallel Virtual Machine).
-
Communication:
- Designing communication methods like remote procedure call (RPC) and message-oriented communication.
-
Processes:
- Managing processes and threads, code migration, and software design.
-
Naming:
- Creating robust naming schemes for locating resources and processes transparently.
-
Synchronization:
- Ensuring coordination among processes, including mutual exclusion and clock synchronization.
-
Data Storage and Access:
- Developing efficient data storage and access schemes across the network.
-
Consistency and Replication:
- Replicating data for scalability and fast access while ensuring consistency.
-
Fault Tolerance:
- Maintaining operation despite failures through resilience mechanisms.
-
Security:
- Addressing security aspects like cryptography and access control.
-
API and Transparency:
-
Providing transparent access to system resources and locations.
-
Transparency:
- Hides implementation details from users.
- Types of transparency include:
- Access Transparency: Uniform access to resources despite differences in data representation.
- Location Transparency: Resources' locations are transparent to users.
- Migration Transparency: Relocating resources without altering names.
- Relocation Transparency: Relocating resources during access.
- Replication Transparency: Users unaware of data replication.
- Concurrency Transparency: Masks concurrent resource use.
- Failure Transparency: Ensures reliability and fault tolerance.
-
-
Scalability and Modularity:
- Distributing algorithms, data, and services for scalability using techniques like replication and caching.
-
Execution Models and Frameworks:
- Interleaving and partial order models for system executions and algorithm design.
-
Dynamic Distributed Graph Algorithms:
- Modeling distributed systems as graphs and designing algorithms for communication, data dissemination, and object management.
-
Time and Global State:
- Challenges in providing accurate physical time and logical time for distributed systems.
-
Synchronization/Coordination Mechanisms:
- Essential for overcoming limited observation of system state and enabling impactful actions.
-
Group Communication and Message Delivery:
- Efficient algorithms for dynamic group management and ordered message delivery.
-
Monitoring Distributed Events and Predicates:
- On-line algorithms for monitoring global system state conditions.
-
Program Design and Verification Tools:
- Designing tools for methodical program design and verification.
-
Debugging Distributed Programs:
- Challenges in debugging due to concurrency and uncertainty.
-
Data Replication, Consistency, and Caching:
- Managing replicated data for fast access while ensuring consistency and addressing placement challenges.
1. Mobile Systems
- Wireless Communication: Shared broadcast medium.
- Challenges: Routing, location management, channel allocation, localization, mobility management.
- Architectures:
- Base-station (cellular) approach
- Ad-hoc network approach
2. Sensor Networks
- Function: Sense physical parameters.
- Characteristics: Mobile/static, wireless/wired communication.
- Challenges: Self-configuration, position and time estimation.
3. Ubiquitous or Pervasive Computing
- Examples: Intelligent homes, smart workplaces.
- Features: Self-organizing, network-centric, resource-constrained, connected to powerful networks.
4. Peer-to-Peer (P2P) Computing
- Definition: Peer-level interactions without hierarchy.
- Characteristics: Self-organizing, no central directories.
5. Publish-Subscribe, Content Distribution, and Multimedia
- Dynamic Info Distribution: Efficient publishing, subscribing, and filtering.
- Multimedia Challenges: Large data sizes, compression, synchronization.
6. Distributed Agents
- Functions: Collect, process, exchange information.
- Interactions: Cooperative or competitive.
- Challenges: Coordination, mobility control, software design.
7. Distributed Data Mining
- Scenarios: Private, sensitive data (banking); massive datasets (weather prediction).
- Challenges: Data cannot be centralized; needs distributed processing.
8. Grid Computing
- Definition: Virtual supercomputer using network-connected machines.
- Challenges: Job scheduling, quality of service, security.
9. Security in Distributed Systems
- Challenges: Confidentiality, authentication, availability.
- Goal: Efficient, scalable security solutions.
Overview:
- Structure: Set of processors connected by a communication network.
- Communication: Via message passing; no shared global memory.
- Delay: Finite but unpredictable communication delays.
- Clock: No global clock; processes have no instantaneous clock access.
- Challenges: Out-of-order messages, message loss, duplication, processor/link failures.
- Graph Model: Processes are vertices; communication channels are directed edges.
Distributed Programs:
- Composition: Consist of
nasynchronous processes (p1, p2, ..., pn) on different processors. - Channels:
Cijis the channel from processpitopj. - Messages:
mijdenotes a message frompitopj. - Execution: Asynchronous, with processes executing actions and sending messages independently.
Global State:
- Components: States of processes and communication channels.
- Process State: Defined by local memory state.
- Channel State: Defined by messages in transit.
Execution Model:
- Process Execution: Sequential execution of actions.
- Types of Events:
- Internal events
- Message send events
- Message receive events
- Event Effects: Change states of processes and channels.
- Internal event: Changes state of the process.
- Send/Receive event: Changes state of both the process and the channel.
Event Ordering:
- Events at a process are linearly ordered by occurrence.
Execution and Events:
- Distributed application execution produces a set of events
H = ∪i hi. -
- Causal Dependencies: Defined by a binary relation
→onH.
Causal Precedence (→):
- Irreflexive Partial Order: Induces a partial order on events.
- Lamport's "Happens Before": If
ei → ej, thenejdepends onei.- Direct/Transitive Dependency:
ejis dependent oneithrough a path of messages and process executions. - Flow of Information: All information at
eiis accessible atej.
- Direct/Transitive Dependency:
Implications of Causal Precedence:
- If
ei → ej, theneiaffectsej, andejis aware ofei. - If
eiandejare not related by→:ejdoes not depend onei.ejis not aware ofeior subsequent events on the same process.
Concurrency (||):
- Definition: If
ei → ejandej → ei, theneiandejare concurrent, denoted asei || ej. - Non-transitivity:
||is not a transitive relation. - Event Relationship: For any events
eiandej:- Either
ei → ej - Or
ej → ei - Or
ei || ej
- Either
Logical Concurrency:
- Definition: Two events are logically concurrent if they do not causally affect each other.
- Independence: These events can occur independently without influencing each other's outcome.
- Example: Events
eiandejare logically concurrent if neitherei → ej(ei happens before ej) norej → ei(ej happens before ei). This meanseidoes not happen beforeejandejdoes not happen beforeei.
Physical Concurrency:
- Definition: Events occur at the same instant in physical time.
- Synchronization: Actual simultaneous occurrence in the physical timeline.
Distinguishing Features:
- Temporal Independence: Logically concurrent events do not have to occur simultaneously in physical time.
- Outcome Consistency: The outcome of computation is unaffected by whether logically concurrent events happen at the same physical instant or not.
- Processor Speed and Delays: Variations in processor speed and message delays could make logically concurrent events overlap in physical time.
Key Point:
- Logically concurrent events remain consistent in their outcome regardless of their physical timing, highlighting their independence in logical ordering.
FIFO (First-In, First-Out):
- Description: Channels act as queues, preserving message order.
- Property: Messages are received in the order they were sent.
Non-FIFO:
- Description: Channels act like sets, where messages can be received in any order.
- Property: Message order is not preserved.
Causal Ordering:
- Description: Based on Lamport’s “happens before” relation.
- Property: Causally related messages are delivered in an order consistent with their causal relationships.
- Usefulness:
- Simplifies distributed algorithm design by providing built-in synchronization.
- Ensures consistency in replicated database systems by maintaining the order of updates.
Examples:
- Replicated Databases: Ensures all replicas receive updates in the same order, maintaining consistency without extra checks.
Definition:
- Global State: Collection of local states of processes and communication channels.
- Local State: Defined by process internals; channel state by message transit.
- State Transitions: Events change process and channel states.
-
Consistency:
- Consistent Global State: All received messages are recorded as sent, maintaining causality.
- Inconsistent Global State: Violation of causality; some messages received without being sent.
Definition:
- Cut: Zigzag line joining arbitrary points on each process line in a space–time diagram.
- PAST and FUTURE: Divides events into PAST (left) and FUTURE (right) of the cut.
-
Notation:
$( PAST(C) )$ and$( FUTURE(C) )$ denote events in the PAST and FUTURE of cut$( C )$ . - Global State Representation: Every cut corresponds to a global state graphically.
Consistency:
- Consistent Cut: Every received message in the PAST was sent in the PAST.
- All messages crossing from PAST to FUTURE are in transit.
- Inconsistent Cut: Message crosses from FUTURE to PAST, violating causality.
Example:
- C1: Inconsistent cut.
- C2: Consistent cut.
Past and Future Cones:
-
Definition: Events in PAST of
$( e_j )$ are those that causally affect$( e_j )$ . -
Notation:
$( Past(e_j) )$ denotes events in the past of$( e_j )$ in a computation$( (H, \rightarrow) )$ . -



