방송기능을 가진 근거리통신망에서 데이타할당을 위한 방법론 = Data Allocation Methodology in Local Area Networks with Broadcast Capability

국문 초록 (Abstract)

분산시스템 설계에서 중요한 것중의 하나는, 정보처리 요구가 주어진 경우에 효과적으로 데이터를 할당하는 것이다. 본 논문에서는 근거리통신망에서 갱신(update)동작이 방송에 의해서 행해진 경우에 적용할 수 있는 데이터 할당기술을 몇가지 소개한다. 모든 제한(constraints)이 없고, 통신비용이 국소처리 비용보다 훨씬 많은 경우에, 선형시간을 갖는 좌적 데이터할당 알고리듬을 구했다. 저장제한(storage constraints)이 없는 경우에 n개의 장소에 m개의 관계데이타를 여분으로 할당할 수 있는 O(m n log n)의 계산복잡성을 갖는 최적알고리듬을 구했다. 저장제한이 있는 경우는 NP-hard 문제로 알려져 있으며, 이 경우 다항식으로 표시될 수 있는 시간에 동작할 수 있는 효과적인 준 최적해가 얻어졌다. 간단한 예를 통하여 휴리스틱(heuristics)을 보였다.

다국어 초록 (Multilingual Abstract)

A critical part of distributed system design is an efficient allocation of data given Information and processing requirements. We describe several data allocation techniques for local area networks in which an update operation is accomplished by broadcast A linear time optimal data allocation algorithm is presented for the case in which all the constraints are relaxed, and communication cost is dominant in comparison with local processing cost An optimal redundant allocation of m relations at n sites without storage constraints is achieved with computational complexity of O (m n log n). The case with storage constraint is known to be a NP-hard problem. In this case, a sequence of heuristics is proposed for an efficient near-optimal solution which runs in polynomial time The heuristics are illustrated with simple numerical examples.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. Introduction
• 2. Problem Formulation and Optimality Conditions
• 3. Data Allocation without Storage Constraint(Case 1)
• 4. Redundant Data Allocation without Storage Constraint(Case 2)
• 5. Data Allocation with Storage Constraints and Multiple Relations (Case 3)
• 6. Conclusion and Future Directions
• REFERENCES
• 저자소개