article

Free access

Capability-based addressing

Author:

R. S. FabryAuthors Info & Claims

Communications of the ACM, Volume 17, Issue 7

Pages 403 - 412

https://doi.org/10.1145/361011.361070

Published: 01 July 1974 Publication History

Abstract

Various addressing schemes making use of segment tables are examined. The inadequacies of these schemes when dealing with shared addresses are explained. These inadequacies are traced to the lack of an efficient absolute address for objects in these systems. The direct use of a capability as an address is shown to overcome these difficulties because it provides the needed absolute address. Implementation of capability-based addressing is discussed. It is predicted that the use of tags to identify capabilities will dominate. A hardware address translation scheme which never requires the modification of the representation of capabilities is suggested. The scheme uses a main memory hash table for obtaining a segment's location in main memory given its unique code. The hash table is avoided for recently accessed segments by means of a set of associative registers. A computer using capability-based addressing may be substantially superior to present systems on the basis of protection, simplicity of programming conventions, and efficient implementation.

References

[1]

Arden, B.W., Galler, B.A., O'Brien, T.C., and Westervelt, F.H. Program and addressing structure in a time-sharing environment. J. ACM 13, 1 (Jan. 1966), 1-16.]]

Digital Library

[2]

Batson, A., et al. Measurements of segment size. Proc. 3rd Syrup. on Operating Systems Principles. Stanford U., Oct. 1971, 25-29.]]

Digital Library

[3]

Bensoussan, A., Clingen, C.T., and Daley, R.C. The MULTICS virtual memory: concepts and design. Comm. ACM 15, 5 (May 1972), 308-318.]]

Digital Library

[4]

Berry, D.M. Introduction to Oregano. In J. Tou and P. Wegner (Eds.). Sigplan Notices--Proc. Symposium on Data Structures in Programming Languages, Vol. 6, No. 2, Feb. 1971, pp. 171-190.]]

Digital Library

[5]

Bobrow, D.G., and Wegbreit, B. A model and stack implementation of multiple environments. Comm. ACM 16, l0 (Oct. 1973), 591-603.]]

Digital Library

[6]

Burroughs Corporation. Burroughs B5500 Information processing systems reference manual. Detroit, Mich., 1964.]]

[7]

Burroughs Corporation. The descriptor--a definition of the B5000 information processing system. Detroit, Mich., 1961.]]

[8]

Cleary, J.G. Process handling on Burroughs B6500. Proc. Fourth Australian Comp. Conf., Adelaide, South Australia, 1969, pp. 231-239.]]

[9]

Cosserat, D.C. A capability oriented multi-processor system for real-time applications. Presented at the I.C.C. Conf., Washington, D.C., Oct. 1972, 8 pp.]]

[10]

Cotton, J.M. The operational requirements for future communications control processors. Presented at lnternat. Switching Symp., Cambridge, Mass., June 6-9, 1972, 5 pp.]]

[11]

Daley, R.C., and Dennis, J.B. Virtual memory, processes, and sharing in MULTICS. Comm. ACM l I, 5 (May 1968), 306-313.]]

Digital Library

[12]

Daley, R.C., and Neumann, P.G. A general purpose file system for secondary storage. Proc. AFIPS 1965 FJCC, Vol. 27, Pt. I., AFIPS Press, Montvale, N.J., pp. 213-230.]]

[13]

Dennis, J.B. Programming generality, parallelism and computer architecture. Proc. IFIP 1968, North Holland, Amsterdam, pp. CI-7.]]

[14]

Dennis, J.B. Segmentation and the design of multiprogrammed computer systems. J. ACM 12, 4 (Oct. 1965), 589-602.]]

Digital Library

[15]

Dennis, J.B., and Van Horn, E.C. Programming semantics for multiprogrammed computations. Comm. ACM 9, 3 (Mar. 1966), 143-155.]]

Digital Library

[16]

England, D.M. Architectural features of System 250. In Infotech State of the Art Report or Operating Systems, 1972, 12 pp.]]

[17]

England, D.M. Operating System of System 250. Presented at Internat. Switching Symp., Cambridge, Mass., June 6-9, 1972, 5 pp.]]

[18]

Evans, D.C., and LeClerc, J.Y. Address mapping and the control of access in an interactive computer. Proc. AFIPS 1967 SJCC, Vol. 30, AFIPS Press, Montvale, N.J., pp. 23-32.]]

[19]

Fabry, R.S. A user's view of capabilities. ICR Quart. Rep. 15 (Nov. 1967), ICR, U. of Chicago, Sec. IC.]]

