ctfnote
  • /home/ret2basic.eth
  • Game Hacking
    • ✅C++
    • Ghidra
    • Cheat Engine
    • Proxy
    • DLL injection
    • Keygen
    • Aimbot
  • Web3 Security Research
    • 👑Web3 Security Research Trivia
    • ✅Solidity
      • ✅Mastering Ethereum
      • ✅Storage
      • ✅Memory
      • ✅Calldata
      • ✅ABI
    • ✅Foundry
      • ✅Introduction
      • ✅How to Write Basic Tests
      • ✅Set Soliditiy Compiler Version
      • ✅Remappings
      • ✅Auto Format Code
      • ✅Console Log
      • ✅Authentication
      • ✅Error
      • ✅Event
      • ✅Time
      • ✅Send ETH
      • ✅Signature
      • ✅Fork
      • ✅Mint 1 Million DAI on Mainnet Fork
      • ✅FFI
      • ✅Fuzz
      • ✅Invariant Testing - Part 1
      • Invariant Testing - Part 2
      • Invariant Testing - Part 3
      • Differential Test
    • ✅Secureum
      • ✅Epoch 0
        • ✅Slot 1: Ethereum 101
          • ✅Notes
          • ✅Ethereum Whitepaper
          • ✅Extra Study: What happens when you send 1 DAI
          • ✅Quiz
        • ✅Slot 2: Solidity 101
          • ✅Notes
          • ✅OpenZeppelin ERC20
          • ✅OpenZeppelin ERC721
          • ✅OpenZeppelin Ownable
          • ✅OpenZeppelin Pausable
          • ✅OpenZeppelin ReentrancyGuard
          • ✅Quiz
        • ✅Slot 3: Solidity 201
          • ✅Notes
          • ✅OpenZeppelin SafeERC20
          • ✅OpenZeppelin ERC-777
          • ✅OpenZeppelin ERC-1155
          • ✅OpenZeppelin ERC-3156
          • ✅OpenZeppelin - Proxy Upgrade Pattern
          • ✅Quiz
        • ✅Slot 4: Pitfalls and Best Practices 101
          • ✅Notes
          • ✅Intro to Security First Development
          • ✅Quiz
        • ✅Slot 5: Pitfalls and Best Practices 201
          • ✅Notes
          • So you want to use a price oracle
          • The Dangers of Surprising Code
          • ✅Quiz
        • ✅Slot 6: Auditing Techniques & Tools 101
          • ✅Notes
          • ✅Quiz
        • ✅Slot 7: Audit Findings 101
          • Notes
          • ✅Fei Protocol - ConsenSys
          • ✅Uniswap V3 - Trail of Bits
          • ✅Chainlink - Sigma Prime
          • ✅Opyn Gamma - OpenZeppelin
          • ✅Quiz
        • ✅Slot 8: Audit Findings 201
          • Notes
          • 1inch Liquidity - Consensus
          • Original Dollar - Trail of Bits
          • Synthetix EtherCollateral - Sigma Prime
          • Holdefi - OpenZeppelin
          • Quiz
      • ✅Epoch ∞
        • ✅RACE #4 - ERC20 Implementation
        • ✅RACE #5 - ERC1155 Implementation
        • ✅RACE #6 - ERC721 Application
        • ✅RACE #7 - Bored Ape
        • ✅RACE #8 - ERC721 Roles
        • ✅RACE #9 - Proxy
        • ✅RACE #10 - Test Cases
        • ✅RACE #11 - Staking
        • ✅RACE #12 - ERC20 Permit
        • ✅RACE #13 - ERC20 with Callback
        • ✅RACE #14 - Lending
        • ✅RACE #15 - DEX
        • ✅RACE #16 - Flash Loan
        • ✅RACE #17
    • DeFi
      • Glossary
        • TWAP vs. VWAP
        • Tranches
      • DeFi MOOC
        • Lecture 2: Introduction to Blockchain Technologies
        • Lecture 5: DEX
        • Lecture 6: Decentralized Lending
        • Lecture 10: Privacy on the Blockchain
        • Lecture 12: Practical Smart Contract Security
        • Lecture 13: DeFi Security
      • Uniswap V2
      • Compound V3
        • ✅Whitepaper
        • ✅Interacting with Compound
          • ✅Supply and Redeem
          • ✅Borrow and Repay
          • ✅Liquidation
          • ✅Long and Short
        • ✅Interest Model
        • CToken
      • Aave
      • Chainlink
        • ✅Getting Started
        • ✅Data Feeds
        • ✅VRF
      • Optimism
        • Bedrock
      • LayerZero
      • Opensea
        • Seaport
    • EVM
      • ✅Andreas Antonopoulos - The Ethereum Virtual Machine
      • ✅Program The Blockchain - Smart Contract Storage
      • ✅EVM Codes - EVM Playground for Opcodes
      • ✅Fvictorio - EVM Puzzles
      • ✅Daltyboy11 - More EVM Puzzles
      • ✅EVM Through Huff
      • Noxx - EVM Deep Dives
      • ✅Jordan McKinney - EVM Explained
      • Openzepplin - Deconstructing a Solidity Contract
      • Jeancvllr - EVM Assembly
      • Peter Robinson - Solidity to Bytecode, Memory & Storage
      • Marek Kirejczyk - Ethereum Under The Hood
      • ✅Official Solidity Docs
      • Dissecting EVM using go-ethereum Eth client implementation - deliriusz.eth
    • Vulnerabilities
      • Rounding Issues
        • Kyberswap
      • Bridges
      • Governance / Voting Escrows
      • Bizzare Bug Classes
        • TIME - ERC2771Context + Multicall calldata manipulation
    • Fancy Topics
      • Vulnerabilities SoK
        • ✅Demystifying Exploitable Bugs in Smart Contracts
        • Blockchain Hacking Techniques 2022 Top 10 - Todo
      • yAcademy
        • Proxies
          • yAcademy - Proxy Basics
          • yAcademy - Proxies Deep Dive
          • yAcademy - Security Guide to Proxy Vulns
        • defi-fork-bugs
      • Spearbit
        • ✅Community Workshop: Riley Holterhus
        • Economic Security with fmrmf
        • Numerical Analysis for DeFi Audits: A TWAMM Case Study by Kurt Barry
  • Red Teaming
    • ✅Enumeration
      • Service Enumeration
        • SMTP (Port 25)
        • Samba (Port 139, 445)
        • SNMP (Port 161,162,10161,10162)
        • rsync (Port 873)
        • NFS (Port 2049)
        • Apache JServ Protocol (Port 8081)
        • NetBIOS
      • Nmap
      • Gobuster / Feroxbuster / FUFF / Wfuzz
      • Drupal
    • ✅Exploitation
      • Public Exploits
      • PHP Webshells
      • Reverse Shell
      • TTY
      • File Transfer
      • Metasploit
      • Password Spray
    • ✅Buffer Overflow
      • Step 0: Spiking (Optional)
      • Step 1: Fuzzing
      • Step 2: Finding the Offset
      • Step 3: Overwriting the EIP
      • Step 4: Finding Bad Characters
      • Step 5: Finding the Right Module
      • Step 6: Generating Shellcode and Gaining Root
    • ✅Privilege Escalation
      • Linux Privilege Escalation
        • Linux Permissions
        • Manual Enumeration
        • Automated Tools
        • Kernel Exploits
        • Passwords and File Permissions
        • SSH Keys
        • Sudo
        • SUID
        • Capabilities
        • Cron Jobs
        • NFS Root Squashing
        • Docker
        • GNU C Library
        • Exim
        • Linux Privilege Escalation Course Capstone
      • Windows Privilege Escalation
        • Manual Enumeration
        • Automated Tools
        • Kernel Exploits
        • Passwords and Port Forwarding
        • WSL
        • Token Impersonation and Potato Attacks
        • Meterpreter getsystem
        • Runas
        • UAC Bypass
        • Registry
        • Executable Files
        • Startup Applications
        • DLL Hijacking
        • Service Permissions (Paths)
        • CVE-2019-1388
        • HiveNightmare
        • Bypass Space Filter
    • ✅Post Exploitation
      • Linux Post Exploitation
        • Add a User
        • SSH Key
      • Windows Post Exploitation
        • windows-resources
        • Add a User
        • RDP
    • ✅Pivoting
      • Windows: Chisel
      • Linux: sshuttle
    • Active Directory (AD)
      • Initial Compromise
        • HTA Phishing
        • VBA Macro Phishing
        • LLMNR Poisoning
        • SMB Relay
        • GPP / cPassword
      • Domain Enumeration
        • Manual Enumeration
        • PowerView
        • BloodHound
      • Lateral Movement
        • PsExec
        • WMI
        • Runas
        • Pass the Hash
        • Overpass the Hash
        • Pass the Ticket
      • Kerberos
        • Kerberoast
        • AS-REP Roast
      • MS SQL Server
    • Command & Control (C2)
      • Cobalt Strike
        • Bypassing Defences
          • Artifact Kit
          • Resource Kit
          • AMSI Bypass
          • PowerPick
        • Extending Cobalt Strike
          • Elevate Kit
          • Malleable C2 Profile
      • Metasploit
        • Payloads
        • Post Exploitation
        • Automation
      • C2 Development
    • Malware Development
      • "Hot Dropper"
      • PE Format
        • Overview
      • Process Injection
      • Reflective DLL
      • x86 <=> x64
      • Hooking
      • VeraCry
      • Offensive C#
      • AV Evasion
        • AV Evasion with C# and PowerShell
        • AMSI Bypass
  • Cryptography
    • Hash Functions
    • MAC
    • AES
      • Byte at a Time
      • CBC CCA
      • CBC Bit Flipping
      • CBC Padding Oracle
    • Diffie-Hellman
    • RSA
      • Prime Factors
      • Multiple Ciphertexts
      • Low Public Exponent
      • Low Private Exponent
    • ECC
    • Digital Signature
    • JWT
    • PRNG
    • SSL/TLS
    • Research
      • ✅Lattice-based Cryptography (Lattice)
      • Elliptic Curve Cryptography (ECC)
      • Oblivious Transfer (OT)
      • Secure Multi-party Computation (MPC)
      • Learning with Error (LWE)
      • Fully Homomorphic Encryption (FHE)
      • Zero Knowledge Proof (ZKP)
      • Oblivious RAM (ORAM)
  • Computer Science
    • Linux
      • Setup
      • curl
      • Hard Link vs. Symlink
      • Man Page
      • /dev/null
    • Python
      • New Features
      • Operators, Expressions, and Data Manipulation
      • Program Structure and Control Flow
      • Objects, Types, and Protocols
      • Functions 101
      • Generators
      • Classes and Object-Oriented Programming
      • Memory Management
      • Concurrency and Parallelism
        • Multithreading and Thread Safety
        • Asynchronization
        • Multiprocessing
        • Global Interpreter Lock (GIL)
      • Built-in Functions and Standard Library
        • import collections
        • import itertools
        • import sys
        • import re
        • import pickle
        • import json
      • Third-party Library
        • from pwn import *
        • import requests
        • from bs4 import BeautifulSoup
        • from scapy.all import *
        • py2exe
    • HTML, CSS, JavaScript, and React
      • HTML
      • CSS
      • JavaScript
        • var vs. let
        • Objects
        • Arrays
        • Functions
        • Modules
        • Asynchronous JavaScript
      • React
    • Data Structures and Algorithms
      • Binary Search
    • The Linux Programming Interface
      • Processes
        • Memory Allocation
        • The Process API
        • Process Creation
        • Process Termination
        • Monitoring Child Processes
        • Program Execution
      • Signals
      • Threads
        • Thread Synchronization
        • Thread Safety and Pre-Thread Storage
      • IPC
        • Pipes and FIFOs
        • Memory Mappings
        • Virtual Memory Operations
      • Sockets
    • Computer Systems
      • Hexadecimal
      • Signedness
      • Registers
      • Instructions
      • Syscall
      • Process Memory
      • Stack Frame
      • Preemptive Multitasking
      • IPC
      • Threads
    • Databases
      • MySQL
        • Basic Syntax
        • Data Types
        • Modifying Tables
        • Duplicating and Deleting
        • SELECT
        • Transaction
      • GraphQL
    • Distributed Systems
      • Introduction
        • What is a Distributed System?
        • Design Goals
        • Scaling Techniques
        • Types of Distributed Systems
      • Architecture
        • System Architectures
        • Example Architectures
      • Communication
        • Foundations
        • Remote Procedure Call
        • Message-oriented Communication
      • Coordination
        • Clock Synchronization
        • Logical Clock
      • Consistency and Replication
        • Introduction
        • Data-centric Consistency
        • Client-centric Consistency
    • Static Analysis
      • Intermediate Representation
      • Data Flow Analysis
      • Interprocedural Analysis
      • Pointer Analysis
      • Static Analysis for Security
      • Datalog-Based Program Analysis
      • Soundness and Soundiness
      • CFL-Reachability and IFDS
  • Web
    • ✅Prerequisites
      • OWASP Top 10
        • 1. Broken Access Control
        • 2. Cryptographic Failures
        • 3. Injection
        • 4. Insecure Design
        • 5. Security Misconfiguration
        • 6. Vulnerable and Outdated Components
        • 7. Identification and Authentication Failures
        • 8. Software and Data Integrity Failures
        • 9. Security Logging and Monitoring Failures
        • 10. SSRF
      • HTTP
        • HTTP Status Codes
        • HTTP Headers
      • Burp Suite
        • Burp Intruder
        • Burp Extender
        • Burp Collaborator
      • Information Gathering
        • DNS
        • Git
        • Editor
        • Server
      • Bug Bounty Report Writing
    • File Upload
      • Webshell
      • IIS, Nginx, and Apache Vulnerabilities
      • .htaccess (Apache) / web.config (IIS)
      • Alternate Data Stream
      • Code Review: bWAPP Unrestricted File Upload
    • SQL Injection (SQLi)
      • Cheat Sheet
      • UNION Attacks
      • Examining the Database
      • Blind SQL Injection
      • WAF Bypass
      • Out-Of-Band (OOB)
      • Webshell and UDF
      • sqlmap
        • Code Review: Initialization
        • Code Review: tamper
    • Cross-Site Scripting (XSS)
      • Cheat Sheet
      • Reflected XSS
      • Stored XSS
      • DOM-Based XSS
      • XSS Contexts
      • CSP
    • CSRF and SSRF
      • Client-Side Request Forgery (CSRF)
        • XSS vs. CSRF
        • CSRF Tokens and SameSite Cookies
      • Server-Side Request Forgery (SSRF)
        • Attacks
        • Bypassing Restrictions
        • SSRF + Redis
    • XML External Entities (XXE)
    • Insecure Deserialization
      • Python Deserialization
      • PHP Deserialization
      • Java Deserialization
        • Shiro
        • FastJSON
        • WebLogic
    • HTTP Request Smuggling
    • OS Command Injection
      • Whitespace Bypass
      • Blacklist Bypass
      • Blind OS Command Injection
      • Lab 1: HITCON 2015 BabyFirst
      • Lab 2: HITCON 2017 BabyFirst Revenge
      • Lab 3: HITCON 2017 BabyFirst Revenge v2
    • ✅Directory Traversal
    • HTTP Parameter Pollution
    • Server-Side Template Injection (SSTI)
    • LDAP Injection
    • Redis
      • Authentication
      • RCE
      • Mitigations
  • Pwn
    • Linux Exploitation
      • Protections
      • Shellcoding
        • Calling Convention
        • Null-free
        • Reverse Shell
        • ORW
      • ROP
        • Stack Alignment
        • ret2text
        • ret2syscall
        • ret2libc
        • ret2csu
        • BROP
        • SROP
        • Stack Pivot
      • ptmalloc
        • chunks
        • malloc() and free()
        • bins
        • tcache
      • UAF
      • Race Conditions
        • TOCTTOU
        • Dirty Cow
        • Meltdown
        • Spectre
      • Kernel
      • Appendix: Tools
        • socat
        • LibcSearcher-ng
        • OneGadget
    • Windows Exploitation
      • Classic
      • SEH
      • Egghunting
      • Unicode
      • Shellcoding
      • ROP
      • Appendix: Tools
        • ImmunityDbg
        • Mona.py
    • Fuzzing
      • AFL++
        • Quickstart
        • Instrumentation
        • ASAN
        • Code Coverage
        • Dictionary
        • Parallelization
        • Partial Instrumentation
        • QEMU Mode
        • afl-libprotobuf-mutator
      • WinAFL
      • Fuzzilli
  • Reverse
    • Bytecode
      • Python Bytecode
    • 👑Z3 solver
    • angr
      • angr Template