[20]

Fabry, R.S. Preliminary description of a supervisor for a machine oriented around capabilities. ICR Quart. Rep. 18 (Aug. 1968), ICR, U. of Chicago, Sec. lB.]]

[21]

Fabry, R.S. List-structured addressing. Ph.D. Th., U. of Chicago, 1971.]]

[22]

Feustal, E.A. The Rice research computer--a tagged architecture. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J. pp. 369-377.]]

[23]

Feustal, E.A. On time advantages of tagged architecture. IEEE Trans. on Computers C-22, 7 (July 1973), 644-656.]]

Digital Library

[24]

Graham, G.S., and Denning, P.J. Protection--principles and practice. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J., pp. 417-429.]]

[25]

Halton, D. Hardware of the System 250 for communication control. Presented at the lnternat. Switching Syrup., Cambridge, Mass., June 6-9, 1972, 7 pp.]]

[26]

Hamer-Hodges, K.J. Fault resistance and recovery within System 250. Presented at I.C.C. Conf., Washington, D.C., Oct. 1972, 6 pp.]]

[27]

Iliffe, J.K. Basic maehhw principles. American Elsevier, New York, 1968.]]

[28]

Iliffe, J.K., and Jodeit, J.G. A dynamic storage allocation scheme. Comput. J. 5 (Oct. 1962), 200-209.]]

[29]

Jones, A.K. Protection structures. Ph.D. Th., Carnegie- Mellon U., 1973.]]

[30]

Lampson, B.W. On reliable and extendable operating systems. In Techniques in Software Engineering, NATO Science Committee Workshop Material, Vol. 11, Sept. 1969.]]

[31]

Lampson, B.W. Dynamic protection structures. Proc. AFIPS 1969 FJCC, Vol. 35, AFIPS Press, Montvale, N.J., pp. 27-38.]]

[32]

Lampson, B.W. Protection. Proc. 5th Ann. Princeton Conf., Princeton U., Mar. 1971, pp. 437-443.]]

[33]

LeClerc, J.Y. Memory structures for interactive computers. Project GENIE document No. 40.10.110, U. of California, Berkeley, 1966.]]

Digital Library

[34]

Needham, R.M. Protection systems and protection implementations. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 571-578.]]

[35]

Organick, E.I. Computer System Organization--the B5700 B6700 Series. Academic Press, New York, 1973.]]

Digital Library

[36]

Organick, E.I. Tile Multics System: An Examination of Its Structure. MIT Press, Cambridge, Mass., 1972.]]

Digital Library

[37]

Saltzer, J.H. Traffic control in a multiplexed computer system. MAC-TR-30, Proj. MAC, MIT, Cambridge, Mass., 1966.]]

Digital Library

[38]

Schroeder, M.D. Performance of the GE-645 associative memory while Multics is in operation. Proc. Workshop on System Performance Evaluation, Cambridge, Mass., 1971, pp. 227-245.]]

Digital Library

[39]

Schroeder, M.D. Cooperation of mutually suspicious subsystems in a computer utility. Ph.D. Th., MIT, 1972.]]

[40]

Sevick, K.C., et al. Project SUE as a learning experience. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N. J., pp. 331-339.]]

[41]

Shepherd, J. Principal design features of the multi-computer. (The Chicago Magic Number Computer). ICR Quart. Rep. 19 (Nov. 1968), 1CR, U. of Chicago, Sec. 1-C.]]

[42]

Sturgis, H.E. A postmortem of a time sharing system. Ph.D. Th., U. of California, Berkeley, 1973.]]

[43]

Wilkes, M.V. Time Sharing Computer Systems. 2nd ed., American Elsevier, New York, 1972.]]

Digital Library

[44]

Wilner, W.T. Design of the Burroughs BI700. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 489-497.]]

[45]

Wilner, W.T. Burroughs BI700 memory utilization. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 579- 586.]]

[46]

Wulf, W.A., et al. HYDRA: The kernel o f a multiprocessor operating system. Carnegie Mellon U., Comput. Sci. Dep. rep., June 1973.]]

[47]

Yngve, V.H. The Chicago Magic Number Computer. ICR Quart. Rep. 18 (Nov. 1968), ICR, U. of Chicago, Sec. 1-B.]]

Cited By