Powered by GitBook
On this page
  • Idea
  • Happens-before
  • Logical Time
  • Lamport's Algorithm
  • Example: Total-ordered Multicasting

Was this helpful?

  1. Computer Science
  2. Distributed Systems
  3. Coordination

Logical Clock

PreviousClock SynchronizationNextConsistency and Replication

Last updated 3 years ago

Was this helpful?

Idea

  • In a seminal paper, Lamport showed that although clock synchronization is possible, it need not be absolute.

  • If two processes do not interact, it is not necessary that their clocks be synchronized.

  • What usually matters is not that all processes agree on exactly what time it is, but rather that they agree on the order in which events occur.

Happens-before

  • a→ba \rightarrow ba→b is read "event aaa happens before event bbb".

    • It means that all processes agree that first event aaa occurs, then afterward, event bbb occurs.

  • The happens-before relation can be observed directly in two situations:

    • If aaa and bbb are events in the same process, and aaa occurs before bbb, then a→ba \rightarrow ba→b is true.

    • If aaa is the event of a message being sent by one process, and bbb is the event of the message being received by another process, then a→ba \rightarrow ba→b is also true. A message cannot be received before it is sent, or even at the same time it is sent, since it takes a finite, nonzero amount of time to arrive.

  • Happens-before is a transitive relation

    • If a→ba \rightarrow ba→b and b→cb \rightarrow cb→c, then a→ca \rightarrow ca→c.

  • If two events, xxx and yyy, happen in different processes that do not exchange messages (not even indirectly via third parties), then x→yx \rightarrow yx→y is not true, but neither is y→xy \rightarrow xy→x

    • These events are said to be concurrent, which simply means that nothing can be said (or need be said) about when the events happended or which event happended first.

Logical Time

    • Corrections to time can be made by adding a positive value, never by subtracting one.

Lamport's Algorithm

  • Time only moves forward.

  • If a message was sent at time 60 but received at time 56, the receiver's clock must be adjusted.

Example: Total-ordered Multicasting

  • For example, to improve query performance, a bank may place copies of an account database in two different cities, say New York and San Francisco.

  • A query is always forwarded to the nearest copy.

  • Each update operation must be carried out at each replica.

  • But we must solve the inconsistent update problem.

    • Assume a customer in San Francisco wants to add $100 to his account, which currently contains $1,000.

    • At the same time, a bank employee in New York initiates an update by which the customer's account is to be increased with 1 percent interest.

    • Now we have two updates: "deposit" (update 1) and "interest" (update 2).

    • If "deposit" is carried out before "interest", the account total becomes $1,111; if "interest" is carried out before "deposit", the account total becomes $1,110.

    • Consequently, the San Francisco database will record a total amount of $1,111, whereas the New York database records $1,110.

  • The important issue is that both copies should be exactly the same.

  • In general, situations such as these require a total-ordered multicast, that is, a multicast operation by which all messages are delivered in the same order to each receiver.

  • Lamport's logical clocks can be used to implement total-ordered multicasts in a completely distributed fashion.

    • When a process receives a message:

      • It puts the message in a local queue, ordered by its timestamp.

      • It multicasts an acknowledgement to the other processes.

    • A process delivers a queued message to its application

      • Only when that message is at the head of the queue and has been acknowledged by each other process.

      • All processes have the same copy of the local queue, and all messages are delivered in the same order everywhere.

Let C(a)C(a)C(a) be the logical time of an event a (that all processes agree).

If a→ba \rightarrow ba→b, then C(a)<C(b)C(a) < C(b)C(a)<C(b).

The clock time, CCC, must always go forward (increasing), never backward (decreasing).

To implement Lamport's logical clocks, each process PiP_iPi​ maintains a local counter CiC_iCi​.

Before executing an event (i.e., sending a message over the network, delivering a message to an application, or some other internal event), PiP_iPi​ does C_i += 1.

When process PiP_iPi​ sends a message mmm to process PjP_jPj​, it sets mmm's timestamp ts(m) = C_i after having executed the previous step.

Upon the receipt of a message mmm, process PjP_jPj​ adjusts its own local counter as C_j = max(C_j, ts(m)) after which it then executes the first step and delivers the message to the application.