Schagaev IKaegi TSchagaev IGutknecht J(2024)Recovery PreparationSoftware Design for Resilient Computer Systems10.1007/978-3-031-55139-0_8(127-156)Online publication date: 16-Jul-2024
https://doi.org/10.1007/978-3-031-55139-0_8
Brohet MRegazzoni F(2023)A Survey on Thwarting Memory Corruption in RISC-VACM Computing Surveys10.1145/360490656:2(1-29)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3604906
Samaniego MDeters R(2023)Digital Twins and Blockchain for IoT ManagementProceedings of the 5th ACM International Symposium on Blockchain and Secure Critical Infrastructure10.1145/3594556.3594611(64-74)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3594556.3594611
Show More Cited By

Index Terms

Capability-based addressing
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Hashed file organization
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems

Recommendations

Hierarchical addressing scheme for 6LoWPAN WSN

This paper proposes a hierarchical addressing scheme for 6LoWPAN WSN and aims to reduce the addressing cost and latency. The proposed scheme includes the address initialization and address maintenance algorithms. When the network starts, the address ...
Addressing for 6LoWPAN WBAN

This paper makes a distinction between HoA and CoA, and proposes the addressing algorithms for HoA and CoA, respectively.The CoA addressing is achieved based on the HoA addressing, so the CoA addressing latency is shortened.A WBAN performs the HoA/CoA ...
A survey of addressing algorithms for wireless sensor networks
WiCOM'09: Proceedings of the 5th International Conference on Wireless communications, networking and mobile computing

Addressing is an important research topic for wireless sensor networks (WSNs) because addressing makes it possible to guarantee basic levels of network communication, such as unicast. Addressing approaches focus on dynamic autoconfiguration of addresses ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 17, Issue 7

July 1974

63 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/361011

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Copyright © 1974 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1974

Published in CACM Volume 17, Issue 7

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

315
Total Citations
View Citations
2,108
Total Downloads

Downloads (Last 12 months)276
Downloads (Last 6 weeks)37

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schagaev IKaegi TSchagaev IGutknecht J(2024)Recovery PreparationSoftware Design for Resilient Computer Systems10.1007/978-3-031-55139-0_8(127-156)Online publication date: 16-Jul-2024
https://doi.org/10.1007/978-3-031-55139-0_8
Brohet MRegazzoni F(2023)A Survey on Thwarting Memory Corruption in RISC-VACM Computing Surveys10.1145/360490656:2(1-29)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3604906
Samaniego MDeters R(2023)Digital Twins and Blockchain for IoT ManagementProceedings of the 5th ACM International Symposium on Blockchain and Secure Critical Infrastructure10.1145/3594556.3594611(64-74)Online publication date: 10-Jul-2023
https://dl.acm.org/doi/10.1145/3594556.3594611
Rasifard HGopinath RBackes MNemati HRanise SCarbone RTakabi D(2023)SEAL: Capability-Based Access Control for Data-Analytic ScenariosProceedings of the 28th ACM Symposium on Access Control Models and Technologies10.1145/3589608.3593838(67-78)Online publication date: 24-May-2023
https://dl.acm.org/doi/10.1145/3589608.3593838
Narayan SGarfinkel TTaram MRudek JMoghimi DJohnson EFallin CVahldiek-Oberwagner ALeMay MSahita RTullsen DStefan DAamodt TJerger NSwift M(2023)Going beyond the Limits of SFI: Flexible and Secure Hardware-Assisted In-Process Isolation with HFIProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3582016.3582023(266-281)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3582016.3582023
Dinh Duy KCho KNoh TLee HMeng WJensen CCremers CKirda E(2023)Capacity: Cryptographically-Enforced In-Process Capabilities for Modern ARM ArchitecturesProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623079(874-888)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623079
Lee JKim YCao JKim ELee JKim HSalapura VZahran MChong FTang L(2022)Securing GPU via region-based bounds checkingProceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527420(27-41)Online publication date: 18-Jun-2022
https://dl.acm.org/doi/10.1145/3470496.3527420
Lee SYu YTang YKhandelwal AZhong LBhattacharjee A(2021)MINDProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483561(488-504)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483561
El-Korashy ATsampas SPatrignani MDevriese DGarg DPiessens F(2021)CapablePtrs: Securely Compiling Partial Programs Using the Pointers-as-Capabilities Principle2021 IEEE 34th Computer Security Foundations Symposium (CSF)10.1109/CSF51468.2021.00036(1-16)Online publication date: Jun-2021
https://doi.org/10.1109/CSF51468.2021.00036
Flikkema PPalmer JYalcin TCambou B(2020)Dynamic Computational Diversity with Multi-Radix Logic and Memory2020 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC43674.2020.9286255(1-6)Online publication date: 22-Sep-2020
https://doi.org/10.1109/HPEC43674.2020.9286255
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents